排序算法资料文件与下载

 排序算法

排序，又称分类，是计算机进行数据处理时经常使用的一种重要操作。本章在介绍排序算法基本概念及对各种常见排序算法进行性能比较的基础上，重点讲解插入排序、选择排序、交换排序、归并排序和分配排序等常用排序算法的原理和实现方法。

1．排序算法及常见排序算法比较

排序，是指将一个待排序元素集合按关键字递增（或递减）顺序整理为一个有序序列的过程。例如，对于一组具有关键字值{43, 56, 37, 28, 17, 39, 22, 70}的数据元素集合{R₁, R₂, …, R₈}，按关键字递增顺序的排序结果为{R₅, R₇, R₄, R₃, R₆, R₁, R₂, R₈}（对应的关键字值为{17, 22, 28, 37, 39, 43, 56, 70}）。下面都以递增排序为例讲解排序算法。

若任意两个待排序元素都具有不同的关键字值，则排序结果必然唯一；若多个待排序元素具有相同的关键字值，则排序结果可能不唯一。若采用某种排序算法对任一组元素进行排序，在排序前后，那些具有相同关键字值的元素之间的相对次序都保持不变，则将这种排序算法称为是稳定的，否则称为是不稳定的。例如，对于一组具有关键字值{43, 56, 37, 28, 17, 37, 22, 70}的数据元素集合{R₁, R₂, …, R₈}，若根据算法A得到的排序结果为{R₅, R₇, R₄, R₆, R₃, R₁, R₂, R₈}（对应的关键字值为{17, 22, 28, 37, 37, 43, 56, 70}），则算法A是不稳定的。这里需要注意，不稳定的排序算法并不一定对每一组元素都会得到不稳定的排序结果，只要一种排序算法在某一组元素上得到不稳定的排序结果，则这种排序算法就是不稳定的。

排序算法有很多，各有优缺点，一般从时间复杂度、空间复杂度、稳定性3个角度衡量算法优劣并结合实际应用条件选取适合的排序算法。其中，时间复杂度主要看排序时元素之间的比较次数和元素的移动次数；空间复杂度主要看排序时除了待排序元素所占据的空间外还需要多大的辅助空间。

排序分为两类：内排序和外排序。内排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外排序是指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。

下面只介绍直接插入排序、简单选择排序、冒泡排序、堆排序、快速排序、归并排序、箱排序和基数排序等内排序算法。下面先给出是这些排序算法的适用范围和复杂度情况，可为读者在遇到排序问题时选择合适的算法提供参考。

1）排序算法的适用范围

排序算法的适用范围如下：

（1）直接插入排序、简单选择排序和冒泡排序都是简单排序算法，它们的时间复杂度和空间复杂度分别为O(n²)和O(1)。若待排序元素数量n较小，可以选用直接插入排序和冒泡排序。另外，当待排序元素基本有序时，也应选用直接插入排序和冒泡排序，此时时间复杂度都能达到O(n)。若元素本身数据量较大，元素移动操作代价较高，则应选用平均移动元素次数最少的简单选择排序。希尔排序是对直接插入排序算法的改进，大大降低了时间复杂度，但它是一种不稳定的排序算法。

（2）堆排序、快速排序和归并排序主要适用于待排序元素数量n较大的情况，当待排序元素数量n较小时，它们的性能有可能劣于简单排序算法。因此，在实际应用时，快速排序算法和归并排序算法经常与简单排序算法结合使用（例如，可以先用快速排序算法将集合划分为规模更小的子集合，对于元素数量较小的子集合，则用直接插入排序算法进行排序）。在所有平均时间复杂度为O(nlog₂n)的算法中，尽管快速排序在最坏情况下时间复杂度较高，但它通常被认为是平均性能最好的一种算法，并且通过优化可以降低最坏情况出现的概率。归并排序是一种稳定的排序算法，其时间性能一般要优于堆排序，但它所需要的辅助空间较多，当应用环境要求排序前后具有相同值的元素相对次序不能改变时可以考虑使用。堆排序所需的辅助空间最少，当可用空间非常有限时可以考虑使用。

（3）箱排序和基数排序的时间复杂度最低，但它们的空间复杂度最高。箱排序主要适用于待排序元素长度（即d值）较小的情况，在实际中应用不多；基数排序是箱排序的改进，主要适用于整数或字符串的排序，或者与其他排序算法结合进行实数的排序（例如，可以先用基数排序算法按整数部分将元素分成若干个子集合，再对每个子集合应用直接插入排序算法进行排序）。

2）排序算法的复杂度

下面对各类排序算法的性能作一下比较。设待排序元素数目为n、待排序元素的长度为d、待排序元素每一位可能取值的个数为rd（例如，待排序元素为至多4位的整数，此时d=4、rd=10；再如，待排序元素为长度至多为20的字符串、每一字符取值为'a'~'z'，此时d=20、rd=26），则各排序算法的性能如表1所示。

表1  各种排序算法的性能比较

2. 插入排序

插入排序是指按关键字大小每次将一个待排序的元素插入到已排序的序列中，直至所有元素都插入完毕。插入排序有多种形式，下面主要介绍直接插入排序和希尔排序两种算法。

2.1  直接插入排序

直接插入排序是一种简单排序算法，其具体步骤为：

（1）初始已排序区为空，将第一个待排序的元素插入到已排序区中。

（2）将后继每一个待排序的元素依次取出，并按照关键字大小将其插入到已排序区中的适当位置，使该序列仍然有序。

（3）重复上一步骤直至将待排序的元素都插入到已排序序列中。

例如，对于一组具有关键字值{43, 56, 37, 28, 17, 37, 22, 70}的数据元素集合{R₁, R₂, …, R₈}，其直接插入排序过程如图1所示。

                                                                                       图1  直接插入排序过程示例

直接插入排序的算法描述如下。

【描述1】  直接插入排序的算法描述。

分析：由图1可见，已排序元素数目与待排序元素数目之和保持不变，因此，可以使用同一个数组的不同部分分别保存已排序序列和未排序元素集合。如定义一个一维数组R，在第i趟排序后R中下标为1到i+1的位置用于存放已排序序列、之后的位置用于存放未排序元素集合。

参考程序如下：

template <class T>

void InsertSort(T R[], int nSize)

{

int i, j;

for (i=1; i<nSize; i++)

{

// 若当前待排序元素的值大于或等于已排序序列中最后一个元素的值，则该元

// 素不需改变位置

if(R[i+1]>=R[i])

continue;

R[0] = R[i+1]; // 将待排序元素放入监视哨中

R[i+1] = R[i];

for (j=i-1; R[0]<R[j]; j--) // 利用监视哨可以省去下标取值范围的检查条件

R[j+1] = R[j];

R[j+1] = R[0];

}

}

提示：在排序算法中，数组中下标为0的位置一般不存储数据元素，而是用来作为停止循环的监视哨，以减少比较次数。

直接插入排序算法所需的元素比较次数和元素移动次数与元素的初始排列有关。对于包含n个元素的待排序集合，若初始时元素是按递增正序排列的，则所需的元素比较次数达到最小值n-1、元素移动次数达到最小值0（时间复杂度分别为O(n)和O(1)）；若初始时元素是按递减逆序排列的，则所需的元素比较次数达到最大值、元素移动次数达到最大值（时间复杂度均为O(n²)）；平均情况下元素比较次数和元素移动次数的时间复杂度均为O(n²)。直接插入排序算法只需一个监视哨的辅助空间，因此空间复杂度为O(1)。算法严格按照从前至后的顺序依次将各元素插入到正确的位置，保证了具有相同值的元素的相对次序在排序前后保持不变，因此直接插入排序是稳定的。

2.2  希尔排序

希尔排序，又称为“缩小增量排序”，其具体步骤为：

（1）令n为待排序元素数目，设置增量序列{d₀, d₁, …, d_k}，其中n>d₀>d₁>…>d_k=1。

（2）按增量d_i（i依次取值为0, 1, …, k）将待排序元素分为d_i组，将所有下标距离为d_i的倍数的元素放在同一组中，即R[1], R[1+ d_i], R[1+2*d_i], …在第一组中，R[2], R[2+ d_i], R[2+2*d_i], ……在第二组中，……，依此类推。然后分别在各组内进行直接插入排序。

（3）重复上一步骤直至最后以1为增量对所有待排序元素进行直接插入排序。

例如，对于一组具有关键字值{43, 56, 37, 28, 17, 37, 22, 70, 30, 80}的数据元素集合{R₁, R₂, …, R₁₀}，以增量序列{5, 3, 1}进行希尔排序，其过程如图2所示。

                                                                                                图2  希尔排序过程示例

希尔排序的算法描述如下。

【描述2】  希尔排序的算法描述。

参考程序如下：

// 由ShellSort调用，按增量di分组并在各组内进行直接插入排序

template <class T>

void ShellInsert(T R[], int nSize, int di)

{

int i, j;

for(i=1; i<=nSize-di; i++)

{

// 若分组中当前待排序元素的值大于或等于已排序序列中最后一个元素的值，

// 则该元素不需改变位置

if(R[i+di]>=R[i])

continue;

R[0] = R[i+di]; // 将待排序元素放入监视哨中

for(j=i; j>0 && R[0]<R[j]; j-=di)

R[j+di] = R[j];

R[j+di] = R[0];

}

}

// 按增量序列d对数组R中的元素进行希尔排序

template <class T>

void ShellSort(T R[], int nSize, int d[], int k)

{

int i;

for(i=0; i<k; i++)

ShellInsert(R, nSize, d[i]);

}

提示：希尔排序的比较次数和移动次数依赖于增量序列，为了具有较好的性能，一般增量序列中的元素应避免互为倍数的情况。另外，增量序列中的最后一个元素必须是1。

希尔排序算法的时间复杂度与使用的增量序列有关，但如何针对特定增量序列计算算法的时间复杂度以及如何选择增量序列使算法的时间复杂度最低仍是数学上尚未解决的难题。因此，这里仅给出定性的结论：当待排序元素数目n很大时，希尔排序算法的时间复杂度要远低于直接插入排序算法。与直接插入排序算法相同，希尔排序算法只需要一个监视哨的辅助空间，因此空间复杂度也为O(1)。从图2中可以看出，希尔排序是不稳定的。

3． 选择排序

选择排序是指每次从待排序的元素中选择具有最小（或最大）关键字的元素放到已排序序列的尾部（或头部），直至所有元素都排序完毕。选择排序有多种形式，下面主要介绍简单选择排序和堆排序两种。

3.1  简单选择排序

简单选择排序是一种简单排序算法，其具体步骤为：

（1）初始已排序区为空，待排序区包含所有待排序元素。

（2）从待排序区中选择具有最小关键字的元素，将其与待排序区的第一个元素交换位置，并将该位置加到已排序区中。

（3）重复上一步骤直至所有元素都排序完毕。

例如，对于一组具有关键字值{43, 56, 37, 28, 17, 37, 22, 30}的数据元素集合{R₁, R₂, …, R₈}，其简单选择排序过程如图3所示。

                                                                                          图3  简单选择排序过程示例

简单选择排序的算法描述如下。

【描述3】  简单选择排序的算法描述。

参考程序如下：

template <class T>

void SelectSort(T R[], int nSize)

{

int i, j, nMin;

for(i=1; i<nSize; i++)

{

nMin = i; // 先假设待排序区中下标为i的元素值最小

// 通过循环找出待排序区中具有最小值的元素位置

for(j=i+1; j<=nSize; j++)

if (R[j]<R[nMin])

nMin = j;

// 若待排序区中第一个元素具有最小值，则不需进行交换

if(nMin==i)

continue;

// 将待排序区中具有最小值的元素与第一个元素交换位置

R[0] = R[i];

R[i] = R[nMin];

R[nMin] = R[0];

}

}

提示：在选择排序中，对于nSize个元素的排序问题，若前nSize-1个元素已排好序，则最后一个元素必然是具有最大值的元素，不需再排序。因此，选择排序只需进行nSize-1轮。

简单选择排序算法所需的元素比较次数与元素的初始排列无关，任何情况下算法所需的元素比较次数均为（时间复杂度为O(n²)）。算法所需的元素移动次数与元素的初始排列有关，若初始时元素是按递增正序排列的，则所需的元素移动次数达到最小值0（时间复杂度为O(1)）；若初始时元素是递减逆序排列的，则所需的元素比较次数达到最大值3(n-1)（时间复杂度均为O(n)）；平均情况下元素移动次数的时间复杂度均为O(n)。简单选择排序算法只在进行元素交换时需要一个辅助空间，因此空间复杂度为O(1)。从图3可以看出，简单选择排序是不稳定的。

3.2  堆排序

在简单选择排序算法的每轮排序中，都需要对待排序区的所有元素进行比较，最后只有具有最小关键字的元素被取出，而其余待排序区中的元素在下一轮排序时需重新比较，这样就使得许多比较操作重复多次，增加了算法的时间复杂度。例如，对于图3所示的简单选择排序过程，在第1轮选择排序中，37和28已做过比较；而在第2轮和第3轮选择排序中，37和28会再作比较。

堆排序是对简单选择排序算法的优化，它利用完全二叉树的顺序存储结构减少元素之间的重复比较。堆排序的过程实质上就是不断创建堆的过程，下面先给出堆的概念，然后再给出堆排序算法。

1）堆

对于包含n个元素的集合R={R[1], R[2], …, R[n]}，若满足：

（1）R[i]≤R[2*i]且R[i]≤R[2*i+1]（即R所表示的完全二叉树中每一棵子树的根结点的值均不大于其孩子结点的值）。

（2）或R[i]≥R[2*i]且R[i] ≥R[2*i+1]（即R所表示的完全二叉树中每一棵子树的根结点的值均不小于其孩子结点的值）。

则称集合R为堆。若满足前一个条件则称R为小根堆，满足后一个条件则称R为大根堆。例如，{56, 43, 37, 30, 17, 37, 22, 28}是一个大根堆，{17, 28, 22, 30, 56, 37, 37, 43}是一个小根堆，它们所对应的完全二叉树表示分别如图4（a）和7-4（b）所示。

                                                                                          图4  大根堆和小根堆示例

2）建堆方法

建堆是指假设已存在一棵由元素关键字作为结点的完全二叉树，现在调整该二叉树中结点的值，使调整后的二叉树表示的元素集合是一个堆。

堆一般采用自底向上的构建方法，即在将以某一结点为根结点的二叉树构建成堆之前，先将其左子树和右子树构建成堆。以叶子结点为根的子树必然是堆，因此，对于由n个元素构成的完全二叉树，其对应的堆的构建过程从R[ën/2û]作为根结点的子树开始，依次对R[ën/2û-1]、R[ën/2û-2]、…、R[1]作为根结点的树进行堆的构建。例如，对于集合{30, 22, 37, 17, 28, 37, 56, 43}，其对应的大根堆的构建过程如图5所示，在每一步处理时将虚线框中的子树整理为堆。

                                                                                    图5  构建大根堆过程示例

在将一棵R[i]作为根结点的子树整理为堆时，只有根结点不满足堆的条件，因此，需将根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件，这里以大根堆构建为例介绍其具体过程：

（1）若R[i]存在左孩子R[2*i]，则令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i]，则令j=2*i+1。将R[j]与R[i]比较，若R[i]较小，则将R[i]和R[j]交换，并令i=j。

（2）重复上述步骤直至R[i]无孩子结点或R[i]比其孩子结点都大，此时该子树即为堆。

例如，对于图5所示的大根堆构建过程，图5（c）到图5（d）的作用是将整棵树整理为堆，其具体步骤为：将根结点R[1]与具有较大值的右孩子结点R[3]比较，有R[1]<R[3]，因此将R[1]和R[3]交换；将R[3]与左孩子结点R[6]比较（左右孩子同样大时以左孩子结点优先），有R[3]<R[6]，因此将R[3]和R[6]交换；R[6]无孩子结点，此时该树已整理为堆。

3）堆排序算法

下面给出堆排序的具体过程：

（1）采用自底向上的方法将包含n个元素的待排序集合R={R[1], R[2], …, R[n]}整理为大根堆，其元素数目i=n，初始时已排序集合R'为空集；

（2）将R[1]与R[i]交换，并将i算作已排序集合中的元素位置，更新待排序集合中最后一个元素的位置i=i-1，此时待排序集合R={R[1], R[2], …, R[i]}，已排序集合R'={R[i+1], R[i+2], …, R[n]}。显然，待排序集合R={R[1], R[2], …, R[i]}中只有根结点R[1]不满足大根堆的条件，通过下移R[1]重新将R整理为大根堆；

（3）重复上一步骤直至待排序集合R={R[1]}，此时直接将R[1]作为已排序集合R'中的元素，堆排序过程结束。

例如，对于集合{30, 22, 37, 17, 28, 37, 56, 43}，其堆排序过程如图6所示。可见，这里给出的堆排序选择元素的顺序与前面给出的简单选择排序正好相反，每轮堆排序从待排序集合中选择最大元素并将其放到已排序集合的头部。本书中给出的是常见实现方式，实际上可以利用小根堆实现堆排序使其选择元素的顺序与前面给出的简单选择排序相同，也可更改前面给出的简单选择排序使其选择元素的顺序与这里给出的利用大根堆实现的堆排序相同。

                                                                                                图6  堆排序过程示例

堆排序的算法描述如下。

【描述4】  堆排序的算法描述。

参考程序如下：

// 由HeapSort调用，将数组中nTop到nBottom之间的元素调整为大根堆

// 要求除R[nTop]外，nTop+1到nBottom之间的元素均满足大根堆的条件

template <class T>

void Sift(T R[], int nTop, int nBottom)

{

int i;

R[0] = R[nTop];                // 记录待调整的元素

i = 2*nTop;                    // R[i]是R[nTop]的左孩子

while(i <= nBottom)              // 当左孩子存在时则一直循环

{

// 若右孩子存在且右孩子关键字较大，则将右孩子与待调整元素比较

if(i<nBottom && R[i]<R[i+1])

i++;

// 若待调整元素比当前孩子关键字小

if(R[0] < R[i])

{

R[nTop] = R[i];                 // 将当前孩子调整到双亲的位置上

nTop = i;                      // 将待调整元素放到当前孩子位置上

}

else

break; //待调整元素比当前孩子关键字大，nTop即为待调整元素应放位置

i = 2*nTop; // R[i]是R[nTop]的左孩子

}

R[nTop] = R[0];

}

// 对R进行堆排序

template <class T>

void HeapSort(T R[], int nSize)

{

int i;

// 将R调整为大根堆

for(i=nSize/2; i>0; i--)

Sift(R, i, nSize);

for(i=nSize; i>1; i--)

{

// 将堆中最大元素与堆中最后一个元素交换位置

R[0] = R[1];

R[1] = R[i];

R[i] = R[0];

// 将R中前nI-1个元素调整为大根堆

Sift(R, 1, i-1);

}

}

堆排序算法的时间复杂度分析较为复杂，这里仅给出结论：堆排序算法在平均情况和最坏情况下所需的元素比较次数和元素移动次数的时间复杂度均为O(nlog₂n)。堆排序算法只在整理堆和进行元素交换时需要一个辅助空间，因此空间复杂度为O(1)。从图6可以看出，堆排序是不稳定的。

提示：要实现降序排序，只要在建立初始堆和整理堆时按照小根堆处理就行了。感兴趣的读者可以自己对程序进行修改。

4． 交换排序

交换排序是指从待排序的元素中选择两个次序相反的元素进行交换，直至任意两个元素的次序都正确。下面介绍冒泡排序和快速排序两种交换排序方法。

4.1  冒泡排序

冒泡排序是一种简单排序算法，其具体步骤为：

（1）初始已排序区为空，待排序区包含所有待排序元素。

（2）在一轮排序中，对待排序区所有相邻元素从前至后进行两两比较，若相邻两个元素次序相反（即前一个元素的关键字值大于后一个元素的关键字值），则交换它们的位置。每轮排序后，待排序区中的最大元素会移到待排序区的尾部，将待排序区的最后一个元素放到已排序区的头部。

（3）重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有出现相邻元素交换的情况，此时直接将待排序区中的所有元素按原次序放到已排序区的头部，冒泡排序结束。

例如，对于一组具有关键字值{43, 56, 37, 28, 17, 37, 22, 30}的数据元素集合{R₁, R₂, …, R₈}，其冒泡排序过程如图7所示。在第6轮冒泡排序中，由于没有出现相邻元素交换的情况，因此，直接将待排序区中的所有元素按原次序放到已排序区的头部，冒泡排序结束。

                                                                                                图7  冒泡排序过程示例

冒泡排序的算法描述如下。

【描述5】  冒泡排序的算法描述。

参考程序如下：

// 对R进行冒泡排序

template <class T>

void BubbleSort(T R[], int nSize)

{

int i, j;

bool bSwap;

for(i=nSize; i>0; i--)// 待排序区的终止位置

{

bSwap = false;

for(j=1; j<i; j++)

{

// 若相邻两个元素次序相反，则交换它们的位置

if(R[j] > R[j+1])

{

R[0] = R[j];

R[j] = R[j+1];

R[j+1] = R[0];

bSwap = true;

}

}

// 若没有出现相邻元素交换的情况，则冒泡排序结束

if(!bSwap)

break;

}

}

冒泡排序算法所需的元素比较次数和元素移动次数与元素的初始排列有关。对于包含n个元素的待排序集合，若初始时元素是按递增正序排列的，则所需的元素比较次数达到最小值n-1、元素移动次数达到最小值0（时间复杂度分别为O(n)和O(1)）；若初始时元素是按递减逆序排列的，则所需的元素比较次数达到最大值、元素移动次数达到最大值（时间复杂度均为O(n²)）；平均情况下元素比较次数和元素移动次数的时间复杂度均为O(n²)。冒泡排序算法只在交换元素时需要一个辅助空间，因此空间复杂度为O(1)。算法仅对相邻两个元素进行交换，若相邻两个元素的值相同则不会发生交换操作，从而保证了具有相同值的元素的相对次序在排序前后保持不变，因此冒泡排序是稳定的。

4.2  快速排序

在冒泡排序算法中，仅对相邻元素进行比较和交换。通过每次交换，元素前移或后移一个位置。若排序前元素位置为i，排序后元素位置为j，则在排序过程中为了将该元素移到正确位置需要做|j-i|次交换操作。因此，冒泡排序所需要的元素比较和移动次数较多。

快速排序是对冒泡排序算法的优化，它通过对待排序集合进行逐层划分，可以实现两个相距较远元素的比较和交换操作，从而大大减少了元素的比较和移动次数。快速排序的过程实质上就是不断对待排序集合进行划分的过程，因此，在介绍快速排序之前，先说明划分的作用和待排序集合划分的过程。

划分是以指定元素x为基准将一个集合R分为两个子集R₁和R₂，其中R₁中的元素都小于或等于x，R₂中的元素都大于或等于x。例如，对于集合R={43, 56, 37, 28, 17, 37, 22, 30}，以43为基准，可以将其划分为两个子集R₁={30, 22, 37, 28, 17, 37}和R₂={56}。

对于包含(high-low+1)个元素的待排序集合R={R[low], R[low+1], …, R[high]}，以R[k]（low ≤k ≤high）为基准对其进行划分的具体过程为：

（1）令i、j分别指向集合R的第一个元素和最后一个元素（即i=low、j=high），并将R[k]与R[i]交换（即初始基准元素在i所指向的位置，此时基准元素前面没有任何元素，下面对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素）。

（2）若j!=i且R[j]≥R[i]，则令j=j-1，重复直至R[j]<R[i]或j==i。上述处理后，若j!=i（即通过R[j]<R[i]这个条件退出循环）则将R[j]与R[i]交换、i=i+1，并转到下一步（该步处理结束后，基准元素在j所指向的位置，此时基准元素后面的元素都大于或等于基准元素，而位置i前面的元素都小于或等于基准元素，下面对基准元素前面、位置在i到j-1之间的元素按照从前至后的顺序逐一检查其是否小于或等于基准元素）。

（3）若i!=j且R[i]≤R[j]，则令i=i+1，重复直至R[i]>R[j]或i==j。上述处理后，若i!=j（即通过R[i]>R[j]这个条件退出循环）则将R[i]与R[j]交换、j=j-1，并回到上一步（该步处理结束后，基准元素在i所指向的位置，此时基准元素前面的元素都小于或等于基准元素，而位置j后面的元素都大于或等于基准元素，下面继续对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素）；否则集合划分操作结束。

集合划分操作结束后，i和j所共同指向的位置即是基准元素所在的位置，子集合R₁={R[low], …, R[i-1]}中的元素都小于或等于基准元素R[i]，子集合R₂={R[i+1], …, R[high]}中的元素都大于或等于基准元素R[i]。例如，对于集合R={56, 43, 37, 22, 28, 30 , 37, 17}，以28为基准，其划分过程如图8所示。

图8  集合划分过程示例

集合划分的算法描述如下。

【描述6】  集合划分的算法描述。

分析：在算法实现时，为了减少基准元素的移动次数，可以用R[0]保存基准元素，每次将元素R[X]与基准元素比较时直接将R[X]与R[0]比较即可，而每次将元素R[X]与基准元素交换时只需将元素R[X]移入基准元素应在的位置即可。在最后找到基准元素的正确位置后，将R[0]移入该位置。图8所对应的算法实现处理过程如图9所示。

                                                                                          图9  集合划分算法实现示例

参考程序如下：

// 对集合{R[low], R[low+1], ..., R[high]}进行划分

template <class T>

int Partition(T R[], int low, int high, int nBase)

{

int i=low, j=high;

// 将基准元素存入R[0]中

R[0] = R[nBase];

if(nBase != low)

R[nBase] = R[low];

while(i!=j)

{

// 从后向前扫描

while(i!=j && R[j]>=R[0])

j--;

if(i!=j)

{

R[i] = R[j];

i++;

}

// 从前向后扫描

while(i!=j && R[i]<=R[0])

i++;

if(i!=j)

{

R[j] = R[i];

j--;

}

}

// 将基准元素放入正确位置

R[i] = R[0];

return i;

}

快速排序就是对集合不断划分的过程：通过划分可以将一个集合分为两个子集合，若子集合中元素数目大于1则再对子集合分别进行划分，重复该过程直至最终每个子集合中元素数目都小于或等于1时快速排序结束。例如，对于集合R={37, 43, 26, 30, 17, 37, 22, 28}，其快速排序过程如图11所示（这里假设每次将待划分集合中的第一个元素作为基准元素）。

                                                                                             图10  快速排序过程示例

显然，快速排序过程是一个对集合的递归划分过程，可以使用递归方式来实现。下面给出快速排序递归实现的算法描述。

【描述7】  快速排序递归实现的算法描述。

参考程序如下：

// 对R进行快速排序的递归实现

template <class T>

void QuickSort(T R[], int low, int high)

{

int nBase; // 每次划分后基准元素所在的位置

if(low < high) // 待划分的集合长度大于

{

// 以R[low]为基准对集合{R[low], R[low+1], ..., R[high]}进行划分

nBase = Partition(R, low, high, low);

// 对划分后的两个子集合分别进行快速排序

QuickSort(R, low, nBase-1);

QuickSort(R, nBase+1, high);

}

}

快速排序也可以利用栈以非递归方式实现，下面给出快速排序非递归实现的算法描述。

【描述8】  快速排序非递归实现的算法描述。

分析：非递归快速排序需要利用栈实现，栈顶元素是当前要划分的集合（由Range类对象表示集合，其中两个成员变量m_low和m_high分别保存待划分集合的起始位置和结束位置）。具体步骤为：

（1）将初始待排序集合进栈。

（2）取栈顶元素，若上一次出栈的是划分后的两个子集合中的后一个子集合，则表明其划分后得到的两个子集合也已划分完毕，将栈顶元素出栈；若上一次出栈的是划分后的两个子集合中的前一个子集合，则表明其划分后得到的两个子集合中还有一个子集合没有进行划分，将后一个子集合进栈；否则，表明对栈顶元素所表示的集合还没有进行划分，此时若栈顶集合长度大于1则对栈顶集合进行划分、并将划分后得到的前一个子集合进栈，若栈顶集合长度小于或等于1则不需进行划分、直接出栈即可。

（3）重复步骤（2）直至栈为空。

对于集合R={37, 43, 26, 30, 17, 37, 22, 28}，其非递归快速排序过程如表2所示。

表2  非递归快速排序过程示例

参考程序如下：

// 对R进行快速排序的非递归实现

class Range // 存储每次划分后子集合的起始位置和终止位置

{

public:

template <class T>

friend void QuickSort(T R[], int nSize);

Range() { m_low = m_high = 0; }

Range(int low, int high)

{

m_low = low;

m_high = high;

}

private:

int m_low;

int m_high;

};

template <class T>

void QuickSort(T R[], int nSize)

{

LinkStack<Range> s; // 保存需要进行划分的集合

int nBase; // 每次划分后基准元素所在的位置

Range range(1, nSize), lastPopRange(nSize+1, nSize+1);

s.Push(range); // 初始对整个集合进行划分

while(!s.IsEmpty()) // 栈不为空表示仍有需要进行划分的集合

{

s.Top(range); // 取栈顶元素

// 若上一次出栈的是划分后的两个子集合中的后一个子集合，则作出栈操作

if(range.m_high==lastPopRange.m_high)

{

s.Pop(lastPopRange);

continue;

}

// 若上一次出栈的是划分后的两个子集合中的前一个子集合，则将后一个子集

// 合入栈

else if(range.m_low==lastPopRange.m_low)

{

s.Push(Range(lastPopRange.m_high+2, range.m_high));

continue;

}

if(range.m_low < range.m_high) // 若待划分集合长度大于1

{

// 以R[low]为基准对集合{R[low], R[low+1], ..., R[high]}进行划分

nBase = Partition(R, range.m_low, range.m_high, range.m_low);

// 将划分后的两个子集合中的前一个子集合入栈

s.Push(Range(range.m_low, nBase-1));

}

else // 否则将其出栈

s.Pop(lastPopRange);

}

}

快速排序算法所需的元素比较次数、元素移动次数及辅助空间均与元素的初始排列有关。对于包含n个元素的待排序集合，假设每次以第一个元素作为基准对集合进行划分，若初始时元素是基本有序的，则每次对长度为m的集合划分后得到的两个子集合的长度分别为0和m-1，也就是说不能对集合进行有效的一分为二的划分，此时失去了快速排序的优势，算法的时间复杂度和空间复杂度分别达到最大值O(n²)和O(n)；在最好情况下，每次划分得到的两个子集合的长度大致相等，此时算法的时间复杂度和空间复杂度分别达到最小值O(nlog₂n)和O(log₂n)；平均情况下算法的时间复杂度为O(nlog₂n)、空间复杂度为O(log₂n)。从图10可以看出，快速排序是不稳定的。

5．归并排序

K路归并排序是指每次将K（K≥2）个已排序的子序列组合在一起，形成一个有序的序列，重复该过程直至得到一个包含所有待排序元素的有序序列。这里以二路归并排序（下文简称归并排序）为例介绍归并排序的算法。

归并排序的具体步骤为：

（1）对于包含n个元素的待排序集合，将其分为n个长度为1的子序列。

（2）将每两个相邻的子序列进行归并，得到ën/2û个长度为2的子序列和0或1个长度为1的子序列。

（3）在此基础上，再对每两个相邻的子序列进行归并，得到ën/4û个长度为4的子序列和0或1个长度小于4的子序列。

（4）重复该过程直至得到一个长度为n的有序序列为止。

例如，对于集合R={43, 56, 37, 28, 17, 37, 22, 30, 2}，其归并排序过程如图11所示。

图11归并排序过程示例

归并排序的算法描述如下。

【描述8】  归并排序的算法描述。

参考程序如下：

// 将pSrc所指向的数组中下标为[low,mid]的子序列与下标为[mid+1,high]的子序

// 列归并，归并结果保存在pDst所指向数组中相应的位置

template <class T>

void Merge(T *pSrc, T *pDst, int low, int mid, int high)

{

int i=low, j=mid+1, k=low;

while(i<=mid && j<=high)

{

// 比较下标为nI和nJ的两个元素，将具有较小值的元素先取出赋到pDst所

// 指向的数组中

if(pSrc[i]<=pSrc[j])

{

pDst[k]=pSrc[i];

i++;

}

else

{

pDst[k]=pSrc[j];

j++;

}

k++;

}

// 若一个子序列已处理完毕、而另一个子序列中还有元素未处理，则直接将这些元

// 素赋到pDst所指向的数组中

while(i<=mid)

{

pDst[k]=pSrc[i];

i++;

k++;

}

while(j<=high)

{

pDst[k]=pSrc[j];

j++;

k++;

}

}

// 将pSrc所指向的数组中相邻的两个长度为nLength的子序列归并

// 归并结果保存在pDst所指向的数组中

template <class T>

void MergePass(T *pSrc, T *pDst, int nSize, int nLength)

{

int i, j;

// 将相邻的两个长度为nLength的子序列归并

for(i=0; (i+2)*nLength<=nSize; i+=2)

Merge(pSrc, pDst, i*nLength+1, (i+1)*nLength, (i+2)*nLength);

if((i+1)*nLength<nSize)       // 后一个子序列长度不足nLength

Merge(pSrc, pDst, i*nLength+1, (i+1)*nLength, nSize);

else           // 最后只剩下一个子序列，则直接拷贝该子序列中的元素

for(j=i*nLength+1; j<=nSize; j++)

pDst[j]=pSrc[j];

}

// 对R进行归并排序

template <class T>

void MergeSort(T R[], int nSize)

{

int nLength; // 待归并的子序列长度

T *MR = new T[nSize+1]; // 存放归并后的结果

T *pSrc=R, *pDst=MR, *pTemp;

int i;

if(MR==NULL)

exit(1);

for(nLength=1; nLength<nSize; nLength*=2)

{

// 将pSrc指向数组中相邻的两个长度为nLength的子序列归并，

// 归并结果保存在pDst所指向的数组中

MergePass(pSrc, pDst, nSize, nLength);

// 交换pSrc和pDst的指向，即基于上一轮归并结果进行下一轮子序列归并

pTemp=pSrc;

pSrc=pDst;

pDst=pTemp;

}

if(pSrc!=R) // 若最后一轮归并后的结果保存在MR中

{

for(i=1; i<=nSize; i++)

R[i]=MR[i];

}

delete []MR;

}

对于包含n个元素的待排序集合，归并排序算法需进行élog₂nù趟归并，每轮归并中元素移动次数为n、元素比较次数小于n，因此归并排序在任何情况下的时间复杂度均为O(nlog₂n)。归并排序需要与待排序元素等数量的辅助空间，空间复杂度为O(n)。归并排序对相邻的两个子序列进行归并操作，若两个子序列中含有具有相同值的元素，则归并后的结果中后一个子序列的同值元素必然在前一个子序列的同值元素的后面，同值元素的相对次序不会改变，因此归并排序是稳定的。

6．分配排序

前面介绍的排序算法都是通过对待排序集合中元素的比较和移动来实现排序的。分配排序则采用了一种截然不同的思想，它不需要对元素进行直接比较，而是根据元素本身所具有的值将各元素逐一映射到一组有序空间中，最后再依次从有序空间中将各元素取出即形成了排序结果。与前面学习的排序算法相比，分配排序一般有着更低的时间复杂度但更高的空间复杂度。下面介绍箱排序和基数排序两种分配排序方法。

6.1  箱排序

箱排序，又称为桶排序，是指通过设置一些有序的箱子，将待排序集合中各元素根据它们的值逐一分配到各箱子中，最后再按箱子的顺序依次将各元素从箱子中取出从而形成排序结果的一种排序算法。

在箱排序中，箱子的个数由元素的取值范围决定。例如，要将学生按其课程成绩（设取值范围为0～100之间的整数）排序，则需要设置101个箱子；要将学生按其学号（设学号为7位，取值范围为0000000～9999999）排序，则需要设置10 000 000个箱子。可见，箱排序适用于取值范围较小的情况。

另外，在箱排序中，具有相同值的元素会放在同一个箱子里。例如，n名学生的课程成绩都是m，那么在按课程成绩排序时这n名学生对应的是同一个箱子。此时，可以考虑每个箱子用一个线性表来保存若干个具有相同值的元素，在具体实现时通常使用队列以保证排序过程是稳定的。

箱排序的具体步骤为：

（1）假设待排序元素的取值范围为m~m+n-1，则箱子数量为n，设置包含n个元素的队列集合B={B[0], B[1], …, B[n-1]}代表n个箱子。

（2）依次取出每一个待排序元素，若其值为m+i（i=0, 1, …, n-1），则通过入队操作将其放在箱子B[i]中。

（3）从B[0]开始，依次检查集合B中每一个队列所代表的箱子，若箱子不为空，则通过出队操作将箱子中的元素逐个取出并依次加到已排序集合中。

例如，对于待排序集合R={3, 6, 7, 8, 3, 7, 2, 9}，其箱排序过程如图12所示。

                                                                                                图12  箱排序过程示例

箱排序的算法描述如下。

【描述9】  箱排序的算法描述。

参考程序如下：

// 对R进行箱排序

template <class T>

void BinSort(T R[], int nSize)

{

int nMax=1, nMin=1, nRange, i, j;

LinkQueue<T> *B = NULL;

// 计算待排序元素的取值范围

for(i=2; i<=nSize; i++)

{

if(R[i] < R[nMin])

nMin = i;

else if(R[i] > R[nMax])

nMax = i;

}

nRange = R[nMax]-R[nMin]+1;

// 根据待排序元素取值范围设置箱子

B=new LinkQueue<T>[nRange];

if(B==NULL)

exit(1);

// 根据元素值通过入队操作将其装入对应的箱子

for(i=1; i<=nSize; i++)

B[R[i]-R[nMin]].Insert(R[i]);

// 通过出队操作依次从箱子中取出元素并放回到R中

i=1;

for(j=0; j<nRange; j++)

{

while(!B[j].IsEmpty())

{

B[j].Delete(R[i]);

i++;

}

}

// 释放箱子所占据的空间

delete []B;

}

对于包含n个元素的待排序集合，箱排序算法仅需进行n次装箱操作和n次出箱操作，因此箱排序在任何情况下的时间复杂度均为O(n)。箱排序的空间复杂度与待排序元素的长度有关系，若对d位数据组成的集合进行箱排序，且数据的每一位可能取的值的个数为rd，那么需要rd^d个箱子（例如，要对由4位十进制整数组成的集合进行箱排序，需设置10⁴=10 000个箱子），另外还需要设置与待排序元素数量相同的辅助空间来存储装箱的元素，因此箱排序的空间复杂度为O(n+rd^d)。箱排序用队列存储具有相同值的元素，位置靠前的同值元素装箱时先入队、出箱时先出队，保证了同值元素的相对次序不会改变，因此归并排序是稳定的。

6.2  基数排序

箱排序适用于待排序元素长度较小的情况，当待排序元素长度较大时则可能会存在大量的空箱子、从而导致存储空间的浪费。基数排序是对箱排序的改进和推广，它先将待排序元素按规则分解得到多个分量、再根据每一个分量对元素进行多次箱排序。

对于数字排序问题，基数排序方法先将每一个数字写成以r为基数的按权展开式形式：N= a_n-1*r^n-1+…+a₀*r⁰+a_-1*r^-1+…+a_-m*r^-m，如105.36=1*10²+0*10¹+5*10⁰+3*10^-1+6*10^-2；再按照从低位到高位（即从r^-m开始到r^n-1）的顺序进行n+m次箱排序。例如，对于待排序数字集合R={43.56, 5.63, 3.36, 28.3, 155, 3.36, 22, 3.63}，其基数排序过程如图13所示。

图13  数字排序问题的基数排序过程示例

对于字符串排序问题，基数排序方法按照从后至前的顺序对字符串中的每个字符分别进行箱排序。若待排序字符串中最长的字符串长度为n，则需进行n次箱排序；若某一字符串长度为m（0≤m≤n），则该字符串在前(n-m)次箱排序中对应的字符值为'\0'。例如，对于待排序字符串集合R={"data", "date", "tea", "a", ""}，其基数排序过程如图14所示。

图14  字符串排序问题的基数排序过程示例

基数排序的算法描述如下。

【描述10】  基数排序的算法描述。

参考程序如下：

// 根据A中元素值对R进行箱排序，由基数排序调用

template <class T1, class T2>

void BinSort(T1 R[], int nSize, T2 A[])

{

int nMax=1, nMin=1, nRange, i, j;

LinkQueue<T1> *B = NULL;

// 计算待排序元素的取值范围

for(i=2; i<=nSize; i++)

{

if(A[i] < A[nMin])

nMin = i;

else if(A[i] > A[nMax])

nMax = i;

}

nRange = A[nMax]-A[nMin]+1;

// 根据待排序元素取值范围设置箱子

B = new LinkQueue<T1>[nRange];

if(B==NULL)

exit(1);

// 根据元素值通过入队操作将其装入对应的箱子

for(i=1; i<=nSize; i++)

B[A[i]-A[nMin]].Insert(R[i]);

// 通过出队操作依次从箱子中取出元素并放回到R中

i = 1;

for(j=0; j<nRange; j++)

{

while(!B[j].IsEmpty())

{

B[j].Delete(R[i]);

i++;

}

}

// 释放箱子所占据的空间

delete []B;

}

// 对字符串数组R进行基数排序

void RadixSort(char* R[], int nSize)

{

int nMaxLen=0; // 记录最长字符串的长度

int i, j;

char *A=new char[nSize+1]; // 记录每次用于箱排序的字符值

if(A==NULL)

exit(1);

// 计算最长字符串的长度

for(i=1; i<=nSize; i++)

{

if(nMaxLen<(int)strlen(R[i]))

nMaxLen=(int)strlen(R[i]);

}

// 按照从后至前的顺序进行nMaxLen次箱排序

for(j=nMaxLen; j>=1; j--)

{

// 将用于箱排序的字符值放在A中

for(i=1; i<=nSize; i++)

{

if((int)strlen(R[i])<j)

A[i]='\0';

else

A[i]=R[i][j-1];

}

// 进行一轮箱排序

BinSort(R, nSize, A);

}

delete []A;

}

// 对数字数组R进行基数排序

// nN和nM为整数部分和小数部分的最大长度

template <class T>

void RadixSort(T R[], int nSize, int nN, int nM)

{

int i;

char cFormatN[50], cFormatM[50];

char **S=new char*[nSize+1];

char *cM=new char[nM+3]; // 记录小数部分对应的字符串

if(S==NULL || cM==NULL)

exit(1);

// 将待排序数字先转为字符串以方便处理

sprintf(cFormatN, "%%0%dd", nN);

sprintf(cFormatM, "%%.0%dlf", nM);

for(i=1; i<=nSize; i++)

{

S[i]=new char[nN+nM+2];

if(S[i]==NULL)

exit(1);

sprintf(S[i], cFormatN, (int)R[i]);

if(nM!=0)

{

sprintf(cM, cFormatM, R[i]-(int)R[i]);

strcat(S[i], &cM[1]);

}

}

// 对转换后的字符串数组R进行基数排序

RadixSort(S, nSize);

// 将排序后的结果转换为数字存储到数字数组R中

for(i=1; i<=nSize; i++)

{

R[i] = (T)atof(S[i]);

delete []S[i];

}

delete []S;

delete []cM;

}

基数排序算法的时间复杂度和空间复杂度与元素分解次数d和每次分解得到的分量可能取值的个数rd有关。对于包含n个元素的待排序集合，需进行d轮箱排序，每轮箱排序的时间复杂度为O(n)，因此基数排序算法的时间复杂度为O(d×n)。每轮箱排序中需设置rd个箱子，另外需要设置与待排序元素数量相同的辅助空间来存储装箱的元素，因此空间复杂度为O(n+rd)。与箱排序一样，基数排序也是稳定的。