经典排序算法总结

缺乏、安全感 2022-04-03 14:43 260阅读 0赞

### 排序算法总结 ###

> Author: Sean / Date:2018-12-11

排序的算法的分类标准有很多，最简单的事根据复杂度进行划分。分为简单排序和复杂排序。

#### 简单排序 ####

*  简单选择排序
 *  简单插入排序
 *  冒泡排序

#### 复杂排序 ####

*  希尔排序
 *  堆排序
 *  归并排序
 *  快速排序

#### 应用实例 ####

*  应用实例1: `Colletions.sort()`方法实现
 *  应用实例2: 数据库`Order By`方法实现

当然，还有`梳排序`、`计数排序`、`桶排序`、`基数排序`等排序算法。后面的几种排序算法，使用不多，暂时概不提及。

--------------------

### 简单排序 ###

*  简单选择排序(Selection Sort)

简单选择排序的思想是，每次从`N-K+1`个数中，选择`最大/最小`的数字放入第`K`个位置上。

> 排序细节:
> 
> 原始数字: 6 5 3 1 8 7 2 4
> 
> (K=1 排列第1位) （`1`) 5 3 `6` 8 7 2 4
> 
> (K=2 排列第2位) (1 `2`) 3 6 8 7 `5` 4
> 
> (K=3 排列第3位) (1 2 `3`) 6 8 7 5 4
> 
> (K=4 排列第4位) (1 2 3 `4`) 8 7 5 `6`
> 
> (K=5 排列第5位) (1 2 3 4 `5`) 7 `8` 6
> 
> (K=6 排列第6位) (1 2 3 4 5 `6`) 8 `7`
> 
> (K=7 排列第7位) (1 2 3 4 5 6 `7`) `8`
> 
> (K=8 排列第8位) (1 2 3 4 5 6 7 8)

### 伪代码
    
    for i <- 1 to length(A)
       min <- i
       for j <- i + 1 to length(A){
       		if (A[min]>A[j]){
       			min <- j
       		}
       		j <- j + 1
       }

// 选择排序
    	public static boolean selectionSort(int array[]){
    		boolean flag = false;  
    		if(null != array && array.length > 0){
    			// 每次确定array[i]的最终数字
    			for(int i=0; i<array.length ; i++){
    				int min = i;
    				for(int j = i+1; j<array.length;j++){
    					if(array[j]<array[min]){
    						min = j;
    					}
    				}
    			}
    			flag = true;
    		}
    		return flag;
    	}

> 最好情况:比较N-1,…1次，总计(N)(N-1)/2次,不用交换。
> 
> 最坏情况:比较N-1,…1次，总计(N)(N-1)/2次,交换(N-1)次。
> 
> 平均复杂度: 比较O(N^2)，交换O(N).
> 
> 评价:不稳定排序，最好情况和最坏情况基本一致。复杂度O(N^2).复杂度和冒泡一致，但是基本上还是优于冒泡排序。
> 
> > 参考文献
> 
> \[1\] [Wiki - selection sort][]
> 
> \[2\]

> 简单(直接)选择排序的稳定性？

举个栗子:(要求从小到大排序)  
8 5 8 7 9  
简单选择排序:  
第二次外循环8和8的相对顺序就发生了改变,违反了稳定性的定义,故不稳定;

> 朴素的直接选择排序是不稳定的，这毫无疑问。当然可以写成稳定的版本。  
> 稳定的排序：直接插入排序、冒泡排序、归并排序  
> 不稳定的排序：希尔排序、直接选择排序、堆排序、快速排序
> 
> [简单(直接)选择排序的稳定性？][Link 1]

*  简单插入排序(Insertion Sort)

![insertion-sort-gif][]

从第一个数字开始排序，每次让前K个数字变得有序。对于K+1个数字，依次与前K个数字进行比较，决定第K+1个数字的位置。

> 排序细节:
> 
> 原始数字: 6 5 3 1 8 7 2 4
> 
> (K=1 排列数字6) `6`
> 
> (K=2 排列数字5) `5` 6
> 
> (K=3 排列数字3) `3` 5 6
> 
> (K=4 排列数字1) `1` 3 5 6
> 
> (K=5 排列数字8) 1 3 5 6 `8`
> 
> (K=6 排列数字7) 1 3 5 6 `7` 8
> 
> (K=7 排列数字2) 1 `2` 3 5 6 7 8
> 
> (K=8 排列数字4) 1 2 3 `4` 5 6 7 8

### 伪代码
    
    for i ← 1 to length(A)
        j ← i
        while j > 0 and A[j-1] > A[j]
            swap A[j] and A[j-1]
            j ← j - 1

### Java代码
    
    // 选择排序
    	public static boolean insertionSort(int array[]){
    		boolean flag = false;  
    		if(null != array && array.length > 0){
    			// 从array[0]开始排起，每次添加array[i]作为新元素插入
    			for(int i=0;i<array.length;i++){
    				int j = i;
    				while(j > 0 && array[j] < array[j-1]){
    					swap(array,j,j-1);
    					j--;
    				}
    			}
    			flag = true;
    		}
    		return flag;
    	}

> 最好情况:比较N次，不用交换。复杂度O(N),交换O(N).
> 
> 最坏情况:比较1,2,3 … N-2次,总计(N-1)(N-2)/2次。复杂度O(N2)，交换O(N2).
> 
> 平均复杂度: 比较O(N2)，交换O(N2).
> 
> 评价:同样O(N^2)的时间复杂度，直接插入排序比冒泡和选择排序性能稍微好一点。

*  冒泡排序(Bubble Sort)

冒泡排序思想:两两比较相邻纪录的关键字。排序过程中，最小的数字像气泡一样慢慢浮上来，由此得名。冒泡排序的核心在于`相邻的数字两两比较`。自上而下的冒泡算法和自下而上的冒泡算法都可以。

![buddle-sort-gif][]

> 排序细节:
> 
> 原始数字: 6 5 3 1 8 7 2 4
> 
> (K=1) `5` `6` 3 1 8 7 2 4
> 
> (K=1) 5 `3` `6` 1 8 7 2 4
> 
> (K=1) 5 3 `1` `6` 8 7 2 4
> 
> (K=1) 5 3 1 `6` `8` 7 2 4
> 
> (K=1) 5 3 1 6 `7` `8` 2 4
> 
> (K=1) 5 3 1 6 7 `2` `8` 4
> 
> (K=1) 5 3 1 6 7 2 `4` `8`

![bubble-sort][]

### 伪代码
    
    for i <- 1 to length(A)
        for j <- 1 to length(A)-i-1
        	// 为了让j+1不越界(j+1 < length(A)-i) -> (j < length(A)-i-1)
        	if(A[j]>A[j+1]){swap(j,j+1)}
        	j++;

### Java代码
    	// 冒泡排序
    	public static boolean bubbleSort(int array[]){
    		boolean flag = false;  
    		if(null != array && array.length > 0){
    			// 每次确定array[i]的最终数字
    			for(int i=0; i<array.length ; i++){
    				int j = 0;
    				for(; j<array.length-i-1;j++){
    					if(array[j]>array[j+1]){
    						swap(array, j, j+1);
    					}
    				}
    			}
    			flag = true;
    		}
    		return flag;
    	}

*  希尔排序(Shell Sort)

希尔排序是按照不同的步长进行插入排序。初始时，元素无序时，步长较大，每组内元素较少，速度很快。当元素基本有序时，步长较小，元素较多，但是元素基本有序，插入排序对于基本有序的序列效率较高。(插入排序是稳定的，但是希尔排序相当于多次插入排序，所以是不稳定的。)

![shell-sort][]

> > WIKI  
> > \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lCgkG8ob-1591086681525)(https://upload.wikimedia.org/math/9/8/a/98a5e472f889c0db4a6bdae9f56ed052.png)\]  
> > 如上图我们去d1=5，d2=3，d3=1
> 
> d=5时，分组为 (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10)，对组内的元素进行分别插入排序，得到第二排数组
> 
> d=3时，分组为(a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12)，对其分组插入排序，得到第三排数组。
> 
> d=1时，分组为 (a1,…, a12)，进行插入排序，得到结果。

# 伪代码数组默认从1开始计算
    array 数组; 
    length 数组长度; 
    step步长(通常取值为length/2);
    
    for (step =length/2; step >= 1; step=step/2){
    	// 内嵌插入排序
    	for(j=d+1;j <= length;j++){
    		// 注意此处的j-d不要越界
    		int tmpJ = j; 
    		while((tmpJ-d)>=1 & a[tmpJ] < a[tmpJ-d]){
    			swap(array, tmpJ, tmpJ-d);
    			tmpJ = tmpJ-d;
    		}
    	}
    }

#Java代码
    /**
     * 希尔排序
     * 1. 选择j,将a[0] a[0+j] a[0+2j]分成一组进行插入排序
     * 2. 缩小j j--
     * 3. 重复1,2步骤，直到循环结束(j=1)
     * */
    public class ShellSortAlgorithm {
    	public static boolean sort(int array[]){
    		boolean flag=false;
    		if(null != array && array.length > 0){
    			for(int j = array.length/2; j>=1 ;j=j/2){
    				// 内嵌插入排序
    				for(int i=j;i<array.length;i++){
    					int tmp = i;
    					while(tmp >= j && array[tmp] < array[tmp-j]){
    						tmp = tmp-j;
    						SortUtil.swap(array,i,tmp);
    					}
    				}
    			}
    			flag = true; 
    		}
    		return flag;
    	}
    	
    	public static void main(String[] args) {
    //		int array1[] = {4,2,3,6,1,2};
    		int array1[] = {4,2,3,6,1,2,2,312,23,32,3,2,1,14,5,2,1,132,4};
    
    		SortUtil.print(array1);
    		ShellSortAlgorithm.sort(array1);
    		SortUtil.print(array1);
    	}
    
    }

> 平均复杂度: 比较O(N \* log2N).
> 
> 评价:希尔排序是第一种将复杂度低于O(N^2)的算法。对于步长(Step)的选择可以根据数据集的大小进行决定。(具体的时间复杂度证明可以查看参考文献4与5)
> 
> 希尔排序是对于插入排序的一种改善。希尔排序是按照不同的步长进行插入排序。初始时，元素无序时，步长较大，每组内元素较少，速度很快。当元素基本有序时，步长较小，元素较多，但是元素基本有序，插入排序对于基本有序的序列效率较高。

> > 参考文献
> 
> \[1\] [《Thinking in Algorithm》12.详解十一种排序算法][Thinking in Algorithm_12.]
> 
> \[2\] [百度经验: 希尔排序][Link 2]
> 
> \[3\] [图解排序算法(二)之希尔排序][Link 3]
> 
> \[4\] [数据结构基础 希尔排序 之 算法复杂度浅析][_ _]
> 
> \[5\] [希尔排序&选择排序&时间复杂度分析][Link 4]
> 
> \[6\] [希尔排序 时间复杂度 证明][Link 5]

*  归并排序(Merge Sort)-2路归并

![merge-sort-gif][]

归并排序的核心在于分冶法。先使用分冶将排序的元素分成间隔为1的个体，然后合并成2/4/8/…步长的合集。

![merge-sort-svg][]

分冶

![merge-sort][]

归并  
![merge-sort-2][]

# 伪代码
    
    void mergeSort(int []array,int begin,int end){
    	if(begin<end){
    		int mid = (begin+end)/2;
    		// 分冶
    		mergeSort(array,begin,mid);
    		mergeSort(array,mid+1,end);	
    		//归并
    		merge(array,begin,end);
    	}	
    }

#Java代码
    
    /**
     * 归并排序 (将集合先分离，在合并)
     * 1. 将集合从中间分离
     * 2. 将集合合并
     * 3. 重复步骤1，2直到循环结束
     * */
    public class MergeSortAlgorithm {
    	public static boolean sort(int array[]){
    		boolean flag = false;
    		if(null != array && array.length > 0){
    			// 拷贝一个一样大小都array数组作为辅助
    			int []tmpArray = array.clone();
    			sort(array,0,array.length-1,tmpArray);
    			flag = true;
    		}
    		return flag;
    	}
    	
    	public static void sort(int array[],int front,int second,int []tmpArray){
    		if(front < second){
    			int mid = (front+second)/2;
    			sort(array,front,mid,tmpArray);
    			sort(array,mid+1,second,tmpArray);
    			merge(array, front, second, tmpArray);
    		}
    	}
    	
    	public static void merge(int array[],int front,int second,int []tmpArray){
    		int mid = (front+second)/2;
    		int tmpFront = front;
    		int tmpSecond = mid+1;
    		int tmpIndex = 0;
    		while(tmpFront <= mid && tmpSecond <= second ){
    			if(array[tmpFront] < array[tmpSecond]){
    				tmpArray[tmpIndex++] = array[tmpFront++];
    			}else{
    				tmpArray[tmpIndex++] = array[tmpSecond++];
    			}
    		}
    		while(tmpFront <= mid){
    			tmpArray[tmpIndex++] = array[tmpFront++];
    		}
    		while(tmpSecond <= second){
    			tmpArray[tmpIndex++] = array[tmpSecond++];
    		}
    		tmpFront = front;
    		tmpIndex = 0;
    		while(tmpFront <= second){
    			array[tmpFront++] = tmpArray[tmpIndex++];
    		}
    	}
    	
    	public static void main(String[] args) {
    //		int array1[] = {4,2,3,6,1,2};
    		
    		int array1[] = {4,2,3,6,1,2,2,312,23,32,3,2,1,14,5,2,1,132,4};
    
    		SortUtil.print(array1);
    		MergeSortAlgorithm.sort(array1);
    		SortUtil.print(array1);
    	}
    }

> 归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
> 
> 个人理解: 归并排序主要应用了分冶法，通过递归和迭代将2-4-8-16-…元素变成有序序列。由于用到了完全二叉树，所以平均复杂度为O(N \* logN)。因为排序时为进行大量的相互变换，所以是一种稳定排序。速度比快速排序要差，但是算法较为稳定。
> 
> > 参考文献  
> > \[1\] [图解排序算法(四)之归并排序][Link 6]  
> > \[2\] [《Thinking in Algorithm》12.详解十一种排序算法][Thinking in Algorithm_12.]  
> > \[3\] [wiki-merge sort][]  
> > \[4\] [百度经验-归并排序][-]

*  堆排序(Heap Sort)

堆是一种树形结构。堆排序的主要过程就是不读构建堆结构(大顶堆/小顶堆)，随后不断替换第一个和最后一个元素，再重复构建堆结构，使最后一个元素有序的过程。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iDKEl5Lr-1591086681533)(https://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif)\]

![heap-sor][]

#Java 代码
    /**
     * 堆排序
     * 1. 初始化堆
     * 2. 将堆a[0]与a[back]互换
     * 3. 重新构建堆
     * 4. 重复2,3步骤直到循环停止
     * 
     * */
    public class HeapSortAlgotitm {
    	public static boolean sort(int []array){
    		boolean flag = false;
    		if(null !=array && array.length > 0){
    			// first set heap 
    			for(int i = (array.length/2)-1;i>=0;i--){
    				adjustHeap(array,i,array.length);
    			}	
    			// other sort
    			for(int j=array.length; j > 0;j--){
    				SortUtil.swap(array,0,j-1);
    				adjustHeap(array, 0, j);
    			}
    			flag=true;
    		}
    		return flag;
    	}
    	
    	public static void adjustHeap(int []array,int root,int length){
    		int tmp = array[root];
    		for(int i=root*2+1;(i+1)<length;i=i*2+1){
    			// a[i*2+1] 与 a[i*2+2]的比较
    			if(array[i] < array[i+1]){
    				i=i+1;
    			}
    			// array[root]与array[i]比较
    			if(tmp >= array[i]){
    				break;
    			}else{
    				array[root] = array[i];
    				// swap(array,root,i);
    				root =  i; // 是变化的最后变成array[root]的值的地方
    			}
    		}
    		array[root] = tmp;	
    	}
    	
    	public static void main(String[] args) {
    		int array1[] = {4,2,3,6,1,2};
    		SortUtil.print(array1);
    		HeapSortAlgotitm.sort(array1);
    		SortUtil.print(array1);
    	}
    
    }

> > 参考文献:  
> > \[1\]

*  快速排序(Quick Sort)

快速排序的思路是：选择一个中间值，把小于中间值的都排列在左边，大于中间值的都排列在右边。然后不断迭代。

![quick-sort][]

#伪代码
    QUICKSORT(A, p, r)
     1 if p < r
     2    then q ← PARTITION(A, p, r)
     3         QUICKSORT(A, p, q - 1)
     4         QUICKSORT(A, q + 1, r)

#Java代码
    package com.yanxml.algorithm.classical.sort;
    
    /**
     * 快速排序
     * 1. 选取中间值K,比K大的都排右边，比K小的都排左边。
     * 2. 重复1步骤直到循环结束
     * */
    public class QuickSortAlgorithm {
    
    	public static boolean sort(int []array){
    		boolean flag = false;
    		if(null != array && array.length >0 ){
    			sort(array,0,array.length-1);
    			flag = true;
    		}
    		return flag;
    	}
    	
    	public static void sort(int []array,int front,int second){
    		if(front < second){
    //			int mid = partition(array, front, second);
    			int mid = partition2(array, front, second);
    			sort(array, front, mid-1);
    			sort(array, mid+1, second);
    		}else{
    //			break;
    		}
    	}
    	
    	// 交换法
    	public static int partition(int []array,int front,int second){
    		// 选取中间值
    		int tmp = array[front];
    		int index = front;
    		
    		int tmpFront = front;//前指针
    		int tmpBack = second;//后指针
    		
    		while(tmpFront < tmpBack){
    			// 前和后都优先扫描顺序不太好判断
    			// 这段代码写在前和后得到都结果完全不同
    			while(array[tmpBack] >= tmp && tmpFront < tmpBack){
    				tmpBack--;
    			}
    			while(array[tmpFront] <= tmp && tmpFront < tmpBack){
    				tmpFront++;	
    			}
    			SortUtil.swap(array,tmpFront,tmpBack);
    		}
    		index = tmpFront;
    		SortUtil.swap(array,front,index);
    		return index;
    	}
    	
    	// 占坑法
    	public static int partition2(int []array,int front,int second){
    		// 选取中间值
    		int tmp = array[front];
    		int index = front;
    		
    		int tmpFront = front;//前指针
    		int tmpBack = second;//后指针
    		
    		while(tmpFront < tmpBack){
    			while(array[tmpBack] > tmp && tmpFront < tmpBack){
    				tmpBack--;
    			}
    			array[tmpFront] = array[tmpBack];
    			while(array[tmpFront] <= tmp && tmpFront < tmpBack){
    				tmpFront++;	
    			}
    			array[tmpBack] = array[tmpFront];
    		}
    		index = tmpFront;
    		array[index] = tmp;
    		return index;
    	}
    	
    	public static void main(String[] args) {
    //		int array1[] = {4,2,3,6,1,2};
    		
    		int array1[] = {4,2,3,6,1,2,2,312,23,32,3,2,1,14,5,2,1,132,4};
    
    		SortUtil.print(array1);
    		QuickSortAlgorithm.sort(array1);
    		SortUtil.print(array1);
    	}
    }

> 快速排序是当前速度最快的排序方式，时间复杂度为O(N\*logN)。取中值时，可以选择中间值作为中值。(即三数取中法)
> 
> > 参考文献
> 
> \[1\] [ 图解排序算法(五)之快速排序——三数取中法 ][Link 7]  
> \[2\] [快速排序(三种算法实现和非递归实现)][Link 8]

--------------------

### Others ###

\[1\] [《Thinking in Algorithm》12.详解十一种排序算法][Thinking in Algorithm_12.]

\[2\] [图解排序算法][Link 9]

\[3\] [Arrays.sort和Collections.sort实现原理解析][Arrays.sort_Collections.sort]

\[4\] [MySQL排序内部原理探秘][MySQL]

\[5\] [MySQL order by实现原理分析和Filesort优化][MySQL order by_Filesort]

\[6\] [MySQL排序原理与案例分析][MySQL 1]

\[7\] [\[经典排序算法\]\[集锦\]][Link 10]

\[8\] [十大经典排序算法（动图演示）][Link 11]

\[9\] [字符串 模式匹配][Link 12]

[Wiki - selection sort]: https://en.wikipedia.org/wiki/Selection_sort
[Link 1]: https://zhidao.baidu.com/question/17264385.html
[insertion-sort-gif]: /images/20220403/2b37d2b3bcac47dd8c7e7855d94f6f25.png
[buddle-sort-gif]: /images/20220403/ca5188e6f45843d28c8cd893b786557c.png
[bubble-sort]: /images/20220403/1594746cb4144bd7979786230cfb6ffd.png
[shell-sort]: /images/20220403/69207c89b3584887b4f78d3057c77833.png
[Thinking in Algorithm_12.]: https://blog.csdn.net/speedme/article/details/23021467
[Link 2]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin
[Link 3]: http://www.cnblogs.com/chengxiao/p/6104371.html
[_ _]: https://blog.csdn.net/u013630349/article/details/48250109
[Link 4]: https://blog.csdn.net/ginnosx/article/details/12263619
[Link 5]: https://blog.csdn.net/u013007900/article/details/51232472
[merge-sort-gif]: /images/20220403/a1457e8aa8984e33bba6e0681bd25ec5.png
[merge-sort-svg]: /images/20220403/c1506ade35754777bd0ededea4319dbd.png
[merge-sort]: /images/20220403/7740199080b84e8da705b7b9e6c64dd8.png
[merge-sort-2]: /images/20220403/c7440c33bd8d4659a9d2b1037b7a242f.png
[Link 6]: https://www.cnblogs.com/chengxiao/p/6194356.html
[wiki-merge sort]: https://en.wikipedia.org/wiki/Merge_sort
[-]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin
[heap-sor]: /images/20220403/28eb33018b3e4e9287b7a83af0608f7e.png
[quick-sort]: /images/20220403/2901874205b44481911b3127552d0f17.png
[Link 7]: https://www.cnblogs.com/chengxiao/p/6262208.html
[Link 8]: https://blog.csdn.net/qq_36528114/article/details/78667034
[Link 9]: https://www.cnblogs.com/chengxiao/category/880910.html
[Arrays.sort_Collections.sort]: https://blog.csdn.net/hellodake/article/details/82662602
[MySQL]: https://blog.csdn.net/hgl868/article/details/52759944
[MySQL order by_Filesort]: https://blog.csdn.net/lijingkuan/article/details/70341176
[MySQL 1]: http://www.cnblogs.com/cchust/p/5304594.html
[Link 10]: http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
[Link 11]: https://www.cnblogs.com/onepixel/articles/7674659.html
[Link 12]: http://www.cnblogs.com/jingmoxukong/p/4343770.html