七种基本排序（1）

插入、希尔

选择、堆

冒泡（交换）

归并

快速排序

小咲的开心一刻

前言

大家好，我是小咲，封面是我最喜欢的学妹Himeragi Yukina ，好的心情才能写出代码呢，嗯嗯我没有流口水……

Java语言的对象就像现实世界里的XXX，如果没有的话，我还有封面啦啦啦

言归正传，介绍前面四种排序方法，首先呢先看看具体代码是怎么实现的吧

插入排序

public static void insert(int[] array) {
	//减治算法外层循环长度-1
	for(int i=0;i<array.length-1;i++) {
		//有序区间 [0,i]
		//无序区间 [i+1,length)
		int j;int key=array[i+1];//key在无序区间首元素
		//从后向前遍历
		for(j=i;j>=0;j--) {
			if(array[j]<=key) break;
			//搬家
			array[j+1]=array[j];
		}
		//跳出循环发朋友圈赋值
		array[j+1]=key;
	}
}

希尔排序

书写技巧：

机理：希尔排序自插入排序改进而来，改进了插入排序从后往前的内层循环多此遍历的情况，降低了平均时间

将插入排序的1换成gap，就可以该成希尔排序了

insertwithGap

public static void shell(int[] array) {
	int gap=array.length;
	while(true) {
	gap/=2;//分组公式，或者写成gap=gap/3+1;都可以接受
	insertwithGap(array,gap);
	if(gap==1) break;
	}
}
private static void insertwithGap(int[] array,int gap) {
	//减治算法外层循环长度-1
	for(int i=0;i<array.length-gap;i++) {
		//有序区间 [0,i]
		//无需区间 [i+1,length)
		int j;int key=array[i+gap];//key在无序区间首元素
		//从后向前遍历
		for(j=i;j>=0;j-=gap) {
			if(array[j]<=key) break;
			//搬家
			array[j+gap]=array[j];
		}
		//跳出循环发朋友圈赋值
		array[j+gap]=key;
	}
}

选择排序

//选择排序（数据不敏感的排列方式）
public static void chooseMax(int[] array) {
	//减治算法外层循环长度-1
	for(int i=0;i<array.length-1;i++) {
		int max=0;//假设第一个元素最大,max下标记作0
		//无数认识到减治算法大的人会将这里写成j<array.length-1-i
		//但如此首元素就会被忽视，所以如果初次学习，可以忽视减治算法外层循环长度-1的优化
		for(int j=1;j<array.length-i;j++) {
			if(array[max]<array[j])
				max=j;
		}
		//跳出循环找到最大值max交换
		wrap(array,array.length-1-i,max);//目的最大元素放到最后
	}
}
public static void wrap(int[] array, int i, int k) {
	// TODO 自动生成的方法存根
	int t;
	t=array[i];
	array[i]=array[k];
	array[k]=t;
}

堆排序

public static void heapSort(int[] array) {
	//建立一个堆
	createHeap(array);
	//减治算法外层循环-1
	for(int i=0;i<array.length-1;i++) {
		//找到最大值max交换，这里大堆，下标0处为最大元素
		wrap(array,array.length-1-i,0);
		heapify(array,array.length-i-1,0);
	}
}
private static void createHeap(int[] array) {
	// TODO 自动生成的方法存根
	//最后一个父节点开始遍历调整
	int parent=(array.length-1-1)/2;
	for(int i=parent;i>=0;i--) {
		heapify(array,array.length,i);//数组，实际长度，调整下标位置
	}
}
private static void heapify(int[] array, int size, int index) {
	// TODO 自动生成的方法存根
	//（是否是叶子节点）判断是否越界
	//max记录：比较左右孩子谁大
	//max与index比较是否需要交换（建立大堆，如果array[index]<array[max]需要交换，否则不需要）
	//违反下标规则
	if(size<=index) return;
	while(true) {
		int leftchild=2*index+1;
		int rightchild=2*index+2;
		if(leftchild>=size) return;//左孩子存在
		int max=leftchild;
		if((rightchild<size)&&(array[leftchild]<array[rightchild]))
			max=rightchild;
	    //注意这里返回
		if(array[index]>=array[max]) {return;}
	    	wrap(array,index,max);
	    	index=max;
	    	}
	}
public static void wrap(int[] array, int i, int k) {
	// TODO 自动生成的方法存根
	int t;
	t=array[i];
	array[i]=array[k];
	array[k]=t;
}

测试代码

package 排序;

import java.util.Arrays;
//什么是有序序列？无序序列？
//有序序列是已经排好的数据的集合，无序序列就是还未排好，或者准备排序的集合
//什么是减治算法
//顾名思义就是每次遍历（循环）,数据规模都逐渐减小，
//例如选择排序，每次挑选一个最大的放入有序序列，无序序列减小，
//又例插入排序中每一次取一个元素与已经排好的序列进行比较
//减治算法典型的算法举例
//选择和插入排序
//在代码里有什么体现
//外层循环-1，内层不变
public class Solution {
public static void insert(int[] array) {
	//减治算法外层循环长度-1
	for(int i=0;i<array.length-1;i++) {
		//有序区间 [0,i]
		//无需区间 [i+1,length)
		int j;int key=array[i+1];//key在无序区间首元素
		//从后向前遍历
		for(j=i;j>=0;j--) {
			if(array[j]<=key) break;
			//搬家
			array[j+1]=array[j];
		}
		//跳出循环发朋友圈赋值
		array[j+1]=key;
	}
}
public static void shell(int[] array) {
	int gap=array.length;
	while(true) {
	gap/=2;
	insertwithGap(array,gap);
	if(gap==1) break;
	}
}
private static void insertwithGap(int[] array,int gap) {
	//减治算法外层循环长度-1
	for(int i=0;i<array.length-gap;i++) {
		//有序区间 [0,i]
		//无需区间 [i+1,length)
		int j;int key=array[i+gap];//key在无序区间首元素
		//从后向前遍历
		for(j=i;j>=0;j-=gap) {
			if(array[j]<=key) break;
			//搬家
			array[j+gap]=array[j];
		}
		//跳出循环发朋友圈赋值
		array[j+gap]=key;
	}
}
//选择排序（数据不敏感的排列方式）
public static void chooseMax(int[] array) {
	//减治算法外层循环长度-1
	for(int i=0;i<array.length-1;i++) {
		int max=0;//假设第一个元素最大,max下标记作0
		//无数认识到减治算法大的人会将这里写成j<array.length-1-i
		//但如此首元素就会被忽视，所以如果初次学习，可以忽视减治算法外层循环长度-1的优化
		for(int j=1;j<array.length-i;j++) {
			if(array[max]<array[j])
				max=j;
		}
		//跳出循环找到最大值max交换
		wrap(array,array.length-1-i,max);//目的最大元素放到最后
	}
}
public static void bubbleSort(int[] array) {
	for(int i=0;i<array.length-1;i++) {
		for(int j=0;j<array.lengt-i-1;j++) {
			if(array[j]>array[j+1])
				wrap(array,j,j+1);
		}
	}
}
public static void wrap(int[] array, int i, int k) {
	// TODO 自动生成的方法存根
	int t;
	t=array[i];
	array[i]=array[k];
	array[k]=t;
}
public static void heapSort(int[] array) {
	//建立一个堆
	createHeap(array);
	//减治算法外层循环-1
	for(int i=0;i<array.length-1;i++) {
		//找到最大值max交换，这里大堆，下标0处为最大元素
		wrap(array,array.length-1-i,0);
		heapify(array,array.length-i-1,0);
	}
}
private static void heapify(int[] array, int size, int index) {
	// TODO 自动生成的方法存根
	//（是否是叶子节点）判断是否越界
	//max记录：比较左右孩子谁大
	//max与index比较是否需要交换（建立大堆，如果array[index]<array[max]需要交换，否则不需要）
	//违反下标规则
	if(size<=index) return;
	while(true) {
		int leftchild=2*index+1;
		int rightchild=2*index+2;
		if(leftchild>=size) return;//左孩子存在
		int max=leftchild;
		if((rightchild<size)&&(array[leftchild]<array[rightchild]))
			max=rightchild;
	    //注意这里返回
		if(array[index]>=array[max]) {return;}
	    	wrap(array,index,max);
	    	index=max;
	    	}
	}
/*private static void createHeap(int[] array) {
	// TODO 自动生成的方法存根
	//最后一个父节点开始遍历调整
	int parents=(array.length-1-1)/2;
	for(int i=parents;i>=0;i--) {
		heapify(array,i,0);
	}
	
}*/
private static void createHeap(int[] array) {
	// TODO 自动生成的方法存根
	//最后一个父节点开始遍历调整
	int parent=(array.length-1-1)/2;
	for(int i=parent;i>=0;i--) {
		heapify(array,array.length,i);//数组，实际长度，调整下标位置
	}
	
}
public static void main(String[] args) {
	int[] array1= {8,1,2,3,4,9,5,6,3};
	int[] array2= {9,8,7,6,5,4,3,2,1};
	int[] array3= {8,1,2,3,4,9,5,6,3};
	int[] array= {9,8,7,6,5,4,3,2,1};
	//插入排序
	insert(array1);
	//选择排序（选择最大）
	chooseMax(array2);
	//希尔排序
	shell(array3);
	//堆排序
	heapSort(array);
	//bubbleSort(array);
	System.out.println(Arrays.toString(array1));
	System.out.println(Arrays.toString(array2));
	System.out.println(Arrays.toString(array3));
	System.out.println(Arrays.toString(array));
}
}

小咲的绝对领域

打破砂锅问到底，小咲什么都知道

 

什么是有序序列？无序序列？
有序序列是已经排好的数据的集合，无序序列就是还未排好，或者准备排序的集合
 

什么是减治算法
顾名思义就是每次遍历（循环）,数据规模都逐渐减小，
例如选择排序，每次挑选一个最大的放入有序序列，无序序列减小，
又例插入排序中每一次取一个元素与已经排好的序列进行比较
 

减治算法典型的算法举例
选择和插入排序
在代码里有什么体现
外层循环-1，内层不变

小咲小咲有话说

后记

       有的时候也挺奇怪的，不知道为什么就是想不出算法是怎么写的，特别是隔一段时间基本上想不起来原来是怎么想的，我现在就想总结一个方法能够记住这些代码

由于介绍的都是减治算法，外层遍历统统-1，这就呈现出代码外层for(int i=0;i<array.length-1;i++）

其次插入算法内层思路实际上是你先画一排序好的几个数（有序序列）比如[1][2][5]，再画一个需要插入的数字3（无序序列），这个时候将有序序列这几个数的最后一个数就是i的位置（这里就是元素[5]），然后内层循环，设j=i向前遍历，此时你需要做的就是终止条件：待插入的数字j+1（下标）大于j下标的数字，这里描述必须画一张图片

简单选择不停地将大的元素放到最后，想想就是遍历一遍找到最大的元素然后与未排序好的序列最后一个元素交换

推荐书籍：啊哈！算法