排序算法总结

一、概述

排序算法概念

在计算机科学与数学中，一个排序算法是将一组杂乱无章的数据按一定的规律顺次排列起来的算法。排序的目的是便于查找。

衡量排序算法好坏的三个重要依据

• 时间效率，即排序的速度，用时间复杂度来描述算法的运行时间。
• 空间效率，即占内存辅助空间的大小，用空间复杂度来描述算法占用额外空间的大小。
• 稳定性，若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。不稳定排序算法可能会在相等的键值中改变纪录的相对次序，在这个状况下，有可能产生不同的排序结果。

内部排序与外部排序

若待排序记录都在内存中，则称为内部排序。若待排序记录一部分在内存，一部分在外存，则称为外部排序。

按排序的规则不同，内部排序可分为5类：

• 插入排序（直接插入排序、折半插入排序、希尔排序），其基本思想是每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。

• 交换排序（冒泡排序、快速排序），其基本思想是两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。

• 选择排序（简单选择排序，堆排序），其基本思想是在待排序的序列中依次选择关键字最小（或最大）的元素作为有序序列的最后一个元素，直至全部记录选择完毕。

• 归并排序

• 基数排序

按排序算法的时间复杂度不同，内部排序可分为3类：

• 简单的排序算法：时间效率低，$O(n^2)$
• 先进的排序算法：时间效率高，$O(nlog_2n)$
• 基数排序算算法：时间效率高，$O(d \times n)$

二、常见排序算法

1、直接插入排序

基本思想

在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。

算法描述

设关键字数组为a[0…n-1]。

1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3. i++，并重复第二步直到 i==n-1，排序完成。

如待排序序列 T =（20，16，31，23，19，32，85，0），直接插入排序的中间过程为：

【20】，16，31，23，19，32，85，0

【16，20】，31，23，19，32，85，0

【16，20，31】，23，19，32，85，0

【16，20，23，31】，19，32，85，0

【16，19，20，23，31】，32，85，0

【16，19，20，23，31，32】，85，0

【16，19，20，23，31，32，85】，0

【0，16，19，20，23，31，32，85】

算法分析

• 若设待排序的对象个数为 n，则算法需要进行 n-1 次插入。

• 最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较 1 次，移动 2 次对象。因此，总的关键码比较次数为 n-1，对象移动次数为 2(n-1)。

• 最坏情况下，第 i 趟插入时，第 i 个对象必须与前面 i-1 个对象都做关键码比较，并且每做 1 次比较就要做 1 次数据移动。则总的关键码比较次数 CN 和对象移动次数 MN 分别为

CN = \sum_{i=1}^{n-1}i={n(n-1)}/2 \approx {n^2}/2

MN = \sum_{i=1}^{n-1}(i+2) = {(n+4)(n-1)}/2 \approx {n^2}/2

• 若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为 $n^2/4$。因此，直接插入排序的时间复杂度为 $O(n^2)$。

• 直接插入排序是一种稳定的排序方法。

算法实现

public static void InsertSort(int[] data) 
{
    int i, j;
    int count = data.Length;
    
    for (i = 1; i < count; i++) 
    {
        int t = data[i];
        for(j = i - 1; j >= 0 && data[j] > t; j--)
        {
            data[j + 1] = data[j];
        }
            
        data[j + 1] = t;
    }
}

2、折半插入排序

基本思想

在已形成的有序表中折半查找，并在适当位置插入，把原来位置上的元素向后顺移。

算法描述：

在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素大，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。

算法分析：

• 折半插入排序是直接插入排序的改进，比较的次数大大减少，全部元素比较次数仅为 $O(nlog_2n)$；

• 算法的平均时间复杂度为 $O(n^2)$，虽然比较次数大大减少，但移动次数并未减少；

• 在最好情况下，即待排记录序列已经是从小到大排好顺序时，其时间复杂度为 $O(n)$；

• 当待排记录基本有序或待排序序列的元素个数 n 很小时，算法的效率也比较高。

• 空间复杂度为 $O(1)$；

• 折半插入排序是一种稳定的排序方法。

算法实现：

public static void BinaryInsertSort(int[] data)
{
    for (int i = 1; i < data.Length; i++)
    {
        int low = 0;
        int high = i - 1;
        int tmp = data[i];

        while (low <= high)
        {
            int mid = (low + high) / 2;

            if (data[i] > data[mid])
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }

        for (int j = i; j > low; j--)
        {
            data[j] = data[j - 1];
        }

        data[low] = tmp;
    }
}

3、希尔排序

基本思想

希尔排序，又称缩小增量排序，是插入排序的一种更高效的改进版本。其基本思想是对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：将记录序列分成若干子序列，分别对每个子序列进行插入排序。

例如：将 n 个记录{R[1]…R[n]}分成 d 个子序列：

{ R[1]，R[1+d]，R[1+2d]，…，R[1+kd] }

{ R[2]，R[2+d]，R[2+2d]，…，R[2+kd] }

...

{ R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }

其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。

希尔排序示例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。

希尔排序的实现

取定步长序列，如dk=5,3,1。

对每一步长dk，重复执行如下过程：

把每一子序列第一个元素看成是有序的，对后面的每一个元素r[i]，重复执行如下过程：

把r[i]暂存在第0号单元；

寻找相应子序列中应该插入的位置：从后向前依次比较相应子序列中的元素，直到找到不大于r[i]的元素。

把r[i]放到适当的位置。

希尔排序算法分析

时间效率：
当增量序列为$d(k)=2^{t-k+1}-1$时，时间复杂度为$O(n^{1.5})$。

空间效率：$O(1)$

算法的稳定性： 不稳定

初始： (49，38，65，97, 76, 13, 27, 49*，55, 04）

结束： (04，13，27，38, 49*, 49, 55, 65，76, 97）

4、冒泡排序

基本思想

每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。

算法描述

待排序序列 T=(21，25，49，25*，16，08），冒泡排序的排序过程为：

初态： 21，25，49， 25*，16， 08

第1趟： 21，25，25*，16， 08 ， 49

第2趟： 21，25， 16， 08 ，25*，49

第3趟： 21，16， 08 ，25， 25*，49

第4趟： 16，08 ，21， 25， 25*，49

第5趟： 08，16， 21， 25， 25*，49

算法分析

• 每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

• 时间效率：$O(n^2)$ —因为要考虑最坏情况

• 空间效率：$O(1)$ ——只在交换时用到一个缓冲单元

• 冒泡排序是一种稳定的排序方法，25和25*在排序前后的次序未改变

• 最好情况下，即初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。

• 最坏情况下， 即初始排列逆序，算法要执行 n-1 趟起泡，第 i 趟(1<= i< n) 做了n- i 次关键码比较，执行了n-i 次对象交换。此时的比较总次数 CN 和记录移动次数 MN 为：

CN = \sum_{i=1}^{n-1}{(n-i)}={n(n-1)}/2

MN = 3\sum_{i=1}^{n-1}(n-i) = 3n{(n-1)}/2

算法实现

/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="data"></param>
public static void BubbleSort(int[] data)
{
    int temp = 0;
    bool swapped;

    for (int i = 0; i < data.Length; i++)
    {
        swapped = false;

        for (int j = 0; j < data.Length - 1 - i; j++)
        {
            if (data[j] > data[j + 1])
            {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;

                if (!swapped)
                {
                    swapped = true;
                }
            }
        }

        if (!swapped)
        {
            return;
        }
    }
}

5. 快速排序

基本思想

从待排序列中任取一个元素 (例如取中间值)作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。

算法分析

• 快速排序是一个不稳定的排序算法

• 最大递归调用层次数与递归树的深度一致，理想情况为 $log_2(n+1)$ ，要求存储开销为 $O(log_2n)$。

• 如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。

• 就平均计算时间而言，快速排序是我们所讨论的所有内部排序方法中最好的一个。因为每趟可以确定的数据元素是呈指数增加的！
  设每个子表的支点都在中间（比较均衡），则：
  第1趟比较，可以确定1个元素的位置；
  第2趟比较（2个子表），可以再确定2个元素的位置；
  第3趟比较（4个子表），可以再确定4个元素的位置；
  第4趟比较（8个子表），可以再确定8个元素的位置；
  ……
  只需 $log_2n+1$ 趟便可排好序。而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。快速排序的平均排序效率为 $O(nlog_2n)$；

• 在最坏的情况，排序效率仍为$O(n^2)$。即待排序对象序列已经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过 (n-1) 趟才能把所有对象定位，而且第 i 趟需要经过 (n-i) 次关键码比较才能找到第 i 个对象的安放位置，总的关键码比较次数将达到 $n^2/2$ 。

代码实现

• 每一趟的子表的形成是采用从两头向中间交替式逼近法；
• 由于每趟中对各子表的操作都相似，主程序可采用递归算法。

以数组 data = {16, 20, 19, 20*, 11, 3} 作为示例，取子表中间元素作为基准。初始时数组如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 16 | 20 | 19 | 20* | 11 | 3

此时，i = 0, j = 5, middle = data[(i + j) / 2] = 19, 将中间元素与第一个元素交换，数组变为：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 19 | 20 | 16 | 20* | 11 | 3

采用从两头向中间交替式逼近法，首先，从索引 j 开始向前寻找一个小于等于 middle 的数，当 j = 5 时，符合条件，将 j=5 的值赋到索引 i 的值，i 做累加操作（即 data[0]=data[5]; i++），数组如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 20 | 16 | 20* | 11 | 3

然后，再从索引 i （此时 i=1 ）开始向后寻找一个大于等于 middle 的数，当 i = 1 时，符合条件，将索引 i=1 的值赋给索引 j 的值上，j 做累减操作（即 data[5]=data[1]; j--;），此时数组为

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 20 | 16 | 20* | 11 | 20

这时又从索引 j （此时 j=4）开始向前寻找一个小于等于 middle 的数，当 j=4 时，符合条件，将 j=4 的值赋到索引 i 的值，i 做累加操作（即 data[1]=data[4]; i++），数组如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 11 | 16 | 20* | 11 | 20

此时 i=2, j=4, 又从索引 i 开始向后寻找一个大于等于 middle 的数，当 i=3 时，符合条件，将索引 i=3 的值赋到索引 j(j=4) 的值上，j 做累减操作（即 data[4]=data[3]; j--;），此时数组为

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 11 | 16 | 20* | 20* | 20

此时 i=3，j=3，即 i=j，刚将 middle 的值赋到索引为 3 的值上，数组变为

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
value | 3 | 11 | 16 | 19 | 20* | 20

至此，排序第一趟结束，排序后的结果如下：

index | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---|---
初态 | 16 | 20 | 19 | 20* | 11 | 3
第一趟 | 3 | 11 | 16 | 19 | 20* | 20

可以看出第一趟排序后，data[3] 前面的数字都小于它，a[3] 后面的数字都大于它。再对各子表（a[0,1,2]和a[4,5]这二个子表）重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个，此时便为有序序列了。

C#代码

/// <summary>
/// 快速排序
/// </summary>
/// <param name="data"></param>
public static void QuickSort(int[] data)
{
    QuickSort(data, 0, data.Length - 1);
}

/// <summary>
/// 快速排序，递归方式（采用从两头向中间交替式逼近法）
/// </summary>
/// <param name="data"></param>
/// <param name="left"></param>
/// <param name="right"></param>
private static void QuickSort(int[] data, int left, int right)
{
    if (left < right)
    {
        int midIndex = (left + right)/2;

        // 取中间元素作为基准
        int middle = data[midIndex];

        // 将中间元素与第一个元素交换
        int tmp = data[left];
        data[left] = data[midIndex];
        data[midIndex] = tmp;
        
        int i = left;
        int j = right;

        while (i < j)
        {
            while (data[j] >= middle && i < j)
            {
                j--;
            }

            if (i < j)
            {
                data[i++] = data[j];
            }

            while (data[i] < middle && i < j)
            {
                i++;
            }

            if (i < j)
            {
                data[j--] = data[i];
            }
        }

        data[i] = middle;

        QuickSort(data, left, i - 1);
        QuickSort(data, i + 1, right);
    }
}

6. 选择排序

基本思想

在待排序的序列中依次选择关键字最小（或最大）的元素作为有序序列的最后一个元素，直至全部记录选择完毕。

如待排序的序列 data = [47 38 25 17 16 12 25* 20 49]，使用简单选择排序（选择关键字最小的元素），其过程如下：

[47 38 25 17 16 12 25* 20 49]

12 [38 25 17 16 47 25* 20 49]

12 16 [25 17 38 47 25* 20 49]

12 16 17 [25 38 47 25* 20 49]

12 16 17 20 [38 47 25* 25 49]

12 16 17 20 25* [47 38 25 49]

12 16 17 20 25* 25 [38 47 49]

12 16 17 20 25* 25 38 [47 49]

12 16 17 20 25* 25 38 47 [49]

12 16 17 20 25* 25 38 47 49

12[47 38 25 17 16 12 20 49]
13[38 65 97 76 49 27 49]
13 27[65 97 76 49 38 49]
13 27 38[65 97 76 49 49]
13 27 38 49[65 97 76 49]
13 27 38 49 49[65 97 76]
13 27 38 49 49 65[97 76]
13 27 38 49 49 65 76 97

特点：

1. 算法简单, 时间复杂度为O(n2)
2. 序列存储：顺序、链式
3. 稳定

/// <summary>
/// 简单选择排序
/// </summary>
/// <param name="data"></param>
public static void SelectionSort(int[] data)
{
    for (int i = 0; i < data.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < data.Length; j++)
        {
            if (data[min] > data[j])
            {
                min = j;
            }
        }

        if (min != i)
        {
            int tmp = data[min];
            data[min] = data[i];
            data[i] = tmp;
        }
    }
}

7. 堆排序

若有n个元素(a1，a2，a3，…，an)，当满足如下条件：
ai≤a2i ai≥a2i
（1） ai≤a2i+1 或 (2) ai≥a2i+1

其中i=1,2,…,n/2，则称此n个元素a1，a2，a3，…，an为一个堆。

若将此元素序列按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。

堆节点的访问[编辑]
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
父节点i的左子节点在位置(2i+1);
父节点i的右子节点在位置(2i+2);
子节点i的父节点在位置floor((i-1)/2);
堆的操作[编辑]
在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

原地堆排序[编辑]
基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是：
创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
重复步骤2，直到堆的尺寸为1
平均复杂度[编辑]
堆排序的平均时间复杂度为 {\displaystyle O(n\mathrm {log} n)} O(n\mathrm{log}n)，空间复杂度为 {\displaystyle \Theta (1)} \Theta(1)。

96 50 85 45 17 31 63 24 17

8.归并排序

归并排序指的是将两个或两个以上的有序序列组合成一个新的有序序列操作。

2-路归并排序

设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。

两两合并，得到n/2个长度为2或1的有序子序列。

再两两合并，……如此重复，直至得到一个长度为n的有序序列为止。

时间复杂度：
T(n)=O(nlogn)

空间复杂度：
S(n)=O(n)

它是一个稳定的排序方法。

迭代法[编辑]

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

递归法[编辑]

原理如下（假设序列共有n个元素）：
将序列每相邻两个数字进行归并操作，形成 {\displaystyle floor(n/2)} floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成 {\displaystyle floor(n/4)} floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕

三、总结