SortAlgorithms

原文链接： 八大排序算法总结与java实现 - iTimeTraveler

概述

因为健忘，加上对各种排序算法理解不深刻，过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结，强行学习。首先罗列一下常见的十大排序算法：

• 直接插入排序
• 希尔排序
• 简单选择排序
• 堆排序
• 冒泡排序
• 快速排序
• 归并排序
• 基数排序

<!-- more -->

其中我们讨论的这八大排序算法的实现可以参考我的Github：SortAlgorithms，其中包括了排序测试模块[Test.java]和排序算法对比模块[Bench.java]，大家可以试运行。

它们都属于内部排序，也就是只考虑数据量较小仅需要使用内存的排序算法，他们之间关系如下：

一、直接插入排序（Insertion Sort）

---

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

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

1、基本思想

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

2、算法描述

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

①. 从第一个元素开始，该元素可以认为已经被排序</br> ②. 取出下一个元素，在已经排序的元素序列中从后向前扫描</br> ③. 如果该元素（已排序）大于新元素，将该元素移到下一位置</br> ④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</br> ⑤. 将新元素插入到该位置后</br> ⑥. 重复步骤②~⑤</br>

算法实现中比较有意思的一点是，在每次比较操作发现取出来的新元素小于等于已排序的元素时，可以将已排序的元素移到下一位置，然后将取出来的新元素插入该位置（即相邻位置对调），接着再与前面的已排序的元素进行比较，如上图所示，这样做缺点是交换操作代价比较大。另一种做法是：将新元素取出（挖坑），从左到右依次与已排序的元素比较，如果已排序的元素大于取出的新元素，那么将该元素移动到下一个位置（填坑），接着再与前面的已排序的元素比较，直到找到已排序的元素小于等于新元素的位置，这时再将新元素插入进去。就像基本思想中的动图演示的那样。

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

3、代码实现

/**
 * 插入排序
 *
 * 1. 从第一个元素开始，该元素可以认为已经被排序
 * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 5. 将新元素插入到该位置后
 * 6. 重复步骤2~5
 * @param arr  待排序数组
 */
public static void insertionSort(int[] arr){
    for( int i = 1; i < arr.length; i++ ) {
        int temp = arr[i];    // 取出下一个元素，在已经排序的元素序列中从后向前扫描
        for( int j = i; j >= 0; j-- ) {
            if( j > 0 && arr[j-1] > temp ) {
                arr[j] = arr[j-1];    // 如果该元素（已排序）大于取出的元素temp，将该元素移到下一位置
                System.out.println("Temping:  " + Arrays.toString(arr));
            } else {
                // 将新元素插入到该位置后
                arr[j] = temp;
                System.out.println("Sorting:  " + Arrays.toString(arr));
                break;
            }
        }
    }
}

// 交换次数较多的实现
public static void insertionSort(int[] arr){
    for( int i=0; i<arr.length-1; i++ ) {
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];      //交换操作
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            System.out.println("Sorting:  " + Arrays.toString(arr));
        }
    }
}

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

• 最好情况下，排序前对象已经按照要求的有序。比较次数(KCN)：n−1；移动次数(RMN)为0。则对应的时间复杂度为O(n)。
• 最坏情况下，排序前对象为要求的顺序的反序。第i趟时第i个对象必须与前面i个对象都做排序码比较，并且每做1次比较就要做1次数据移动（从上面给出的代码中看出）。比较次数(KCN)：n²/2 ; 移动次数(RMN)为：n²/2。则对应的时间复杂度为O(n²)。
• 如果排序记录是随机的，那么根据概率相同的原则，在平均情况下的排序码比较次数和对象移动次数约为n²/2，因此，直接插入排序的平均时间复杂度为O(n²)。

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

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

二、希尔排序（Shell Sort）

---

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

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

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

1、基本思想

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

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

2、算法描述

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

3、代码实现

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

/**
 * 希尔排序
 *
 * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
 * 2. 按增量序列个数k，对序列进行k 趟排序；
 * 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
 *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * @param arr  待排序数组
 */
public static void shellSort(int[] arr){
    int gap = arr.length / 2;
    for (; gap > 0; gap /= 2) {      //不断缩小gap，直到1为止
        for (int j = 0; (j+gap) < arr.length; j++){     //使用当前gap进行组内插入排序
            for(int k = 0; (k+gap)< arr.length; k += gap){
                if(arr[k] > arr[k+gap]) {
                    int temp = arr[k+gap];      //交换操作
                    arr[k+gap] = arr[k];
                    arr[k] = temp;
                    System.out.println("    Sorting:  " + Arrays.toString(arr));
                }
            }
        }
    }
}

下面是维基百科官方实现，大家注意gap步长取值部分：

/**
 * 希尔排序（Wiki官方版）
 *
 * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（注意此算法的gap取值）
 * 2. 按增量序列个数k，对序列进行k 趟排序；
 * 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
 *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * @param arr  待排序数组
 */
public static void shell_sort(int[] arr) {
    int gap = 1, i, j, len = arr.length;
    int temp;
    while (gap < len / 3)
        gap = gap * 3 + 1;      // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
    for (; gap > 0; gap /= 3) {
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
    }
}

以下是希尔排序复杂度:

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

三、选择排序（Selection Sort）

---

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

1、基本思想

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

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

2、算法描述

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

3、代码实现

选择排序比较简单，以下是我自己的实现，跟官方版差不多，所以完全可以参考。

/**
 * 选择排序
 *
 * 1. 从待排序序列中，找到关键字最小的元素；
 * 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
 * 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。
 *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * @param arr  待排序数组
 */
public static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length-1; i++){
        int min = i;
        for(int j = i+1; j < arr.length; j++){    //选出之后待排序中值最小的位置
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        if(min != i){
            int temp = arr[min];      //交换操作
            arr[min] = arr[i];
            arr[i] = temp;
            System.out.println("Sorting:  " + Arrays.toString(arr));
        }
    }
}

以下是选择排序复杂度:

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

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

四、堆排序（Heap Sort）

---

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

堆的定义如下：n个元素的序列{k1,k2,···,kn}，当且仅当满足下关系时，称之为堆。

ki <= k(2i)  且   ki <= k(2i+1) </br>

或：   ki >= k(2i) 且 ki >= k(2i+1) </br>

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

1、基本思想

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

2、算法描述

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

动图效果如下所示：

3、代码实现

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

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

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

对于堆节点的访问：

• 父节点i的左子节点在位置：(2*i+1);
• 父节点i的右子节点在位置：(2*i+2);
• 子节点i的父节点在位置：floor((i-1)/2);

/**
 * 堆排序
 *
 * 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
 * 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key
 * 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
 * @param arr  待排序数组
 */
public static void heapSort(int[] arr){
    for(int i = arr.length; i > 0; i--){
        max_heapify(arr, i);

        int temp = arr[0];      //堆顶元素(第一个元素)与Kn交换
        arr[0] = arr[i-1];
        arr[i-1] =