前言

排序是数据结构中非常常见的问题，也是必须要掌握的算法之一。接下来我们先从排序的基本概念开始介绍排序算法。

本文排序均以从小到大的升序排序为例。

排序基本概念

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列，老师查看上课出勤情况时，会按学生学号顺序点名等等。

我们一般把排序分为内部排序和外部排序。内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这一章一般说的都是内部排序。

内部排序，我们根据各种排序方法的特点又可以分为：比较排序——通过对数组中的元素进行比较来实现排序；非比较排序——通过确定每个元素之前，应该有多少个元素来排序。

我们有很多种排序，我们衡量它们之间的优劣，一般从算法的时间、空间复杂度，代码难易程度、排序效率和稳定性有关。

稳定性，即假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。反之则是不稳定的排序。例如：

在(a)中，green、yellow、blue它们对应的编号相同，分别位置设为i,j,k，此时初始时i<j<k；在稳定的排序中，即(b)中，它们仍满足i<j<k；而在不稳定的排序中k<i<j，没有保持原本的顺序，故为不稳定。

稳定性是衡量结果是否会不一样的标准，因为有时同样的数据会有不一样的含义，如上述例子，它们代表的颜色不一样。并且对于复杂的类型，稳定的排序还可以减少交换次数。

接下来我们一个个分析各种常见排序算法。

比较排序

对于比较排序，我们还可以细分出：插入法排序、选择法排序、交换法排序和分治法排序，接下来我们一个个来看他们的特点。

插入法排序

插入排序（Insertion Sort）

最简单的排序算法之一是插入排序(insertion sort)。这个算法理解起来非常简单，因为这个过程就是我们平时玩扑克牌中熟知的排序方法——找到比拿到的手牌大的最小的牌，把拿到的手牌插入到序列中指定位置的方法。

我们换个说法，插入排序的基本操作是将一个记录插入到巳经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

它的过程非常好理解，我们通过一个动图来演示：

由图所示，它的实现步骤：

  • 从第一个元素开始，认为该元素为初始有序序列中的元素；
  • 取出下一个元素，并把它存储起来，在有序序列中从后向前扫描；
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置，直到找到已排序的元素小于或者等于新元素的位置；
  • 将新元素插入到该位置后；
  • 把新元素和原有序序列形成的新有序序列作为初始有序序列，继续下次同样的操作。

故我们的代码：

void InsertSort(ElementType *A, int n)
{
    for(int i=1;i<n;i++) 
    { 
      int tmp=A[i]; //取出下一位元素，前0~i-1位为有序 
      int j; 
      for(j=i;j > 0 && A[j-1] > tmp;j--)    //比较前一位与取出的这一位的大小
         A[j] = A[j-1];
      A[j] = tmp;    //找到了比取出的这一位小的(第j-1位)，插入到它的后面(第j位)
    }
}

在评价插入排序时，对于其空间复杂度，很明显我们申明的是2个变量空间，故它只需要一个记录的辅助空间，此时空间复杂度是O(1)。

时间复杂度上，我们观察可知存在两个for循环，一般来说就是O(N2)的复杂度。当其本身全为有序的情况下，一共只需要比较N-1次，此时时间复杂度为O(N)；最坏的情况，即为逆序时，每次都需要比较N-1次，一共有N-1个需要比较，此时时间复杂度为O(N2)。

关于稳定性上，插入排序面对相同元素时会一视同仁，即只会在它们前面或它们后面，或跳过它们，不会改变它们原本的顺序，新插入的也会因为比较而在之前插入的之后，故插入排序是稳定的。

希尔排序（Shell Sort）

少量的插入操作（总数少或是基本有序）就可以完成整个序列的排序工作的情况下，插入排序是很高效的，可以达到O(N)。

所以我们对于一个序列，我们将其分成若干个子序列分别进行插入排序，这样的做法可以使各个子序列的总数变少，此时的插入排序是高效的。

例如我们有一个待排序的序列：{9,1,5,8,3,7,4,6,2}。现在将它分成三组， ｛9,1,5}, {8,3,7}, {4,6,2}

接下来我们将它们各自使用插入排序，得到：{1,5,9}, {3,7,8}, {2,4,6}，并把它们合成在一起为{1,5,9,3,7,8,2,4,6}。

此时，这个序列还是杂乱无序的，至少要到达：小的关键字基本在前面，大的基本在后面，不大不小
的基本在中间的情况才能说为基本有序。故这样的划分也不能做到很有效，我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。

因此我们只能采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序。

我们可以参考下面的图片知晓其过程。图源

看图我们知道，每一次我们通过gap的值来得到分组的数量，经过对划分的组进行插入排序，最后当gap等于1的时候就可以得到一个基本有序的序列了，我们再对全局进行一次插入排序就可以得到有序序列了。

代码为：

void ShellSort(ElementType *A, int n)
{
    for(int increment=n/2; increment > 0; increment/=2)
    {
        for(int i=increment; i<n ;i++) //隔increment个位置进行插入排序
        {
          int tmp = A[i];
          int j;
          for(j=i;j>increment-1 && A[j-increment]>tmp; j-=increment)
            A[j]=A[j-increment];
          A[j] = tmp;
        }
    }
}

我们从代码可以看出，每次我们只对隔着increment的元素进行排序。分析希尔排序则比较麻烦。

关于空间复杂度，和插入排序一样的是O(1)。

时间复杂度上，我们知道希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。故它的时间复杂度和我们选取的增量有关，根据大量的研究表明，一般选取增量为2t-k+1-1时，其时间复杂度为O(n3/2)。

最差的情况下，其时间复杂度也可以达到Θ(n2)，平均时间复杂度根据大量的计算一般认为是O(nlogn)。

对于稳定性，希尔排序在分组时两个相同元素可能不在同一个组内，造成排序后可能导致其位置改变，故其为不稳定的排序。

选择法排序

选择排序（Selection Sort）

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想就是，每一趟在n-i+1(i=1,2,...,n-1) 个元素中选取关键字最小的元素作为有序序列的第 i 个元素。

我们直接看图就很容易理解这个简单的算法：

这是个非常直观的算法，我们直接来看代码就好了。

void SelectSort(ElementType *A, int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min = i;    //将当前下标定义为最小值下标
        for(int j=i+1;j<n;j++)    //找到剩下的元素中最小的
        {
            if(A[j] < A[min])
                min=j;
        }
        int tmp=A[i];    //交换最小的值与开头的值
        A[i]=A[min];
        A[min]=tmp;
    }
}

对于选择排序，我们同样用到了一个min变量去存储最小值的下标，空间复杂度为O(1)。

对于时间复杂度也比较明显，我们可以看到存在两个for循环，它们最多都是n-1和n-2次，故时间复杂度为O(n2)。

稳定性上，因为找最小值的时候同样的元素时最小时最左边的会被先选上交换，下次再选到会到先选上的后边，它们顺序不会因此改变，故选择排序是稳定的。

选择排序是一个非常简单的排序，也是我们在不要求时间复杂度下最经常使用的排序算法之一。

堆排序（Heap Sort）

堆排序在堆那一章已经涉及到了，这里就简单的复习一下。

【数据结构】堆、优先队列和堆排序

我们之前说的选择排序是在待排序的n个记录中选择一个最小的元素需要比较n-1次。而堆排序就是对选择排序的改进，因为堆的性质——最小堆的根是堆中最小的元素，最大堆的根是堆中最小的元素。

因为我们用从小到大的升序举例，故此时应该使用最大堆进行排序，动图如下：

当然我们为了节省空间复杂度每次删除最大元出来的是局部最大值，我们就可以把它放在数组的尾部。

此时的代码因为不需要堆的其他内容，我们就写得简洁一点：

void HeapSort(ElementType *A, int n)
{
    A=BuildHeap(A,n);
    for(int i=0,j=n;i<n;i++,j--)
    {
        A[n-i]=DeleteMax(A,j);
    }
}

其他关于堆的操作，具体解释可以看堆那一章：

int* BuildHeap(int *A, int n)
{
    int *B=(int *)malloc(sizeof(int) * (n+1));
    B[0]=32767;
    for(int i=0;i<n;i++) 
    { 
        HeapInsert(A[i],B,i+1); 
    } 
    return B; 
} 
void HeapInsert(int x, int *B, int n) 
{ 
    for(int i=n;i>=1;i/=2)
    {
        if(x > B[i/2])
        {
            B[i] = B[i/2];
        }
        else
        {
            B[i] = x;
            break;
        }
    }
}

int DeleteMax(int *B, int n)
{
    int MaxElement=B[1];
    int LastElement=B[n];
    int i;
    for(i=1;i*2 <=n;) 
    { 
        if((LastElement >= B[i*2+1] && LastElement >= B[i*2]))
        {
            B[i]=LastElement;
            break;
        }
        else if(B[i*2] >= B[i*2+1] && B[i*2] >= LastElement)
        {
            B[i]=B[i*2];
            i*=2;
            if(i <= n && i*2>n)
            {
                B[i]=LastElement;
                break;
            }
            
        }
        else if(B[i*2+1] > B[i*2] && B[i*2+1] > LastElement)
        {
            B[i]=B[i*2+1];
            i=i*2+1;
            if(i <= n && i*2>n )
            {
                B[i]=LastElement;
                break;
            }
            
        }
    }
    if(i/2 <= n && i>n)
    {
        B[i/2]=LastElement;
    }
    return MaxElement;
}

对于堆排序，空间复杂度为O(1)，仅需一个记录大小供交换用的辅助存储空间。

对于时间复杂度，它因为向上冒泡和向下渗透的过程均是树的高度的次数，即logn，对于n位数的取最大操作，它的时间复杂度为O(nlogn)。

对于稳定性，很明显在取出后位于原本后面的元素到了前面去，它是不稳定的排序。

交换法排序

冒泡排序（Bubble Sort）

冒泡排序是思路最简单，最容易理解的排序方法之一。它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

void BubbleSort(ElementType *A, int n)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++) 
        { 
            if(A[i] > A[j])
            {
                int tmp=A[i];
                A[i]=A[j];
                A[j]=tmp;
            }
        }
    }
}

如果说要优化的话，假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，此时已经是有序的了。我们可以设置一个flag标记是否发生交换，这个太简单就不写了。

很明显，它的空间复杂度是O(1)，时间复杂度为O(N2)，是个稳定的算法。

快速排序（Quick Sort）

这一篇以前有提及：

【C/C++学习笔记】qsort、队列ADT以及位操作

我们可以把数组抽象成一颗树来理解，设置一个基准值pivot为根，所有元素比基准值小的摆放在基准左侧，所有元素比基准值大的摆在基准的右侧。再通过递归把小于基准值元素的子数列和大于基准值元素的子数列排序。

它的过程如下：

代码：

void QuickSort(int *arr, int l, int r)
{
    int first = l;    //最左边数组下标
    int last = r;    //最右边数组下标
    int pivot = first;    //用于比较的标量（选取最左边第一个元素）
    if (first >= last)    //如果只有一个元素，first==last；以及first>last的情况
    {
        return;
    }
    while (first < last)
    {
        while (first < last && arr[last] >= arr[pivot])//右边找比标量小的数
        {
            last--;
        }
        while (first < last && arr[first] <= arr[pivot])    //左边找比标量大的数
        { 
            first++;
        }
        if(first < last)//分析交换找出来的值
        swap(&arr[first], &arr[last]);
    }
    if (first == last)
    {
        swap(&arr[pivot], &arr[last]);    //交换pivot到它应该到的位置上，重新选取标量
    }
    Quicksort(arr,l,first-1);    //左边递归排序
    Quicksort(arr,first+1,r);    //右边递归排序
}

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

我们选取了左边第一个数据为pivot，那么应该先从右边开始比较，从右边第一个数据开始与pivot进行比较，如果比它大则继续向左比较(last--)，直到找到比pivot小的数据，便停下来。

右边的比较暂时结束了，此刻开始从左边开始与pivot比较，如果比pivot小则继续向右比较(first++)，如果比pivot大则也停下来。

我们比较first对应的元素与last此时对应的元素，如果first < last，左边找到的比pivot大的数与右边找到的比pivot小的数进行交换。

关于空间复杂度，很明显是O(1)。

关于时间复杂度，因为可以抽象为树的模型，故平均时间复杂度为O(nlogn)。

关于稳定性，它是不稳定的排序，因为和pivot相等的可以在任意一组，可能会改变顺序。

分治法排序

归并排序（Merge Sort）

前面我们讲了堆排序，因为它用到了完全二叉树，充分利用了完全二叉树的深度是logn+1 的特性，所以效率比较高。但堆的结构较为复杂，有没有什么比较简单应用二叉树的排序呢。故引入了归并排序。

它的原理：假如初始序列含有 n 个记录，则可以看成是 n 个有序的子序列，每个子序列的长度为 1。然后两两归并，得到 n/2 个长度为2或1的有序子序列；再两两归并，……，如此重复，直到得到一个长度为 n 的有序序列为止，这种排序方法称为 二路归并排序，下文介绍的也是这种排序方式。

它采用了分治法的思想，因此就可以知道它的做法可以用自上而下的递归和自下而上的迭代来实现。

归并的含义是将两个有序表组合成一个新的有序表，我们通过两个图片（图源）来看它的过程。

首先是我们把它从中间分开：

然后再归并：

我们来看代码：

void Mergesort( ElementType *A, int n )
{
    ElementType *TmpArray = (ElementType *)malloc(n * sizeof(ElementType));
    if(TmpArray != NULL )    //TmpArray为存储合并后的临时空间
    {
        MSort(A, TmpArray, 0, n - 1 );
        free(TmpArray);
    }
    else 
    {
        printf("No Space!\n");
        exit(-1);
    }
}

首先这一段代码中，我们申请了空间，用来存放合并后的序列；接下来是分治的过程：

void MSort(ElementType *A, ElementType *TmpArray, int Left, int Right)
{
    if(Left > Right)
    {
        int Center = ( Left + Right ) / 2;
        MSort( A, TmpArray, Left, Center );
        MSort( A, TmpArray, Center + 1, Right );
        Merge( A, TmpArray, Left, Center + 1, Right );
    }
}

我们将数组递归地从中间分开，接下来就是将它们归并起来，归并的时候会调整它们的顺序：

void Merge(ElementType *A, ElementType *TmpArray, int L, int M, int R)
{
    int i=L;    //第一个数组的左端
    int j=M;    //第二个数组的左端
    int count=0;    //记录TmpArray的下标
    for(int k=L;k<=R;k++) 
    { 
        if(i > M-1)    //第一个数组的数已经合并完毕，此时只剩下第二个数组的剩余元素
        {
            TmpArray[count++] = A[j];
            j++;
        }
        else if(j > R)    //第二个数组的数已经合并完毕，此时只剩下第一个数组的剩余元素
        {
            TmpArray[count++] = A[i];
            i++;
        }
        else if(A[i] < A[j])    //第一个数组的i位元素比第二个数组的j元素，把它并入 
        { 
            TmpArray[count++] = A[i]; 
            i++; 
        } 
        else    //否则并入第二个数组的那位元素 
        { 
            TmpArray[count++] = A[j]; 
            j++; 
        } 
    }
    for(int k=count-1;k>=0;k--)    //替换原数据
    {
        A[L+k] = TmpArray[k];
    }
}

在循环中，前面两个if是在判断边界，如果有一方的数组已经合并完了，剩余的直接插入即可，无须比较。因为我们这样的排序保证了，两个子数组都是有序的，这样才能对位比较，不然需要讨论的情况就比较麻烦。建议画图模拟一下这个过程就可以知道了。

对于空间复杂度，因为我们定义了一个TmpArray去存临时数据，所以空间复杂度为O(n)。

对于时间复杂度，我们这样分而治之的思想，抽象为树的过程，时间复杂度为O(nlogn)。

因为在1个或2个元素时，1个元素不会交换，2个元素如果大小相等，没有外部干扰，将不会破坏稳定性，故归并排序是稳定的排序。

非比较排序

非比较排序，即排序是不需要比较就可以来排序的。区别于比较排序，非比较排序利用额外的内存空间实现更快排序，算法以线性时间运行。

我们常见的非比较排序是计数排序、桶排序和基数排序，它们都是通过一定的规律来排序数据，接下来我们一个个来看它们是如何实现的。

分布法排序

计数排序（Counting Sort）

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序。
此时我们需要知道这组数据的范围，因为在存储数组中我们只存它的值，当然要需要根据它的范围来定义空间。随后在相应位置处的计数数组记录着值的次数。

这样的过程就是计数排序的核心了，我们再通过一个动图来了解：

故代码为：

void CountingSort(ElementType *A, int n)
{
    int min=32767;
    int max=-32767;
    for(int i=0;i<n;i++)
    {
        if(A[i] < min) 
            min=A[i]; 
        if(A[i] > max)
            max=A[i];
    }
    int d=max-min+1;
    ElementType *c=(ElementType *)malloc(sizeof(ElementType) * d);
    for(int i=0;i<n;i++)
    {
        /* 用A[i]-min作为统计数组的下标 */
        c[A[i]-min]++;
    }
    int count=0;
    for(int i=0;i<d;i++)
    {
        for(int j=0;j<c[i];j++)
        {
            /* 输出计数次数 */
            A[count++]=i+min;
        }
    }
}

我们这里使用了A[i]-min作为数据存储，可以少创建了一个数组。

很显然的，计数排序是用空间换了时间，它的空间复杂度达到O(n+k)，其中k为整数的范围。

使得时间复杂度非常低，仅为O(n+k)。并且明显的为稳定的排序，因为一样的数据存在不同信息的情况不会出现，仅适用于整数。

但是它的弊端也很明显：当数列元素不是整数时，不适合用计数排序；当最大最小值差距大时，不适合使用计数排序。

桶排序（Bucket Sort）

桶排序是计数排序算法的升级版，即将数据分到有限数量的桶子里，然后每个桶再分别排序。对于分桶则利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

实际上，桶排序的f(k)值的计算，其作用就相当于快速排序中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

那么我们就基于这样的思想，来看这样的示例图：

代码：

void BucketSort(ElementType *A, int n)
{
    int min=32767;
    int max=-32767;
    for(int i=0;i<n;i++)
    {
        if(A[i] < min) 
            min=A[i]; 
        if(A[i] > max)
            max=A[i];
    }
    int size=(max-min)/n+1;    //每size个一个桶
    int cnt=(max-min)/size+1;    //桶的个数
    ElementType **B=(ElementType **)malloc(sizeof(ElementType *) * cnt);
    ElementType *C=(ElementType *)malloc(sizeof(ElementType) * cnt);    //记录桶的次数
    for(int i=0;i<cnt;i++)
    {
        B[i]=NULL;
    }
    for(int i=0;i<cnt;i++)
    {
        C[i]=0;
    }

    for(int i=0;i<n;i++) 
    { 
        int j=1; 
        while(A[i] >=min && A[i] > j*(min+size))
            j++;
        if(B[j-1] == NULL)
            B[j-1]=(ElementType *)malloc(sizeof(ElementType));
        B[j-1][C[j-1]]=A[i];
        C[j-1]++;
    }
    for(int i=0;i<cnt;i++)
    {
        InsertSort(B[i],C[i]);
    }
    int count=0;
    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<C[i];j++)
        {
            A[count++] = B[i][j];
        }
    }
}

我中间调用了插入排序来排序每个桶的数据。我们也像计数排序一样，设置一个计数数组来记录每个桶里的元素。

桶排序的平均时间复杂度为线性的O(n+k)，其中k是桶的个数。桶数量越大，其效率越高，最好的时间复杂度达到O(n)。 当然桶排序的空间复杂度为O(n+k)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

基数排序（Radix Sort）

基数排序更是桶排序的升级版，它对于整数的数列，以每一位的基数为桶进行排序。具体的分析之前的作业部分已经涉及到了，请看：

【数据结构】作业二——栈与树

代码为：

void RadixSort(int arr[])
{
    List bucket[10];
    int P=findmaxe(arr);
    // 创建桶
    for(int i=0; i<10; ++i)
        bucket[i]=CreateList();      // 从低位到高位循环每一位数字
    for(int i=0; i<P; ++i)
    {
        // 将桶置空
        for(int j=0; j<10; ++j)
            bucket[j]=MakeEmpty(bucket[j]);  // 根据当前位上的数字，将之放入对应桶中。并注意顺序（后进的放在后面）
        for(int j=0; j<N; ++j)
        {
            int digit = GetDigit(arr[j], i);
            InsertBack(arr[j], bucket[digit]);
        }
        int k = 0;
        // 将每趟排序后的结果存回arr
        for(int j=0; j<10; j++) { Position pos = First(bucket[j]); while(pos != NULL) { arr[k++] = pos->Element; 
                pos = pos->Next;
            }
        }
    }
    for(int i=0; i<10; ++i)
        DeleteList(bucket[i]);
}


// 取整数x的倒数第y位数字，y从0开始
int GetDigit(int x, int y)    //取x的第y位（个位从0开始数）
{
    int i, t = 1;
    for(i=0; i<y; i++)
        t*=10;
    return (x/t)%10;
}

void PrintArray(int arr[], int size)
{
    int i;
    for(i=0; i<size; ++i) { printf("%d ", arr[i]); } printf("\n"); } int findmaxe(int *arr) { int maxima=-1; while(*arr) //找到数组中最大值 { maxima=(*arr > maxima)?*arr:maxima;
        arr++;
    }
    int maxe=1;    //找到最大值的位数
    while(maxima/10)    //如果不是最后一位，则/10
    {
        maxima/=10;
        maxe++;
    }
    return maxe;
}

PtrToNode CreateList(void)
{
    PtrToNode p = (struct Node*)malloc(sizeof(struct Node));
    p->Next = NULL;
    return p;
}

void InsertBack(ElementType X, List L)
{
    Position pos;
    PtrToNode pNode;
    // move to tail
    pos = L;
    while(pos->Next != NULL)
        pos = pos->Next;
    pNode = (struct Node*)malloc(sizeof(struct Node));
    pNode->Element = X;
    pNode->Next = pos->Next;
    pos->Next = pNode;
}

不同的是，因为我们设计了在每一位就设计了一个桶，故它的平均时间复杂度为O(n x k) ，k为桶的个数，当然空间复杂度也来到O(n x k)。同时它也是稳定的排序。

排序算法之间的比较

讲了这么多个排序算法，它们可以用一张图来概括：

图源：https://sort.hust.cc/

后记

参考：

这里的一切都有始有终，却能容纳所有的不期而遇和久别重逢。
最后更新于 2024-01-14