经典排序算法总结

排序算法总结

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的相对顺序就发生了改变,违反了稳定性的定义,故不稳定;

朴素的直接选择排序是不稳定的，这毫无疑问。当然可以写成稳定的版本。
稳定的排序：直接插入排序、冒泡排序、归并排序
不稳定的排序：希尔排序、直接选择排序、堆排序、快速排序

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

• 简单插入排序(Insertion Sort)

从第一个数字开始排序，每次让前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)

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

排序细节:

原始数字: 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

### 伪代码
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)

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

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.详解十一种排序算法

[2] 百度经验: 希尔排序

[3] 图解排序算法(二)之希尔排序

[4] 数据结构基础 希尔排序 之 算法复杂度浅析

[5] 希尔排序&选择排序&时间复杂度分析

[6] 希尔排序 时间复杂度 证明

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

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

分冶

归并

# 伪代码
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] 图解排序算法(四)之归并排序
[2] 《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)\]

#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)

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

#伪代码
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] 图解排序算法(五)之快速排序——三数取中法
[2] 快速排序(三种算法实现和非递归实现)

Others

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

[2] 图解排序算法

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

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

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

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

[7] [经典排序算法][集锦]

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

[9] 字符串 模式匹配