常规排序算法总结

概述

因为健忘，加上对各种排序算法理解不深刻，过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结，强行学习。首先罗列一下常见的六大排序算法和Java实现（参考维基百科)。

一、选择排序（Selection Sort）

---

从算法逻辑上看，选择排序是一种简单直观的排序算法，在简单选择排序过程中，所需移动记录的次数比较少。

1、基本思想

选择排序的基本思想：比较 + 交换。

在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

2、算法描述

①. 从待排序序列中，找到关键字最小的元素；
②. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
③. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。

3、代码实现

    public static <T extends Comparable<? super T>> void SelectionSort(T[] array){
        int n=array.length;
        for(int i=0;i<n; i++)
        {
            int min=i;
            //从第i+1个元素开始，找最小值
            for(int j=i+1;j<n; j++)
            {
                if(array[min].compareTo(array[j])>0) {
                    min = j;
                }
            }
            //找到之后和第i个元素交换
            if(min!=i) {
                Swap(array, i, min);
            }
        }
    }

以下是选择排序复杂度:

平均时间复杂度   最好情况   最坏情况  空间复杂度
 O(n²)        O(n²)     O(n²)      O(1)

选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。

二、插入排序（Insertion Sort）

---

插入排序的设计初衷是往有序的数组中快速插入一个新的元素。它的算法思想是：把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.

插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序 , 希尔排序 。我们先来看下直接插入排序。

1、基本思想

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

2、算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

①. 从第一个元素开始，该元素可以认为已经被排序

②. 取出下一个元素，在已经排序的元素序列中从后向前扫描

③. 如果该元素（已排序）大于新元素，将该元素移到下一位置

④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤. 将新元素插入到该位置后

⑥. 重复步骤②~⑤

如果比较操作的代价比交换操作大的话，可以采用[二分查找法]来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为[二分查找插入排序]

3、代码实现

        public static <T extends Comparable<? super T>> void InsertionSort2(T[] array){
            int i=0, j=0;
            int n = array.length;
            T key ;
            for (i=1; i<n; i++){
                key = array[i];
                for (j=i-1; j>=0; j--){
                    if(key.compareTo(array[j])<0){
                        array[j+1] = array[j];
                    }else{
                        break;
                    }
                }
                //找到之后和第i个元素交换
                array[j+1] = key;
            }
        }

直接插入排序复杂度如下：

平均时间复杂度   最好情况   最坏情况  空间复杂度
 O(n²)        O(n)     O(n²)      O(1)

Tips: 由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。

三、希尔排序（Shell Sort）

---

第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。

希尔排序，也称递减增量排序算法，1959年Shell发明。是插入排序的一种高速而稳定的改进版本。

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

1、基本思想

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

image.png

可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。更好的步长序列取值可以参考[维基百科]

2、算法描述

①. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
②. 按增量序列个数k，对序列进行k 趟排序；
③. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

3、代码实现

以下是我自己的实现，可以看到实现很幼稚，但是好处是理解起来很简单。因为没有经过任何的优化，所以不建议大家直接使用。建议对比下方的维基百科官方实现代码，特别是步长取值策略部分。

public static <T extends Comparable<? super T>> void ShellSort(T[] array)
{
    int n = array.length;
    int h = 1;
    //初始最大步长
    while (h < n/3) h = h * 3 + 1;
    while (h >= 1)
    {
        //从第二个元素开始
        for (int i = 1; i < n; i++)
        {
            //从第i个元素开始，依次次和前面已经排好序的i-h个元素比较，如果小于，则交换
            for (int j = i; j >= h; j = j - h)
            {
                if (array[j].compareTo(array[j - h]) < 0)
                {
                    Swap(array, j, j - h);
                }
                else //如果大于，则不用继续往前比较了，因为前面的元素已经排好序，比较大的大就是教大的了。
                    break;
            }
        }
        //步长除3递减
        h = h / 3;
    }
}

以下是希尔排序复杂度:
平均时间复杂度     最好情况     最坏情况      空间复杂度
  O(n log2 n)     O(n log2 n)     O(n log2 n）      O(1)

七、归并排序（Merging Sort）

---

image

归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

1、基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

2、算法描述

归并排序可通过两种方式实现：

• 自上而下的递归
• 自下而上的迭代

一、递归法（假设序列共有n个元素）：

①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③. 重复步骤②，直到所有元素排序完毕。

image

二、迭代法

①. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
②. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
③. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
④. 重复步骤③直到某一指针到达序列尾
⑤. 将另一序列剩下的所有元素直接复制到合并序列尾

3、代码实现

归并排序其实要做两件事：

• 分解：将序列每次折半拆分
• 合并：将划分后的序列段两两排序合并

因此，归并排序实际上就是两个操作，拆分+合并

如何合并？

L[first…mid]为第一段，L[mid+1…last]为第二段，并且两端已经有序，现在我们要将两端合成达到L[first…last]并且也有序。

首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]
重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]
此时将temp[]中的元素复制给L[]，则得到的L[first…last]有序

如何分解？

在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列
分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。

这里我写了递归算法如下：

   public static <T extends Comparable<? super  T>> void MergeSort(T[] array, int p, int r){
        if(p<r) {
            int q = (p + r) / 2;
            MergeSort(array, p, q);
            MergeSort(array,q+1, r);
            Merge(array,p,q,r);
        }
    }
    ///合并操作
    public static <T extends Comparable<? super T>> void Merge(T[] array, int p, int q, int r){
        int i=0, j=0, k=0 ;
        int n1 = q - p + 1;
        int n2 = r - q;
        ArrayList<T> leftArray  = new ArrayList<T>();
        ArrayList<T> rightArray = new ArrayList<T>();
        for(i=0; i<n1; i++){
            leftArray.add(i, array[p+i]);
        }
        leftArray.add(n1,null);
        for(j=0; j<n2; j++){
            rightArray.add(j, array[q+j+1]);
        }
        rightArray.add(n2,null);

        //合并左右两个子数组
        T litem, ritem;
        for(i=0,j=0,k=p; k<=r; k++){
            litem = leftArray.get(i);
            ritem = rightArray.get(j);
            if(litem!=null ){
                if(ritem!=null){
                    if(litem.compareTo(ritem)<=0){
                        array[k] = litem;
                        i++;
                    }else{
                        array[k] = ritem;
                        j++;
                    }
                }else{
                    array[k] = litem;
                    i++;
                }
            }else{
                if(ritem!=null) {
                    array[k] = ritem;
                    j++;
                }
            }
        }
    }

以下是归并排序算法复杂度:
平均时间复杂度     最好情况     最坏情况      空间复杂度
  O(nlog₂n)       O(nlog₂n)     O(nlog₂n)      O(n)

从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

四、堆排序（Heap Sort）

---

1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同发明了著名的堆排序算法(Heap Sort).

把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。

1、基本思想

此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

2、算法描述

①. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
②. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key
③. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.

堆排序算法的演示。首先，将元素进行重排，以匹配堆的条件。图中排序过程之前简单的绘出了堆树的结构。 堆排序算法的演示。首先，将元素进行重排，以匹配堆的条件。图中排序过程之前简单的绘出了堆树的结构。

3、代码实现

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。

总结起来就是定义了以下几种操作：

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

    public static <T extends Comparable<? super T>> void HeapSort(T[] array){
        //1.构建大顶堆
        for(int i = array.length/2-1; i>=0; i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            AdjustMaxHeap(array, i, array.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=array.length-1;j>0;j--){
            Swap(array,0,j);//将堆顶元素与末尾元素进行交换
            AdjustMaxHeap(array,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param array
     * @param i
     * @param length
     */
    public static <T extends Comparable<? super T>> void AdjustMaxHeap(T[]array, int i, int length){
        T temp = array[i];//先取出当前元素i
        for(int k=i*2+1; k<length; k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && array[k].compareTo(array[k+1])<0 ){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if( array[k].compareTo(temp)>0 ){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                array[i] = array[k];
                i = k;
            }else{
                break;
            }
        }
        //将temp值放到最终的位置
        array[i] = temp;
    }

以下是堆排序算法复杂度:
平均时间复杂度     最好情况     最坏情况      空间复杂度
  O(nlog₂n)       O(nlog₂n)     O(nlog₂n)      O(1)

Tips: 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.

六、快速排序（Quick Sort）

---

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

1、基本思想

快速排序的基本思想：挖坑填数+分治法。

首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

使用快速排序法对一列数字进行排序的过程 使用快速排序法对一列数字进行排序的过程

2、算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

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

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

快速排序演示 快速排序演示

3、代码实现

用伪代码描述如下：
①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中

[![快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分区版本。]

    public static <T extends Comparable<? super T>> void QuickSort(T[] array, int p, int r){
        if(p<r){
            int q = Partition(array,p,r);
            QuickSort(array, p, q-1);
            QuickSort(array,q+1,r);
        }
    }

    ///划分
    public static <T extends Comparable<? super T>> int Partition(T[] array, int p, int r){
        int q = r ;
        T paviot = array[r];
        for(int  i=r-1; i>=p; i--){
            if (array[i].compareTo(paviot) > 0){
                array[q--] = array[i];
                array[i] = array[q];
            }
        }
        array[q] = paviot;
        return q;
    }

快速排序是通常被认为在同数量级（O(nlog₂n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

以下是快速排序算法复杂度:
平均时间复杂度     最好情况     最坏情况     空间复杂度
  O(nlog₂n)       O(nlog₂n)     O(n²)      O(1)（原地分区递归版）

快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.

Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.

总结

---

各种排序性能对比如下，有些排序未详细介绍，暂且放到这里。实例测试结果可以看这里：[六大排序算法耗时对比]

排序类型	平均情况	最好情况	最坏情况	辅助空间	稳定性
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n^1.3)	O(nlogn)	O(n²)	O(1)	不稳定
归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
快速排序	O(nlog₂n)	O(nlog₂n)	O(n²)	O(nlog₂n)	不稳定

从时间复杂度来说：

(1). 平方阶O(n²)排序：**各类简单排序：直接插入、直接选择

(2). 线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；

(3). O(n1+§))排序，§是介于0和1之间的常数：希尔排序

说明

• 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
• 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

• 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

  
  image.png