最详细的排序解析，理解七大排序

mp.weixin.qq.com

点击上方“方志朋”，选择“置顶或者星标”

你的关注意义重大！

注：

lgN在这里为1og₂N简写
为了方便描述,本文默认用int类型比较，从小到大排序
本文排序算法以java语言实现
本文的排序都是比较排序
比较次数和赋值和交换次数有的排序不好分析，可能不准确

一.插入排序

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

从第一个元素开始，该元素认为已经被排序；
取出下一个元素，在已排序的元素序列中从后向前扫描；
如果已排序元素大于新元素，新元素继续比较前一个元素，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~4。

java实现

public static void insertionSort(int[] a){
	int insertIndex,insertElement;
	for(int i = 1; i < a.length; i++){ //外层循环，默认第一个元素有序，从第二个元素开始，时间复杂度N
		insertIndex = i - 1; //插入的位置，默认有序数列的最后一个元素的位置
		insertElement = a[i]; //新插入的元素，默认外层循环的元素
		while(insertIndex >= 0 && a[insertIndex] > insertElement){ //内层循环，只要新元素比待插入位置的元素小就继续，时间复杂度N
			a[insertIndex + 1] = a[insertIndex]; //比待插入元素大的元素后移一位
			insertIndex--; //插入位置前移一位
		}
		a[insertIndex + 1] = insertElement; //内层循环结束，把新元素放到插入位置后面
	}
}

插入排序为两层循环嵌套，时间复杂度O(N²),插入排序的while循环是先比较，移动待插入的位置，循环结束才真正交换数据位置。这里需要注意，常用的for循环嵌套进行插入排序会导致每次插入一直和前面元素交换直到插入到待插入位置，上面的内循环用while寻找待插入位置，把其他元素后移的算法更合理，每次插入只一次进行一次交换。因插入排序每次只比较一位，对于逆序较多的数组效率较低，衍生算法希尔排序，会大幅加快逆序交换，后面详细介绍。

二.选择排序

在未排序序列中找到最小元素，放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾，循环直到所有元素均排序完毕。

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出最小的记录 R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
循环n-1次，排序完成。

java实现

public static void selectionSort(int[] a){
	int minIndex,temp;
	for(int i = 0; i < a.length - 1; i++){ //外层循环，从无序区第一个元素开始到数组倒数第二个元素，时间复杂度N
		minIndex = i; //每次外层循环假设无序区第一个元素是最小元素
		for(int j = i + 1; j < a.length; j++){	//内层循环，从假设的最小元素的后一个位置开始，到数组最后一个元素，时间复杂度N
			if(a[j] < minIndex){ //判断内层循环的元素是否小于假设的最小元素	
				minIndex = j; //如果比最小元素小，标记该元素的位置为新的最小元素的位置，内层循环完毕，会找出无序区的最小值	
			}
		} 
		temp = a[i]; 		
		a[i] = a[minIndex];
		a[minIndex] = temp;	//无序区真正最小值和第一个元素交换位置，下一次循环无序区从下一个值开始
	}
}

选择排序为两层for循环嵌套，内层循环始终去找最小值，放到最前面。交换次数比冒泡排序少很多，所以实际执行效率比冒泡排序快。衍生算法，双向选择排序（每次循环，同时选出最大值放在末尾，最小值放在前方），可以提高选择效率。

三.冒泡排序

重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=0,1,2…n-1)开始时，当前无序区和有序区分别为R[0..n-i]和R[n-i+1..n]。对每一对相邻元素进行比较，从开始第一对到结尾的最后一对，如果第一个比第二个大，就交换它们两个，这样在最后的元素应该会是最大的数，使R[1..n-i-1]和R[n-i..n]分别变为记录个数减少1个的新无序区和记录个数增加1个的新有序区；
循环n-1次，直到排序完成。

java实现

public static void bubbleSort(int[] a){
	int temp;
	for(int i = 0; i < a.length - 1; i++){ //外层循环，从数组第一个元素到倒数第二个元素，时间复杂度为N
		for(int j = 0; j < a.length - 1 -i; j++){ //内层循环，从数组第一个元素到剩余的元素（减去有序区的元素）
			if(a[j] > a[j+1]){ 
				temp = a[j+1];
				a[j+1] = a[j];
				a[j] = temp; //相邻元素只要前面的比后面的大，就交换位置
			}
		}
	}
}

冒泡排序在代码实现上是最简单的，不需要什么思考，两层for循环嵌套，比大小交换。因为冒泡通常的例子都是让大的往后移，对于刚接触排序的人来说看来上面可能认为冒泡排序与选择排序是反向操作，其实冒泡排序也可以把小数向前移，这样能明显的看出冒泡排序和选择的排序的不同，针对无序区的元素，冒泡排序总是不断地交换，而选择排序是先找出最小的元素再做一次交换。衍生算法，鸡尾酒排序，该排序从左往右找出最大值后，再从右往左，找出最小值，类似鸡尾酒搅拌左右循环。在某些情况下，优于冒泡排序，以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问两次（升序降序各一次）次序列就可以完成排序，但如果使用冒泡排序则需要四次。

四.希尔排序

插入排序的改进版，优先比较距离远的元素，减少交换次数

1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 2.按增量序列个数k，对序列进行k 趟排序； 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

java实现

public static void shellSort(int[] a){
	int h = 1； //希尔排序是使间隔为h的元素有序
	int temp;
	while(h < a.length/3) { //while循环，扩大h
		h = 3*h + 1; //这里用3倍作为希尔排序的间隔，是常用的值，加1是为了防止排序的都是3的倍数
	}
	while(h >= 1){ //while循环让h从大到小插入排序
		for(int i = h; i < a.length; i++){  //从h位置开始，对整个数组遍历，i为插入元素的位置
			temp = a[i]; 把i当前值保存到temp中
			for(int j = i - h; j > 0 && a[j] > temp ;j -= h){ //遍历把i每隔h位进行比较，确定插入的位置
				a[j + h] = a[j];  //如果前面的元素大于temp，把前面元素的值放在后面
			}
			a[j + h] = temp; //把原来i的值赋值给前面元素，此时发生了j -=h，实际上j + h等于循环里的j
		}
		h = h/3; //更大间隔的插入完成，缩小插入间隔
	}
}

上面是常用的写法，每次比较，如果前面的更大都会交换，可以优化一下,直接把上面插入算法嵌入内循环，比较的间隔由1改为h,比较的时候只移动插入位置，比较完只需交换一次 java实现

public static void shellSort(int[] a){
	int h = 1； //希尔排序是使间隔为h的元素有序
	int insertIndex,insertElement;
	while(h < a.length/3) { //while循环，扩大h
		h = 3*h + 1; //这里用3倍作为希尔排序的间隔，是常用的值，加1是为了防止排序的都是3的倍数
	}
	while(h >= 1){ //while循环让h从大到小插入排序
		for(int i = h; i < a.length; i++){  //从h位置开始，对整个数组遍历，i为插入元素的位置
			insertIndex = i - h; //插入的位置，默认前面间隔h的位置
			insertElement = a[i]; //新插入的元素，默认外层循环的最后一个元素
			while(insertIndex >= 0 && a[insertIndex] > insertElement){ //内层循环，只要新元素比待插入位置的元素小就继续
				a[insertIndex + h] = a[insertIndex]; //比待插入元素大的元素后移h位
				insertIndex -= h; //插入位置前移h位
			}
			a[insertIndex + h] = insertElement; //内层循环结束，把新元素放到插入位置后面
		}
		h = h/3; //更大间隔的插入完成，缩小插入间隔
	}
}

希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N^1.5)，希尔排序时间复杂度的下界是Nlg2N。希尔排序没有快速排序算法快 O(N(lgN))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N²)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。

五.堆排序

堆就是完全二叉树，分为最大堆和最小堆，最大堆要求节点的元素都要不小于其孩子（最小堆要求节点元素都不大于其左右孩子），对左右孩子的大小关系不做要求，所以处于最大堆的根节点的元素一定是这个堆中的最大值。堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

1.将初始待排序关键字序列(R1,R2….Rn)构造成最大堆，此堆为初始的无序区； 2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]； 3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

java实现

public static void heapSort(int[] a){
	int N = a.length;
	for(int k = N/2; k >= 1; k--){ //for循环用来构造堆，最终生成最大堆
		sink(a,k,N);
	}
	while(N > 1){ //循环排序无序区
		exch(a,1,N--); //堆顶a[1]与堆的最后一个元素a[N]交换位置，并且去掉最后一个元素到有序区，减小新堆
		sink(a,1,N); //重新生成为最大堆
	}
}

/**
 * 从上至下堆有序化
 */
private static void sink(int[] a,int k,int N){ 
	while(2*k <= N) {
		int j = 2*k;
		if(j < N && a[j] < a[j+1]){ //j<n保证j+1不越界，a[j]和a[j+1]是a[k]的左右子节点，这里是为了选取两个子节点较大的一个，a[j]大取a[j],a[j]小取a[j++]>= a[j]) { //如果父节点大于等于值大的子节点，堆有序，终止循环
			break；	
		}
		if(a[k] >= a[j]) { //如果父节点大于等于值大的子节点，堆有序，终止循环
			break；	
		}
		exch(a,k,j); //交换值大的子节点和父节点的值，达到堆有序
		k = j; //子节点，作为下一个循环的父节点，继续下沉
	}
}

/**
 * 交换两个元素
 */
private static void exch(int[] a,int i,int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

}</n保证j+1不越界，a[j]和a[j+1]是a[k]的左右子节点，这里是为了选取两个子节点较大的一个，a[j]大取a[j],a[j]小取a[j++]>

因为堆的父节点k的子节点为2k和2k+1，下标为0会导致父节点和左子节点都是0，所以上述排序的数组从下标从1开始比较方便。堆排序只需要NlgN的时间，而且算法稳定，只需要少量辅助空间，是最优的利用时间和空间的方法，但因为它的缓存命中率低，应用很少用它，多用于嵌入式。

六.归并排序

递归的把已有序列均分为两个子序列，使子序列有序，合并子序列 1.把长度为n的输入序列分成两个长度为n/2的子序列； 2.对这两个子序列分别采用归并排序； 3.将两个排序好的子序列合并成一个最终的排序序列。

java实现

private static int[] aux; //归并所需的辅助数组
public static void mergeSort(int[] a){
	aux = new int[a.length];
	sort(a,0,a.length-1); //开始递归排序
}

/**
 * 递归的排序归并
 */	
private static void sort(int[] a,int left,int right){
	if(right <= left){ //排序从左到右，确保右边比左边大
		return;
	}
	int mid = (left + right)/2; //找出中间位置
	sort(a,left,mid); //将左半边排序
	sort(a,mid+1,right); //将右半边排序
	merge(a,left,mid,right); //归并结果
}

/**
 * 原地归并方法
 */
private static void merge(int[] a,int left,int mid,int right){ //将a[left..mid]和a[mid+1..right]归并
	int i = left,j = mid + 1;  //左右半边起始位置
	for(int k = left; k <= right; k++){ //将a[left..right]复制到aux[left..right]
		aux(k) = a(k);
	}
	for(int k = left; k <= right; k++){ //归并回到a[left..right]
		if(i > mid){  //i比mid大代表左半边用完，只有右半边有元素
			a[k] = aux[j++]; //右边元素给a[k]
		}else if(j > right){ //j比right大代表右半边用完，只有左半边有元素
			a[k] = aux[i++]; //左边元素给a[k]
		}else if(aux[j] < aux[i]){ //如果右边元素大于左边
			a[k] = aux[j++]; //右边元素给a[k]	
		}else{	//否则左边大于等于右边
			a[k] = aux[i++]; //左边元素给a[k]
		}
	}
}

归并排序是分治法的典型应用，高效稳定，但是归并排序需要一个数组长度的辅助空间，在空间成本高的时候不适合使用

七.快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1.从数列中挑出一个元素，称为 “基准”（pivot）； 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

java实现

public static void quickSort(int[] a){
	sort(a,0,a.length-1);
}

/**
 * 递归进行快速排序
 */
private static void sort(int[] a,int left,int right){
	if(right <= left){ //排序从左到右，确保右边比左边大
		return;
	}
	int j = partition(a,left,right); //切分
	sort(a,left,j-1); //将左半边排序
	sort(a,j+1,right); //将右半边排序
}

/**
 * 快速排序切分
 */
private static int partition(int[] a,int left,int right){ 
	int i = left,j = right + 1; //左右扫描指针
	int v = a[left]; //选取切分元素，这里选第一个，实际数据可以自行挑选
	while(true){
		while(a[++i] < v){ //a[i]<v时增大i，只要比v小继续往右扫描 i="=" v="">< a[--j]){ //a[j]>v时减小j，只要比v大继续往左扫描
			if(j == left){ //扫描到左边则终止
				break;
			}
		}
		while(v < a[--j]){ //a[j]>v时减小j，只要比v大继续往左扫描
			if(j == left){ //扫描到左边则终止
				break;
			}
		}
		if(i >= j){ //如果左右指针交叉，终止循环
			break; 
		}
		exch(a,i,j); //不满足上述条件（左边比v大，右边比v小，指针未交叉），左右元素交换位置
	}
	exch(a,left,j); //将切分元素v放入正确的位置
	return j; //a[left..j-1]<=a[j]<=a[j+1..right]，并返回j
}

/**
 * 交换两个元素
 */
private static void exch(int[] a,int i,int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}</v时增大i，只要比v小继续往右扫描>

快速排序是通常情况下的最优选择，高效，只需要lgN级别的辅助空间，但是快速排序不稳定，受切分点的影响很大

七种排序总结

上面详细介绍了七种排序的实现细节和特点，下面的表格总结了七种排序的各种特征。

其中插入排序，选择排序，冒泡排序都是简单排序，时间复杂度是O(N²),其中插入排序和冒泡排序适合原始序列有序的数组，选择排序的交换和赋值次数会比较少，可以根据不同环境和数据的实际情况和长度选择具体的排序。整体插入排序优于选择排序优于冒泡排序。希尔排序是插入排序的优化，突破了前三个排序O(N²)的时间复杂度，但是本质还是插入排序，突破比较相邻元素的惯性思维，直接比较一定间隔的元素，大幅度减少了逆序调整的比较次数和交换次数，从而达到比较理想的算法复杂度，适合对中等规模数组进行排序。堆排序是利用了最大堆的特点，始终把堆顶元素（最大元素）和最后一个元素替换，再重新构造最大堆，重复执行达到排序的效果。堆结构的特性让算法的复杂度降低到NlgN级别，但是有不方便索引元素的确定，缓存命中率较低。而归并排序则是充分运用了分治原理，把大问题不断的拆分成小问题，进行排序，再合并小数组达到整体排序的目标，归并排序即高效又可靠，唯一的缺点是需要数组长度的辅助空间，在空间成本低的时候适合使用。快速排序则解决了归并排序占用空间的问题，在数组内部用很小的辅助栈，即可完成对元素的分离，再去解决分离后的更小的数组，正常情况下拥有和归并相同级别的时间复杂度，但是得注意选取好切分元素。实际上一个复杂的序列可能用不止一种排序，例如分治和快速排序在分割到很小的序列时再进行分割反而效率不如插入排序等简单排序，可以设置一定的阈值，先用分治或者快速排序的方式分割数组，再转换成插入等简单排序完成最终的排序。

希望本文大家加深对排序的理解有所帮助。我的微信公众号：程序之路，会持续发布技术成长文章，欢迎长按下图关注