第十讲：排序（下）

10.1 快速排序

10.1.1 算法概述

策略：分而治之。

下面举个例子，假如一组数为13/81/92/43/65/31/57/26/75/0，我们对其进行排序。那么首先选择出一个主元，这里我们选择为65，那么将这组数的其他成员分为了两组，一组是小于主元的13/43/31/57/26/0，一组是大于主元的81/92/75.然后将其递归处理，两边各选一个主元再进行分组……倒数第二步的时候，我们在第一步选择出来的主元左侧已经排好了顺序，右侧也排好了顺序，这样将它们放在同一个数组中，就完成了排序。

以下是上面这段话的伪码描述：

void QuickSort(ElementType A[], int N)
{
       if(N<2)
              return;
       pivot = 从A[]中选一个主元;
       将S={A[]\PIVOT}分成2个独立子集：
       A1={a∈S|a≤piovt}和
       A2={a∈S|a≥piovt}
       A[]=Quic_Sort(A1,N1)∪(pivot)∪QuickSort(A2,N2);
}

这个方法的关键在于主元的选取（选取不好，快速算法会很慢）和子集划分（这个过程也是耗费时间的一个地方）。

快速排序算法的最好情况就是每次正好中分，T(N)=O(NlogN)。

10.1.2 选主元

选取头、中、尾的中位数，也可以选取5个、7个等数字的中位数。例如8/12/3的中位数就是8。伪码描述如下：

ElementType Median3(ElementType A[], int Left, int Right)
{
       int Center=(Left+Right)/2;
       if(A[Left]>A[Center])
              Swap(&A[Left],&A[Center]);
       if(A[Left]>A[Right])
              Swap(&A[Left],&A[Right]);
       if(A[Center]>A[Right])
              Swap(&A[Center],&A[Right]);
       Swap(&A[Center],&A[Right-1]);/*将pivot藏到右边*/
       /*只需要考虑A[left+1]到A[Right-2]，这样来划分左右*/
       return A[Right-1];
}

10.1.3 子集划分

为了便于理解，还是举一个例子：

定义两个指针i（指向第一个元素）和j（指向中位数左侧的元素）。（继续强调，这里的i和j不是实际的指针，而是存储所需要元素下标的整数。）先比较i代表的元素和主元的大小，发现8大于6，那么i这个指针不变；然后看j代表的元素和主元比较，发现7大于6，将j减一（即左移一位），然后再比较，发现2小于6，这样就不对了，j停止移动。在i和j都停止移动后，将其所指向的两个元素交换位置，变成了下面这个样子。

然后i加1（右移一位），1小于6，正常，i继续加1（右移一位），4小于6，正常，i继续加1（右移一位），此时9大于6，不正常，i停止；再看j减1（左移一位），5小于6，不正常，j停止，然后交换此时i和j所代表的元素，变成下面这个样子。

然后i加1（右移一位），发现正常，i继续加1，发现正常，i再加1，发现9小于6，不正常，i停止；然后j左移一位，发现3小于6，不正常，停止。

此时发现i-j<0了，子集划分结束，同时将i代表的元素和主元交换，完成了子集的划分。最后结果如下：

快速算法的“快速”在于，划分完成后其主元被一次性放到了正确的位置再也不会移动；例如插入算法等都需要一步一步往后移。

如果有元素正好等于pivot怎么办？停下来处理。

对于小规模数据还不如用插入排序。当递归的数据规模充分小，则停止递归，直接调用简单排序。在程序中定义一个Cutoff的阈值。

10.1.4 算法实现

    伪码描述：

void Quicksort(ElementType A[], int Left, int Right)
{
       if(Cutoff<=Right-Left)
       {
              Pivot = Median3(A, Left, Right);
              i=Left;
              j= Right-1;
              for(;;)
              {
                     while(A[++i]<Pivot){}
                     while(A[--j]>Pivot){}
                     if(i<j)
                            Swap(&A[i],&A[j]);
                     else break;
              }
              Swap(&A[i],&A[Right-1]);
              Quicksort(A,Left,i-1);
              Quicksort(A,i+1,Right);
       }
       else
              Insertion_Sort(A+Left,Right-Left+1);
      
      
}

为了统一接口，在上段程序后面再加一个：

void Quick_Sort(ElementType A[], int N)
{
       Quicksort(A, 0, N-1);
}

快速排序算法是不稳定算法！

以下给出另外的C语言编写的代码，它是直接调用函数库：

/* 快速排序 - 直接调用库函数 */
 
#include <stdlib.h>
 
/*---------------简单整数排序--------------------*/
int compare(const void *a, const void *b)
{ /* 比较两整数。非降序排列 */
    return (*(int*)a - *(int*)b);
}
/* 调用接口 */
qsort(A, N, sizeof(int), compare);
/*---------------简单整数排序--------------------*/
 
 
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/
struct Node {
    int key1, key2;
} A[MAXN];
 
int compare2keys(const void *a, const void *b)
{ /* 比较两种键值：按key1非升序排列；如果key1相等，则按key2非降序排列 */
    int k;
    if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 )
        k = 1;
    else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 )
        k = -1;
    else { /* 如果key1相等 */
        if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 )
            k = -1;
        else
            k = 1;
    }
    return k;
}
/* 调用接口 */
qsort(A, N, sizeof(struct Node), compare2keys);
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/

10.2 表排序

10.2.1 算法概述

表排序用于：元素不是简简单单的排序，每一个元素都是一个庞大的结构，例如一个结构体等，此时如果我们想要交换两个元素，就不能忽略交换所需要的时间了。表排序就是在移动的时候，并不移动原始的数据，只是移动指向它的指针。

它是一种间接排序的方法，定义一个指针数组作为“表”（table）。

用下面一个例子来举例：

利用插入算法，可以得出：

如果仅要求按顺序输出，则输出：

A[table[0]],A[table[1]],……,A[table[N-1]]

10.2.2 物理排序

所谓物理排序就是说，我们不能像前文那样利用指针来移动，而是必须实际移动结构体，那该怎么办呢？

利用这样一个原理：N个数字的排列由若干个独立的环组成。

为了解释这个原理，看10.2.1中最后的结果那个表，table[0]值（3）->table[3]值（1）->table[1]的值（5）->table[5](0)返回到了table[0]。一共有三种环，这三种环互不相交，称为独立。

在排序的时候，先对一个环内进行排序。那么如何判断一个环的结束呢？

每访问一个空位i后，就令table[i]=i。当发现table[i]==i时，环就结束了。

下面分析一下复杂度的情况：

（1）最好的情况：初始即有序。

（2）最坏的情况：有N/2个环，每个环包含两个元素，元素需要移动3N/2次。

但是无论如何，复杂度都可以写为T(N)=O(mN)，其中m是每个A元素复制需要的时间。

10.3 基数排序

10.3.1 桶排序

举例：假设我们有N个学生，他们的成绩是0到100之间的整数（于是有于是有M=101个不同的成绩值个不同的成绩值）。如何在线性时间内将学生按成绩排序？

我们可以为每一个成绩值构造一个“桶”，于是就有了101个桶，如图1所示。如果我们有一个88分的学生，那么就把学生的信息查到88分的这个链表的表头里，伪码描述如下：

void Bucket_Sort(ElementType A[], int N)
{
       count[]初始化;
       while (读入读入11个学生成绩个学生成绩graded)
              将该生插入count[grade]链表;
       for ( i=0; i<M; i++ )
       {
              if(count[i])
                     输出整个count[i]链表;
       }
}

时间复杂度：T(N,M)=O(M+N)

插入学生的成绩，因为是N个学生，所以复杂度为O(N)；输出成绩，for循环，M个成绩，自然复杂度为O(M)。故总的时间复杂度如上。

如果有N=40000个学生，由于M=101，故这就是一个线性的复杂度。

图1

但是，如果M>>N怎么办？

10.3.2 基数排序

举例：假设我们有N=10个整数，每个整数的值在0到999之间之间（于是有于是有M=1000个不同的值个不同的值）。还有可能在线性时间内排序吗？

这里的基数就是跟进制有关，如果是二进制，基数就是2；如果是十进制，基数就是10。这里我们说的是十进制，所以基数就是10。

加入我们的输入序列为：64,8,216,512,27,729,0,1,343,125，用“次位优先”（Least Significant Digit，LSD）算法。主位是指的第一位，剩余的都叫次位。因此这里比较我们先从个位开始。

首先我们建立十个“桶”，然后将它们以个位数为标准放到这10个桶里面去，如表中Pass 1；然后按照十位数为标准放到10个桶里，如Pass 2；在完成之后，我们来做一个收集，收集的过程就是扫描每一个桶，然后把桶里的元素按照0,1,8,512,216……顺序用一个链表把它们串起来；串起来后，按照主位放到相应的桶里，如Pass3；最后，再对它们进行一次收集，用链表连起来，得出结果。

表3.1 基数排序算法流程表

    时间复杂度：T(N,B,P)=O(P(N+B))。其中P为基数排序次数（本例子例为3），N为输入序列中数字个数，B为整数进制。

10.3.3 多关键字排序

例如，一副扑克牌是按2种关键字排序的，如图2所示，花色是它的主关键字，面值是它的次关键字。

图2

在这里，我们可以用“主位优先”（Most Significant Digit, MSD）排序，为花色建立4个桶，在每个桶里分别排序，最后合并结果。

也可以使用“次位优先”（LSD）算法排序，为面值建立13个桶，就可以直接将结果合并，然后为花色建4个桶，放进去就可以了。

在这里，LSD优点是不需要排序，时间复杂度小的多。

基数排序是稳定的算法。

补充

（1）次位优先的C语言代码：

/* 基数排序 - 次位优先 */
 
/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10
 
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
    int key;
    PtrToNode next;
};
 
/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
 
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
    
    for (i=1; i<=D; i++) {
        d = X % Radix;
        X /= Radix;
    }
    return d;
}
 
void LSDRadixSort( ElementType A[], int N )
{ /* 基数排序 - 次位优先 */
     int D, Di, i;
     Bucket B;
     PtrToNode tmp, p, List = NULL;
     
     for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
         B[i].head = B[i].tail = NULL;
     for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
         tmp = (PtrToNode)malloc(sizeof(struct Node));
         tmp->key = A[i];
         tmp->next = List;
         List = tmp;
     }
     /* 下面开始排序 */
     for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
         /* 下面是分配的过程 */
         p = List;
         while (p) {
             Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
             /* 从List中摘除 */
             tmp = p; p = p->next;
             /* 插入B[Di]号桶尾 */
             tmp->next = NULL;
             if (B[Di].head == NULL)
                 B[Di].head = B[Di].tail = tmp;
             else {
                 B[Di].tail->next = tmp;
                 B[Di].tail = tmp;
             }
         }
         /* 下面是收集的过程 */
         List = NULL;
         for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */
             if (B[Di].head) { /* 如果桶不为空 */
                 /* 整桶插入List表头 */
                 B[Di].tail->next = List;
                 List = B[Di].head;
                 B[Di].head = B[Di].tail = NULL; /* 清空桶 */
             }
         }
     }
     /* 将List倒入A[]并释放空间 */
     for (i=0; i<N; i++) {
        tmp = List;
        List = List->next;
        A[i] = tmp->key;
        free(tmp);
     }
}

（2）主位优先C语言代码：

/* 基数排序 - 主位优先 */
/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
 
#define MaxDigit 4
#define Radix 10
 
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node{
    int key;
    PtrToNode next;
};
 
/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
 
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
    
    for (i=1; i<=D; i++) {
        d = X%Radix;
        X /= Radix;
    }
    return d;
}
 
void MSD( ElementType A[], int L, int R, int D )
{ /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
     int Di, i, j;
     Bucket B;
     PtrToNode tmp, p, List = NULL;
     if (D==0) return; /* 递归终止条件 */
     
     for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
         B[i].head = B[i].tail = NULL;
     for (i=L; i<=R; i++) { /* 将原始序列逆序存入初始链表List */
         tmp = (PtrToNode)malloc(sizeof(struct Node));
         tmp->key = A[i];
         tmp->next = List;
         List = tmp;
     }
     /* 下面是分配的过程 */
     p = List;
     while (p) {
         Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
         /* 从List中摘除 */
         tmp = p; p = p->next;
         /* 插入B[Di]号桶 */
         if (B[Di].head == NULL) B[Di].tail = tmp;
         tmp->next = B[Di].head;
         B[Di].head = tmp;
     }
     /* 下面是收集的过程 */
     i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
     for (Di=0; Di<Radix; Di++) { /* 对于每个桶 */
         if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
             p = B[Di].head;
             while (p) {
                 tmp = p;
                 p = p->next;
                 A[j++] = tmp->key;
                 free(tmp);
             }
             /* 递归对该桶数据排序, 位数减1 */
             MSD(A, i, j-1, D-1);
             i = j; /* 为下一个桶对应的A[]左端 */
         }
     }
}
 
void MSDRadixSort( ElementType A[], int N )
{ /* 统一接口 */
    MSD(A, 0, N-1, MaxDigit);
}

10.4 排序算法的比较

前三种排序算法的共同优点是算法编写简单。冒泡排序和直接插入排序每次都是交换两个元素，因此是慢的，但是它们稳定，简单选择排序是跳着交换，有可能不稳定。

希尔排序算法打破了N的平方的复杂度，它的好坏取决于d（增量序列），因为是跳着排的，所以它也是不稳定的。

堆排序和归并排序的时间复杂度是最好的，无论何时都是一样的。归并排序的缺点是它需要一个额外的空间，当数据量非常大的时候，只能排一半数据，但是它的优点是它是稳定的。堆排序理论上看很美，实际情况是虽然理论上是O(NlogN)，但是O这个常数会比较大，所以它到底跟快速排序哪个快，就难说了。堆排序和快速排序的共同缺点是不稳定，快速排序总可以构造一种最糟糕的情况是O(N²)，而且因为是递归的，所以额外空间是需要的，时间复杂度最好时，额外空间复杂度也是O(logN)。

基数排序在某种情况下，会打破NlogN的魔咒，会更快，近乎线性。它需要的额外空间是需要B个桶，每个桶设置B个数据的位置，所以到底什么情况下合算，看情况，它的好处是它是稳定的。