掌握经典排序算法（类型三）整体局部排序

大家好，欢迎来到IT知识分享网。

1. 前言

本篇内容主要讲第三种排序类型，即整体局部排序法。

整体局部排序法总体步骤如下：

• 对数据分组或分区
• 组内局部排序：实现组内局部有序
• 组间整体排序：实现组间整体有序。

整体局部排序法的第一步是确定分组方案，不同的算法有不同的分组方式。确定分组方案后，有的算法可能会先进行组内排序，再进行组间排序；有的算法可能会先进行组间排序，再进行组内排序。不同算法之间会有细节差异，但总体逻辑基本一致。整体局部排序法更关注通过对数据进行分块分区处理，减少排序次数，提高排序效率。前面文章讨论的两种排序方式则没有考虑到分组分区处理。其实，整体局部排序法可以看作前两种排序方式在维度上的升级，在对数据进行组内排序时，一般会调用前两种排序方式中的排序算法，可以看作包含关系。

2. 相关排序算法

相关经典排序算法有六种，即希尔排序，归并排序，快速排序，桶排序，计数排序，基数排序。

2.1 希尔排序

希尔排序是插入排序的改进版本。它结合了数据分区 + 局部排序，实现了整体排序。

2.1.1 计算过程

现有10个待排序数据如下：

下面演示使用希尔排序实现数据从小到大排列：

• 首先按照每3个数，取一个数的方法，将整个数列分成三个子数列，循环取出，可得到：

• 对取出的每个子数列，进行插入排序，插入排序过程这里不做详细演示，仅列出排序结果：

通过对数据进行分块，此步骤实现了以3为取样间距的子数列排序。将子数列还原回原数列，还原方法就是将上面三个子数列左端对齐，从上向下，从左向右读出数据，排成一列：

可以看出，排序并没有完成，子数列有序，整体并非有序。但相对来说，序列更加有序了。

• 按照每2个数，取一个数的方法，将序列分成两个子序列：

对每个子序列分别进行插入排序，得到排序后的子序列：

通过对数据进行分块，此步骤实现了以2为取样间距的子数列排序。将子数列还原回原数列，得：

同样地，排序并没有完成，子数列有序，整体并非有序，相对来说，序列更加有序了。

• 最后，按照每1个数，取一个数的方法，将序列分成一个子序列，此时的子序列完全等同于整个序列，即： 对其进行插入排序可得：

至此，排序结束。

可见，最后一次排序时，序列已经基本有序，这时候插入排序算法效率很高。

希尔排序的将序列划分成子序列进行排序的根本目的，就是将大规模的问题划分成小规模的问题，多次解决小规模的问题以后，大规模的问题也会得到简化。这正是典型的整体局部类型的排序算法。

值得一提的是，多个小规模问题可以并行处理，可以使用并行计算加速计算过程。

为什么要按照每3步取一个数，每2步取一个数，每1步取一个数来划分子数列呢？其实这只是划分子数列的一种常用方法而已，完全可以采用其他方式划分子数列，也完全可以只划分一次子数列。明白其原理后，我们知道，这些划分和计算过程都是可以控制和调整的，并不是一成不变的。

2.1.2 编码实现

项目地址：

• https://gitee.com/pivotfuture/SortAlgorithm/tree/master/src/shellSort

核心代码如下：

/ * @brief shellSort_array * 希尔排序，实现数组从小到大排序，结果存储在原数组中。 * @param unordered_area 无序区数据指针 * @param data_count 需要排序的数据个数 */ void shellSort_array(int unordered_area[], size_t data_count) { if (data_count < 0) return; // 希尔排序有四层循环： // 第一层：切换步长 // 第二层：遍历当前步长下的分区 // 第三层：插入排序，遍历无序区 // 第四层：插入排序，遍历有序区，插入待排序数据到有序区中 int group_count = 3; // 分组数一般为3 int step = group_count; // 取数步长，即每step个数取一个数，等于组数 for (int currentStep = step; currentStep >= 1; currentStep--) // 切换步长 { for (int k = 0; k < currentStep; k++) // 遍历当前步长下的分区 { // 插入排序，遍历无序区，第一个数不需要排序，直接从第二个数开始遍历 // 这里插入排序采用上一篇文章提到过的精简写法 for (int m = 1; m < data_count; m += currentStep) { // 取一个无序区的待排序数，留下一个空位 int currentValue = unordered_area[m]; // 指向当前空位左边的一个有序区数，用于和当前值比较大小 int prevIndex = m - 1; // 插入排序，从右向左遍历有序区，插入待排序数据到有序区中 while (prevIndex >= 0 && unordered_area[prevIndex] > currentValue) { // 大数右移，相当于空位左移 unordered_area[prevIndex + 1] = unordered_area[prevIndex]; // 索引递减，指向下一个需要比较的数 prevIndex--; } // 将当前数放到空位中 unordered_area[prevIndex + 1] = currentValue; } } } // 打印无序区 qDebug("排序后的数据为:"); for (int j = 0; j < data_count; j++) { printf("%d ", unordered_area[j]); } } 

分组数可以任意取，但分组不易过多。取数步长向1逼近的方案可以有多种，可以每次递减1，也可以每次折半，也可以每次取上次步长的，这些没有固定要求。

希尔排序中的局部排序部分，使用插入排序实现。当然，也可以将插入排序改为我们之前说过的最值法中包含的排序算法，只要能对分区后的子数列排序即可。理解其原理以后，完全独立编写出排序代码不是件难事。

2.1.3 算法特点

希尔排序的主要计算量分布在组内局部排序上，仅在最后一步即当分组数为 1 时执行组间排序。

2.2 归并排序

2.2.1 计算过程

计算过程如下：

1. 数据分组：使用二分法，不断将数列及其子分组从中间一分为二，两个分组的个数可以不完全相等，直到每个分组只包含一个数据为止。
2. 组内排序：因为每个最小组只包含一个数据，所以不需要组内排序。
3. 组间排序：对分组进行组间整体排序，组间排序后，两个组间有序的分组，可以视为一个大分组。之后通过不断对大分组进行组间排序，合并成更大的分组，最终实现整个数列有序。此过程也可以叫做分组合并排序。

2.2.2 编码实现

代码使用Qt实现，项目地址：

• https://gitee.com/pivotfuture/SortAlgorithm/tree/master/src/mergeSort

/ * @brief mergeGroup * 合并两个小分组成大分组，每个分组组内有序。 */ QVector<int> mergeGroup(const QVector<int> leftGroup, const QVector<int> rightGroup) { int leftGroupSize = leftGroup.size(); int rightGroupSize = rightGroup.size(); int dataCount = leftGroupSize + rightGroupSize; QVector<int> bigVector(dataCount); int leftGroupIndex = 0; int rightGroupIndex = 0; // 按顺序取从2个分组中取最小值依次放入合并数组中 for (int i = 0; i < dataCount; i++) { if (leftGroupIndex >= leftGroupSize) { bigVector[i] = rightGroup[rightGroupIndex]; rightGroupIndex++; continue; } if (rightGroupIndex >= rightGroupSize) { bigVector[i] = leftGroup[leftGroupIndex]; leftGroupIndex++; continue; } if (leftGroup[leftGroupIndex] <= rightGroup[rightGroupIndex]) { bigVector[i] = leftGroup[leftGroupIndex]; leftGroupIndex++; } else { bigVector[i] = rightGroup[rightGroupIndex]; rightGroupIndex++; } } return bigVector; } / * @brief mergeSort_array * 采用递归的方式实现归并排序，结果存储在新数组中。原数组中数据不变。 * 递归的缺点在于，如果递归调用太深，可能导致栈溢出。 * @param unordered_area 无序区数据指针 * @param data_count 需要排序的数据个数 */ QVector<int> mergeSort_array(QVector<int> &unordered_data) { // 递归结束条件：分组只包含一个数据时，停止分组 int data_count = unordered_data.size(); if (data_count <= 1) { return unordered_data; } QVector<int> result; // 将数据分组 int boundary = data_count / 2; // 分界线 QVector<int> leftGroup(boundary); // 分界线左边的分组 QVector<int> rightGroup(data_count - boundary); // 分界线右边的分组 // 拷贝分组数据 memcpy(leftGroup.data(), &unordered_data[0], leftGroup.size() * sizeof(int)); memcpy(rightGroup.data(), &unordered_data[boundary], rightGroup.size() * sizeof(int)); // 对每个分组，同样采用归并排序处理 QVector<int> sortedLeftGroup = mergeSort_array(leftGroup); QVector<int> sortedRightGroup = mergeSort_array(rightGroup); // 合并两个子分组成一个大分组 result = mergeGroup(sortedLeftGroup, sortedRightGroup); return result; } 

使用递归实现归并排序的特点是，可能导致函数调用栈溢出。另一种可选的方法是使用循环代替递归，将需要保存的临时数据存放到堆上，可以防止栈溢出。感兴趣的读者可自己尝试。

2.2.3 算法特点

归并排序的主要计算量分布在组间合并排序上。同时算法需要频繁分配内存以及拷贝内存，实际计算效率可能比理论值低。

2.3 快速排序

快速排序是目前公认的一种比较好的排序算法，在很多库中都有实现，如C语言标准库中的qsort函数。

2.3.1 计算过程

快速排序的计算过程仍然符合整体局部排序的三个步骤。以从小到达排序为例：

1. 数据分组：从数组中任意选择一个分界值，将数组分为左右两个分组。
2. 组内局部排序：快速排序不需要局部排序。
3. 组间整体排序：将右侧分组中小于分界数的数移动到分界值左侧，将左侧分组中大于分界值的数移动到分界值右侧。使得总体有序，即：

左侧分组分界值右侧分组

4. 对子分组，进行同样的分组及组间排序操作，直到分组只包含一个数值为止，算法结束。

2.3.2 编码实现

项目地址：

• https://gitee.com/pivotfuture/SortAlgorithm/tree/master/src/quickSort

我们以三种方法实现快速排序法：

• 方法一：中间分界值法 此方法下，我们取数组中间位置的元素作为分界值。代码如下：

/ * @brief quickSort_array_boundary_middle_less_more_alternate * 快速排序，结果存储在原数组中。 * - 分界值取数组中间元素。 * - 根据其计算特点，我们将此实现方式称为：“中间分界法”。 * @param unordered_data 无序区整型数组指针 * @param data_count 需要排序的数据个数 */ void quickSort_array_boundary_middle_less_more_alternate(int unordered_data[], size_t data_count) { // 分组大小为1时，停止对其快速排序。 if (data_count <= 1) return; int boundaryIndex = data_count / 2; int &boundaryValue = unordered_data[boundaryIndex]; int low = 0; int high = data_count - 1; // 初始内存布局为 /* |low boundaryValue high| | 大小值混合区 | 分界值/空位 | 大小值混合区 | */ // 计算过程中内存布局 /* |low high| | 小值区 | 大小值混合区 | 大小值混合区 | 大值区 | */ // 目标内存布局为 /* |low boundaryValue high| | 小值区 | 分界值 | 大值区 | */ // 1. 先将左侧大小值混合区中，大于分界值的数移动到右侧 while (low < high) { bool find = false; while (low < boundaryIndex) { if (unordered_data[low] > boundaryValue) { find = true; break; } else { low++; } } if (!find) { // 左侧混合区没有比分界值大的数，步骤1结束 break; } // 在右侧混合区中找比分界值小的数，二者交换 find = false; int i; for (i = boundaryIndex + 1; i < high; i++) { if (unordered_data[i] < boundaryValue) { find = true; break; } } if (!find) { // 右侧混合区没有比分界值小的数，步骤1结束 break; } qSwap(unordered_data[low], unordered_data[i]); low++; } // 左侧中已没有比分界值大的数，右侧(boundaryIndex~high]之间可能有比分界值小的数 if (low == boundaryIndex) { // 处理右侧部分 // 初始内存布局如下，其中小值区初始为空，low指向大小值混合区的起始位置 / | boundaryValue |low/i high| | 分界值 | 大小值混合区 | / // 计算过程内存布局（两个区）： / | boundaryValue | |low i high| | 分界值 | 小值区 |--> 大小值混合区 | / // 过程内存布局： / | boundaryValue | |low i/high| | 分界值 | 小值区 | 大值区 | / // 目标内存布局： /* | | boundaryValue |low i/high| | 小值区 | 分界值 | 大值区 | */ // 计算过程：从高低值混合区，将所有比分界值小的数放入低值区，不断向右扩展低值区 int high_low = boundaryIndex + 1; for (int i = high_low; i <= high; i++) { if (unordered_data[i] < boundaryValue) { qSwap<int>(unordered_data[i], unordered_data[high_low]); // 向右扩展右侧的低值区 high_low++; } } // 将boundaryValue放到高区的低值区与高值区中间 qSwap<int>(boundaryValue, unordered_data[high_low-1]); // 更新分界值的位置 boundaryIndex = high_low-1; } // 右侧中已没有比分界值小的数，左侧可能有比分界值小的数 else { // 处理左侧部分，原理同上 // 把右侧比分界值小的数放在低地址区，比分界值大的数放在高地址区。 int low_low = 0; for (int i = low_low; i < boundaryIndex; i++) { if (unordered_data[i] < boundaryValue) { qSwap<int>(unordered_data[i], unordered_data[low_low]); // 向右扩展右侧的低值区 low_low++; } } // 将boundaryValue放到高区的低值区与高值区中间 qSwap<int>(boundaryValue, unordered_data[low_low]); // 更新分界值的位置 boundaryIndex = low_low; } // 继续对左右两个分区，进行快速排序 quickSort_array_boundary_middle_less_more_alternate(unordered_data, boundaryIndex); quickSort_array_boundary_middle_less_more_alternate(&unordered_data[boundaryIndex + 1], data_count - boundaryIndex - 1); } 

中间边界值法实现起来十分复杂，正因为边界值在数组中间，导致大小值混合区不连续，从而需要分开处理。

• 方法二：0分界，大小交替空位法 此方法下，我们取数组第0个元素作为分界值，这样大小值混合区是连续的。计算过程中存在三个区，交替从大小值混合区取出小于分界值的数放入小值区，从大小值混合区取出大于分界值的数放入大值区，小值区和大值区从两边向中间交替扩展。代码如下：

/ * @brief quickSort_array_boundary0_less_more_alternate * 快速排序，结果存储在原数组中。 * - 取数组第0个元素作为分界值。 * - 计算过程中存在三个区，交替从大小值混合区取出小于分界值的数放入小值区， * 从大小值混合区取出大于分界值的数放入大值区，小值区和大值区从两边向中间交替扩展 * - 根据其计算特点，我们将此实现方式称为：“0分界，大小交替空位法”。 * @param unordered_data 无序区整型数组指针 * @param data_count 需要排序的数据个数 */ void quickSort_array_boundary0_less_more_alternate(int unordered_data[], size_t data_count) { // 分组大小为1时，停止对其快速排序。 if (data_count <= 1) return; int boundaryIndex = 0; int boundaryValue = unordered_data[boundaryIndex]; int low = 0; int high = data_count - 1; // 初始内存布局如下，其中小值区初始为空，low指向大小值混合区的起始位置 / |low high| |boundaryValue/分界值| | | 空位 | 大小值混合区 | / // 计算过程内存布局（三个区）： /* | |low high| | | 小值区 |--> 大小值混合区 <--| 大值区 | / // 目标内存布局： /* | | boundaryValue | | | 小值区 | 分界值 | 大值区 | / // 计算过程：从大小值混合区轮流取大小值放入大值区和小值区 // 数据移动过程中，始终有一个空位存在 while (low < high) { bool find = false; // 找右侧比分界值小的值 while (low < high) { if (unordered_data[high] < boundaryValue) { find = true; break; } else { high--; } } if (find) { // 将右侧比分界值小的值填入low索引处 unordered_data[low] = unordered_data[high]; low++; // 此时空位在high索引处 } else { // 没找到说明排序完成 break; } // 找比分界值大的值 while (low < high) { if (unordered_data[low] > boundaryValue) { find = true; break; } else { low++; } } if (find) { // 将左侧比中值大的值填入 high 索引处 unordered_data[high] = unordered_data[low]; // 此时空位为 low 索引处 } else { // 没找到说明排序完成 break; } } // 将boundaryValue填到low空位处 unordered_data[low] = boundaryValue; boundaryIndex = low; // 加判断防止无穷递归 if (low > 0 && low < data_count) { // 继续对左右两个分区，进行快速排序 quickSort_array_boundary0_less_more_alternate(unordered_data, boundaryIndex); quickSort_array_boundary0_less_more_alternate(&unordered_data[boundaryIndex + 1], data_count - boundaryIndex - 1); } } 

相对于方法一，这种方法实现起来稍微比较简单些。

• 方法三：0分界，取小交换法 此方法下，我们取数组第0个元素作为分界值，这样大小值混合区是连续的。计算过程中存在两个区，相对于方法二更加简单。从混合区取出小于分界值的数，放入小值区，小值区向右扩展，算法结束时，混合区成为大值区，代码如下：

/ * @brief quickSort_array_boundary0_less_more_alternate * 快速排序，结果存储在原数组中。 * - 取数组第0个元素作为分界值，从混合区取出小于分界值的数，放入小值区， * 小值区向右扩展，算法结束时，混合区成为大值区 * - 根据其计算特点，我将此实现方式称为：“0分界，取小交换法”。 * @param unordered_data 无序区整型数组指针 * @param data_count 需要排序的数据个数 */ void quickSort_array_boundary0_only_less(int unordered_data[], size_t data_count) { // 分组大小为1时，停止对其分组及快速排序。 if (data_count <= 1) return; // 下面几个变量的含义参考下方内存布局示意图 int boundaryIndex = 0; int &boundaryValue = unordered_data[boundaryIndex]; int low = 1; int high = data_count - 1; // 初始内存布局如下，其中小值区初始为空，low指向大小值混合区的起始位置 / | boundaryValue |low/i high| | 分界值 | 大小值混合区 | / // 计算过程内存布局（两个区）： / | boundaryValue | |low i high| | 分界值 | 小值区 |--> 大小值混合区 | / // 过程内存布局： / | boundaryValue | |low i/high| | 分界值 | 小值区 | 大值区 | / // 目标内存布局： / | | boundaryValue |low i/high| | 小值区 | 分界值 | 大值区 | / // 计算过程：从高低值混合区，将所有比分界值小的数放入低值区，不断向右扩展低值区 for (int i = low; i <= high; i++) { if (unordered_data[i] < boundaryValue) { // 交换位置 qSwap<int>(unordered_data[i], unordered_data[low]); // 将低值区向右扩展一个元素 low++; } } // 将boundaryValue放到低值区与高值区中间 qSwap<int>(boundaryValue, unordered_data[low-1]); boundaryIndex = low-1; // 继续对左右两个分区，进行快速排序 quickSort_array_boundary0_only_less(unordered_data, boundaryIndex); quickSort_array_boundary0_only_less(&unordered_data[boundaryIndex+1], data_count - boundaryIndex - 1); } 

方法三不管是逻辑上还是代码实现上都是更加简单。

综上，快速排序有多种实现方式，我们需要重点关注最简单的一种实现方法，即“0分界，取小交换法”。如果我们一定要以数组中间某个数为分界值怎么办？我们可以将要取的分界值和数组的第一个元素交换位置，然后再采用“0分界，取小交换法”即可。

2.3.3 算法特点

快速排序算法的特点是可以用递归实现，当然也可以写成非递归的形式。另外快速排序法实现方式也比较简单，平均执行效率较高。

2.4 计数排序

计数排序是针对整数的一种特殊排序算法，非通用排序算法。

2.4.1 计算过程

• 分组：该算法的核心思想是将待排序的数值视为数组索引值，通过数组索引的方式，将数值直接映射为偏移地址，从而实现不通过数值比较，将相同数值的待排序数分到同一组。
• 组内排序：因为组内数值相同，所以不需要组内排序。
• 组间排序：因为数值大小即代表了偏移地址的大小，所以组间排序由计算机的地址转换硬件自动完成，无须考虑组间排序时间。
• 展开：被分到同一组的数，我们可以使用队列来保存其内容及其相关数据，也可以记录分组内数值的个数（这也是计数排序中计数的含义），这需要根据实际需求来确定。分组内的数据因为映射到了同一个索引处，产生了堆叠，当我们需要得到和待排序数组相同大小的有序数组时，需要将其平铺展开。

计数排序比较简单，这里不做深入解读，直接看代码即可理解。

2.4.2 编码实现

代码采用Qt实现，项目地址：

• https://gitee.com/pivotfuture/SortAlgorithm/tree/master/src/countSort

核心代码如下：

/ * @brief countSort_array * 计数排序，结果存储在原数组中。 * 另外 * @param unordered_area 无序区数据指针 * @param data_count 需要排序的数据个数 * @param min * 待排序值的下限值 * @param max * 待排序数的上限值 */ void countSort_array(int unordered_area[], size_t data_count, int min, int max) { if (data_count < 0) return; int range = max - min + 1; int *newArray = new int[range]; memset(newArray, 0, range * sizeof(int)); // 计数 for (int i = 0; i < data_count; i++) { int value = unordered_area[i]; int offset = value - min; newArray[offset]++; } // 展开 int index = 0; for (int i = 0; i < range; i++) { if (newArray[i] > 0) { for (int k = 0; k < newArray[i]; k++) { unordered_area[index] = i + min; index++; } } } delete []newArray; } 

2.4.3 算法特点

计数排序的特点是一般只能应用于整数排序。而且其排序性能受待排序数的数值范围影响，不适用于数值范围大的场景。典型的使用场景是成绩排序，一般成绩的数值范围不会太大。通常成绩会包含少量小数位，我们可以将成绩值乘以10的n次方，将成绩转换为整数，然后进行计数排序。

计数排序需要申请额外的内存。这相当于增加了空间复杂度，降低了时间复杂度。

计数排序将数值直接映射为地址，每个地址代表一个分组，这个过程可以用一个函数简单表示：

可见，计数排序数值的分组和数值成一次函数正比关系。正比关系下，组与组之间可能会有很多空位，这会浪费大量内存，这也是计数排序不适用于大数值范围排序的原因。

2.5 桶排序

桶排序是计数排序是升级版，它和计数排序原理类似。桶排序是使用自定义函数，实现数值到分组的映射。

2.5.1 计算过程

• 分组：使用自定义函数，实现数值到分组的映射。
• 组内排序：分组后，组内是乱序的，需要进行组内排序，这一点和计数排序有所不同。
• 组间排序：使用自定义函数将数值映射到指定的分组中，分组号与数值之间成正比关系，组间排序会在数值映射到分组号过程中自动进行，无须进行比较运算。因为将待排序数放到桶中，需要为桶单独分配内存，所以桶的本质是用增加空间复杂度为代价降低时间复杂度。

2.5.2 编码实现

算法使用Qt实现，项目地址：

• https://gitee.com/pivotfuture/SortAlgorithm/tree/master/src/bucketSort

核心代码如下：

/ * @brief insertSort * 插入排序 * @param unordered_area * @param data_count */ void insertSort(int unordered_area[], size_t data_count) { for (int i = 0; i < data_count; i++) { int currentUnorderedValue = unordered_area[i]; // 当前未排序数 int k = i; while (k > 0) { int prevIndex = k - 1; if (unordered_area[prevIndex] > currentUnorderedValue) { unordered_area[k] = unordered_area[prevIndex]; k--; } else { break; } } // 最后一个空位填入当前值 unordered_area[k] = currentUnorderedValue; } } / * @brief bucketSort_array * 使用c++实现桶排序，结果存储在原数组中。 * 使用c语言需要借助链表实现。 * @param unordered_area 无序区数据指针 * @param data_count 需要排序的数据个数 * @param min 待排序数下限值 * @param max 待排序数上限值 * @param bucketCount 桶个数 */ void bucketSort_array(int unordered_area[], size_t data_count, int min, int max, int bucketCount) { if (data_count < 0) return; QVector<QVector<int> > buckets(bucketCount); int range = max - min + 1; // 遍历待排序数，放入桶中 for (int i = 0; i < data_count; i++) { // 待排序数 int &value = unordered_area[i]; // 桶索引 int bucketIndex = (value - min) * bucketCount / range; // 将待排序数放入桶中 QVector<int> &bucket = buckets[bucketIndex]; bucket.append(value); } // 对每个桶进行插入排序，当然可以使用其他排序方式 foreach (const QVector<int> &bucket, buckets) { // 调用插入排序算法 insertSort((int *)bucket.data(), bucket.size()); } // 顺序展开所有桶中的数据 int index = 0; foreach (const QVector<int> &bucket, buckets) { foreach (int value, bucket) { unordered_area[index] = value; index++; } } } 

2.5.3 算法特点

桶排序使用线性映射函数，将被排序数均匀分布到少数几个桶中，减少了内存资源的浪费。每个桶就是一个分组。由于桶个数的减少，每个桶中包含的数据是不同的，而且是乱序的，需要进行组内排序，组内排序可以调用任何一种已知排序算法完成排序。最后，按顺序展开所有桶得到有序序列。

2.6 基数排序

基数排序也是基于桶实现的。基数排序的桶映射方式不同于桶排序，基数排序根据待排序数值的十进制数每个位上的数值，将数值放入每个位置上可能的值组成的n个桶中。

2.6.1 计算过程

• 分组：将待排序数的十进制形式的每一位取出，对于非负整数，放入0~9十个桶中；对于全体整数，放入 十九个桶中。
• 组内排序：不需要组内排序。
• 组间排序：组间排序在分配桶时进行。但是组内排序是按十进制位完成的，并不是一次完成的。一般十进制有多位，需要多次进行桶的分配和还原过程才能完成最终排序。

2.6.2 编码实现

这里我们实现了支持全体整数排序的基数排序算法，也就是说支持负数，零，正数混合数列的排序。 项目使用Qt实现，地址：

• https://gitee.com/pivotfuture/SortAlgorithm/tree/master/src/radixSort

核心代码如下：

/ * @brief maxbit * 求出待排序数的最大十进制位数 * @param data * @param n * @return */ int maxbit(int data[], int n) { // 先求出最大数和最小数 int max = data[0]; int min = max; for (int i = 1; i < n; ++i) { if (max < data[i]) max = data[i]; if (min > data[i]) min = data[i]; } // 再求其十进制位数 int decimalCount = 1; // 最大十进制位数 int base = 10; // 进制 if (max < 0) { max = -max; } while (max >= base) { max /= base; ++decimalCount; } return decimalCount; } / * @brief radixSort_array * 基数排序，结果存储在原数组中。 * @param unordered_area 无序区数据指针 * @param data_count 需要排序的数据个数 */ void radixSort_array(int unordered_area[], size_t data_count) { if (data_count < 0) return; int decimal_count = maxbit(unordered_area, data_count); // 十进制最大位数 int bucket_count = 19; // 桶数，桶为：-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9 QVector<QVector<int> > buckets(bucket_count); // 桶集合 for(int i = 0; i < decimal_count; i++) //进行decimalCount次排序 { int radix = pow(10, i); // 0号为符号位 // 遍历所有待排序数据，放入桶中 for (int k = 0; k < data_count; k++) { int value = unordered_area[k]; int bucketIndex = 0; if (value < 0) { // 计算桶索引，这里需要自己数一下 bucketIndex = 9 - (-value / radix) % 10; } else { // 计算桶索引，这里需要自己数一下 bucketIndex = 9 + (value / radix) % 10; } buckets[bucketIndex].append(value); } // 还原桶 int index = 0; for (int m = 0; m < bucket_count; m++) { QVector<int> &bucket = buckets[m]; foreach (int value, bucket) { unordered_area[index] = value; index++; } // 清空桶内数据 bucket.clear(); } } } 

这里重点在于对于负数的排序，采用了负数桶的设计。

2.6.3 算法特点

基数排序可定制性很强，使用中可根据实际需求加以修改。基数排序更像是一种基于ASCII码逐位比较的排序算法，它不仅可以用于整数排序，也可以用于字符串排序等其他排序场合，读者可以根据其原理，设计桶的映射关系，发掘其更多用法。

3. 结语

限于篇幅，关于算法复杂度计算，我们这里就不做讲解。在理解算法原理的基础上，查阅相关文献可以快速理解。

至此，十大经典排序算法已基本研究完成。算法本身并不困难，困难的是把算法讲明白。任何一个事物都有多种观察视角，会衍生出多种理解方式。我们不需要迷信所谓“权威“的讲解，事物本身的模样才是真正的权威，我们需要积极地从本质视角审察事物，理解事物，把握本质才能掌握真理，才能从根本上解决问题。

本文原创发布于Qt未来工程师，关注获取更多技术解析，让技术回归本质。