排序算法

本文为数据结构与算法之美-王争的学习笔记，如需查看完整内容，请参考链接。

这篇关于排序算法的笔记写了好久，中间事情也比较多，导致写到最后的桶排序时，前面的一些细节忘了好多。

在众多排序算法中，最经典的有以下几种：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。按照时间复杂度可以划分为以下几类：

由上表可知，冒泡排序和插入排序的时间复杂度都是$O(n^2)$，但在实际工程中更倾向于使用插入排序，这是为什么？

如何分析一个排序算法？

分析一个排序算法要从那几个方面入手？

排序算法的执行效率

最好情况、最坏情况和平均情况时间复杂度

我们在分析排序算法时，要给出排序算法的最好情况、最坏情况和平均情况时间复杂度，并说明各个情况对应的要排序的原始数据是什么情况。

这样做的原因在于：1. 有些排序算法会区分；2. 要排序的数据中，有些接近有序，有些完全无序，我们需要直到算法在不同数据情况下的表现。

时间复杂度的系数、常数和低阶

我们在分析时间复杂度时会假设数据的规模非常大，此时便可以忽略时间复杂度中的系数、常数和低阶。但在实际工程中，需要处理的数据一般很小，此时系数、常数和低阶就无法直接忽略。

比较和交换次数

对于基于比较的排序算法来说，会涉及两种基本的操作：比较和交换。因而，我们在分析排序算法时需要对算法的比较和交换次数进行考虑。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度进行度量，但针对排序算法的空间复杂度分析，引入了一个新的概念：原地排序（Sorted in place）。原地排序算法指的是空间复杂度为$O(1)$的排序算法。

排序算法的稳定性

排序算法的稳定性指的是：当待排序的数据中存在相等的数据时，经过排序之后，相等元素之间原有的先后顺序是否不变。

例如，现在有一组数据：2，9，3，4，8，3，按照大小排序后为：2，3，4，8，9。在这组数据中有两个3，经过某种排序算法之后，如果两个3的前后顺序没有改变，就将这种排序算法称为稳定的排序算法；如果前后顺序发生变化，就将这种排序算法称为不稳定的排序算法。

当待排序的对象为整数时，这一性质似乎没有用。但在实际工程中，待排序的数据往往是具体的对象，对象之间的大小按照某一准则决定。

例如，有一组订单，有金额和下单时间两个性质。我们希望按照金额大小从小到大进行排序，对于金额相同的订单，按照下单时间从早到晚排序。有以下两个思路：

先将订单按照金额大小进行排序，再对每一个金额相同的小区间按照下单时间进行排序。实际上，这种排序算法在实现时复杂度较高。
先将订单按照下单时间进行排序，再使用稳定性排序算法按照金额大小进行排序。稳定性排序后，订单首先满足金额从小到大，接着由于具有稳定性，具有相同金额的订单会维持原有的顺序（下单时间）。

冒泡排序（Bubble Sort）

冒泡排序的操作对象是相邻的两个元素。每一次冒泡操作会对相邻的两个元素进行比较，看是否满足大小要求。如果不满足，就将两个元素交换。一次冒泡至少会让一个元素移动到它应该在的位置，重复n次，就会完成n个数据的排序工作。

以数据4，5，6，3，2，1为例，从小到大进行排序，第一次排序过程如下图：

在一次排序操作后，6被正确归位。将这一操作重复6次便可完成排序操作。

实际上，当某次冒泡操作未进行数据交换时，说明已经完成排序操作，便可以跳过接下来的操作。

代码

#include <vector>
#include <iostream>
using namespace std;

vector<int> bubble_sort(vector<int> array){
    // 是否有数据交换
    for (int i=0; i<array.size(); i++){
        bool flag=false;
        // 顶部存放的是已经归位的元素，因而每次交换时跳过顶部的元素
        for (int j=0; j<array.size()-i-1; j++){
            if (array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = true;
            }
        }
        // 当前迭代没有数据交换，则跳出
        if (!flag)
            break;
    }
    return array;
}

冒泡排序算法是原地排序算法，是稳定的排序算法。

冒泡排序时间复杂度

最好情况下，数组已经是有序的，只需要进行一次冒泡操作，时间复杂度为$O(n)$；最坏情况下，数组完全无序（倒序），需要进行n次冒泡操作，时间复杂度为$O(n)^2$。

因为对于一个数组，其中的元素的排列情况有很多种，而不同的排列情况算法执行的时间肯定不同。为了避免复杂的数学分析，引入“有序度”和“逆序度”两个概念。

有序度指数组中具有有序关系的元素对的个数。

一个倒序排列的数组的有序度就是0，一个完全有序的数组的有序度就是$n*(n-1)/2$，即满有序度。

逆序度有有序度的定义刚好相反，存在这么一种关系：逆序度=满有序度-有序度。排序的过程就是提升有序度，降低逆序度的过程。

以数组4,5,6,3,2,1为例，有序度为3，排序后，满序度为15。

冒泡排序中有两个操作原子，比较和交换。每进行依次交换操作，有序度加1。无论如何改进算法，都要进行逆序度次交换操作，即$n*(n-1)/2$-初始有序度。

对于包含n个数据的数组，最坏情况下，初始有序度为0，要进行$n(n-1)/2$次交换操作；最好时不用进行交换操作。以中间情况为例$n(n-1)/4$，假设这种情况为中间情况。那么，平均情况下，需要进行$n(n-1)/4$次交换操作，比较操作多于或等于交换操作，复杂度上限为$O(n)^2$，因而平均复杂度为$O(n)^2$。

插入排序

对于一个有序的数组，为了在插入了新的数据后仍旧保持原数组的有序，我们需要把新的数组插入到正确的位置。

插入排序算法便是借鉴这一思想，对于一组待排序的数组，插入排序算法会维持两个区间：已排序区间和待排序区间。刚开始时，已排序区间中只有一个元素（数组的第一个元素）；接着，依次从待排序区间取数据，将其插入到已排序区间的合适位置，保证已排序区间一直有序；重复该过程，直到待排序区间中没有元素。

上图中，左侧为已排序区间，右侧为待排序区间。

插入排序同样包含两种操作，一种是元素的比较，一种是元素的移动。对于待插入元素a，要将其于已排序区间中的元素依次进行比较，找到合适的插入位置；接着将插入位置后的元素向后顺序移动一位，再将元素插入。

对于不同的查找方法（从前往后和从后往前），元素的比较次数有区别。但对于同一个给定的初始序列，移动操作的次数固定，等于逆序度。

代码

// 插入排序（从小到大排序）
vector<int> insert_sort(vector<int> array){
    for (int i=1; i<array.size(); i++){
        int temp = array[i];
        for (int j=0; j<i; j++){
            // 找到合适的插入位置(第一个比当前元素大的元素)，则将插入位置后的元素都后移
            if (array[i] < array[j]){
                for (int move_index=i; move_index>j+1; move_index--){
                    array[move_index] = array[move_index-1];
                }
                array[j] = temp;
                break;
            }
        }
    }
    return array;
}

插入排序算法是原地排序算法，是稳定的排序算法。

插入排序时间复杂度

最好情况下的时间复杂度，当数组是完全有序时，在每次插入操作时，从后往前进行查找，那么只需一次比较操作便可以找到正确的位置，因而最好时间复杂度为$O(n)$。

最坏情况下的时间复杂度，当数组是完全逆序时，在每次插入操作时都要移动数组的第一个位置后面的所有元素，因而时间复杂度为$O(n^2)$。

平均时间复杂度，对一个数组进行插入操作的平均时间复杂度为$O(n)$，每一次插入操作都相当于向一个数组中插入元素，因而平均时间复杂度为$O(n^2)$。

选择排序

选择排序同样将数组划分为两部分，每一从待排数组中选出最小的元素放在已排序数组的末尾。如下图所示：

选择排序未使用额外的存储空间，因而空间复杂度为$O(1)$。其最好、最坏和平均时间复杂度都是$O(n^2)$。选择排序算法不是稳定的算法，因为每次交换待排数组中的最小值时会破坏原始数据的顺序。

代码

// 选择排序
vector<int> selection_sort(vector<int> array){
    for(int i=0; i<array.size(); i++){
        int min = 10000;
        int min_index;
        // 找出未排序数组中的最小值和其对应的下标
        for(int j=i; j<array.size(); j++){
            if (array[j] < min) {
                min = array[j];
                min_index = j;
            }
        }
        int temp = array[i];
        array[i] = min;
        array[min_index] = temp;
    }
    return array;
}

为什么选择插入排序？

在冒泡排序和插入排序的代码中，冒泡排序需要进行逆序度次数据交换操作，同样插入排序需要逆序度次数据移动操作。但是一次交换操作需要三步，而一次移动操作只需要一步。因而，虽然时间复杂度都是$O(n^2)$，但是在实际情况下，数据量较大时，插入排序优于冒泡排序。

上述三个排序算法的时间复杂度都是$O(n^2)$，适用于处理小规模的数据。在处理较大规模的数据时就需要用到接下来的两种时间复杂度为$O(nlogn)$的排序算法：归并排序和快速排序。

归并排序

归并排序和快速排序都用到了分治的思想，其中归并排序的思想是：如果要排序一个数组，可以将该数组划分为前后两个部分，再对两个部分分别进行排序，最后再将两个部分进行合并。如下图所示：

所谓分治就是将大的问题分解为小的问题，小的问题被解决后，大的问题自然就被解决。分治的思想和递归的思想很相似，都是将问题进行拆分。因而自然可以使用递归来实现归并排序。

归并排序的递归代码的递推公式为：

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

简单来说，就是分别对数组的两部分进行归并排序，再将排好序的两部分进行合并。

在编写合并代码时，有一个重要的前提条件是，此时两部分都是有序的，并且最终合并得到的数组也得是有序的。我们可以使用交替比较的方式进行合并：

首先分别从两部分数组中取出第$i,j$个元素，比较$part1[i]$和$part2[j]$的大小，将两者中小的那个放入临时数组中，假设$part1[i]<part2[j]$，就$part1[i]$放入临时数组中；
再从$part1$中取出下一个元素，与$part2[j]$比较大小，将较小的那个元素放入临时数组中。
重复这一过程，直到两个数组中有一个数组都被放入临时数组中，最后将另一个未遍历完的数组的剩余部分放到临时数组的尾部即可。

代码

代码实现如下：

// 归并排序
vector<int> merge(vector<int> part1, vector<int> part2){
    /*
     * 将两个有序数组合并为有序数组
     * */
    int part1_index = 0;
    int part2_index = 0;
    vector<int> merge_array;
    while(part1_index < part1.size() && part2_index < part2.size()){
        int num1 = part1[part1_index];
        int num2 = part2[part2_index];
        // 将两者中较小的一个放入合并数组中
        if (num1 < num2 || num1 == num2){
            merge_array.push_back(num1);
            part1_index++;
        } else{
            merge_array.push_back(num2);
            part2_index++;
        }
    }
    // 将剩余的部分放入合并数组中
    if (part1_index == part1.size()){
        auto start = part2.begin() + part2_index;
        merge_array.insert(merge_array.end(), start, part2.end());
    } else{
        auto start = part1.begin() + part1_index;
        merge_array.insert(merge_array.end(), start, part1.end());
    }
    return merge_array;
}


// 归并排序
vector<int> merge_sort(vector<int> unsorted_array){
    if (unsorted_array.size() == 1){
        return unsorted_array;
    }
    vector<int> part1, part2;
    part1.assign(unsorted_array.begin(), unsorted_array.begin()+unsorted_array.size()/2);
    part2.assign(unsorted_array.begin()+unsorted_array.size()/2, unsorted_array.end());

    part1 = merge_sort(part1);
    part2 = merge_sort(part2);
    return merge(part1, part2);
}

归并排序是不是稳定的算法？归并排序是不是稳定的算法主要取决于merge()函数，当遇到两个相同的值时，如果将左侧的元素先放入合并数组中，那么归并排序就是稳定的算法。

归并排序时间复杂度

归并排序是使用递归的方法实现的，分析递归算法的复杂度时会比较复杂。

递归的思想就是将一个复杂的问题分解为多个子问题进行求解，等子问题求解完成后，再将子问题的结果进行合并。如果定义求解问题a的时间为T(a)，求解问题b、c的时间分别为T(b)和T(c)。其中，问题a可以被分解为b和c。那么：

1	T(a) = T(b) + T(c) + K

其中，k对应合并两个子问题时耗费的时间。也就是说：

不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。

对于归并排序，假设对n个元素进行归并排序所学的时间为T(n)，那么分解为两个子数组排序的时间是T(n/2)。merge()函数合并两个有序数组的时间复杂度为$O(n)$。那么，套用公式，归并排序的时间复杂度的计算公式为：

1 2	T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。 T(n) = 2*T(n/2) + n； n>1

对上述公式进行分解：

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

可以将上述的$k$看作二分的次数，最终得到：

$T(n)=2^k*T(\frac{n}{2^k})+k*n$

令：$\frac{n}{2^k}=1$，得到$k=log_2n$，代回上式得到：

$T(n)=n*T(1)+n*log_2n \\ T(n)=Cn+nlog_2n$

使用大$O$表示法，时间复杂度为$O(nlogn)$。

归并排序的执行效率与要排序的原始数组的有序程度无关，因而时间复杂度非常稳定。最好、最坏和平均时间复杂度都是$O(nlogn)$。

归并排序的时间复杂度很好，但在空间复杂度方面，该算法不是原地排序算法。我们在执行合并函数时，需要开辟额外的数组存放合并后的数据，之前的三种排序算法都不需要使用额外的空间。

在进行归并排序的空间复杂度分析时，我们无法使用上述分析时间复杂度的方法。时间复杂度中，各个子数组的运算时间是可以累加的，但对于空间来说，当一个子数组运算完后，该子数组开辟的空间便会被释放，在任何一个时刻，只会有一个数组占用额外的合并空间，临时存储空间不会超过最大的数组的内存大小n，因而空间复杂度为$O(n)$。

快速排序

与归并排序类似，快速排序也使用了分治的思想。快速排序的思想如下：

从数组中任意选取一个数值，将数组中比该数组小的元素都放在该数值的左侧，比该数组大的元素都放在该数值的右侧。这样一来数组就被划分为两个部分，接着继续对左右两部分数组使用快速排序，直到数组的区间缩小为1，返回。

分区的思想如下图所示：

将算法的思想用公式表述，如下：

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

在归并排序中比较重要的操作是merge()函数，而在快速排序中，比较重要的操作就是分区操作。

分区操作简单的实现方式就是，分别维持两个数组，将待分区数组中的元素依次与分区点元素进行比较，大的元素放到一个数组，小的元素放到另一个数组。但是这样一来，每次进行分区操作时都要分配额外的内存空间，进而导致快速排序算法不是原地排序算法。

那么如何实现在原始数组空间上进行分区操作？在选择排序中，我们使用交换的方法将未排序区间中的最小值和未排序区间中的首位值进行交换，以达到将最小值插入已排序数组的目的。这里，我们同样可以借助交换的思想，在原始数组中维持两个部分，左侧为偏小的值的区间。

对于未比较的元素，将其与分区点处的值进行比较，如果小或等于分区点，就将其交换到偏小的值的区间。因而，在实际程序实现时，我们需要使用一个下标$i$指示偏小值的区间的范围，另一个下标$j$指示当前遍历到的元素的位置。如下图所示：

代码

// 快速排序
int separate_partition(vector<int>& unsorted_array, int start_index, int end_index){
    // 注意unsorted_array需要使用引用的方式，因为需要在分区函数中改变数组元素的位置
    int separate_point = unsorted_array[end_index];
    int separate_index = start_index;
    for (int j = start_index; j<end_index; j++){
        // 如果当前值小于或等于分区值，则将当前值交换到已整理区间，已整理区间的下标前移
        if (unsorted_array[j] < separate_point){
            swap_numbers(unsorted_array[separate_index], unsorted_array[j]);
            separate_index++;
        }
    }
    swap_numbers(unsorted_array[end_index], unsorted_array[separate_index]);
    return separate_index;
}


void sub_quick_sort(vector<int> &unsorted_array, int start_index, int end_index){
    if (start_index > end_index || start_index == end_index)
        return;
    // 划分分区
    int separate_index = separate_partition(unsorted_array, start_index, end_index);
    // 对较小值和较大值区间分别排序
    sub_quick_sort(unsorted_array, start_index, separate_index-1);
    sub_quick_sort(unsorted_array, separate_index+1, end_index);
}


vector<int> quick_sort(vector<int> unsorted_array){
    sub_quick_sort(unsorted_array, 0, unsorted_array.size()-1);
    return unsorted_array;
}

在编写快排的代码时，要特别注意值传递的方式（因为要在函数内部改变数组的元素位置，所以应该使用引用进行值传递）。除此之外，要注意分区代码的书写，以及区间索引的计算。

归并排序和快速排序的差别

从两个排序算法的思想上我们可以看出，归并排序是一种自下而上的排序方法，将未排序数组迭代拆分为两个部分，在对两个部分进行排序，接着使用合并函数将两部分合并为有序的数组；而快速排序是一种自上而下的排序方法，首先将未排序数组依据分区点划分为宏观有序的两个部分，接着再对两个部分依次进行划分，最后每一个小部分都有序，原始数组也就有序。两种排序算法的对比如下：

归并排序自下而上的排序方法导致其必须再合并函数中使用额外的数组进行合并，是一种非原地的排序算法；而再快速排序算法中，经过特殊设计的分区函数可以再原地完成划分，是一种原地排序算法，占用的内存更少。

快速排序的性能

快排同样是递归操作，如果每次进行分区时都能够将数组划分为大小相同的两个子数组，那么其时间复杂度的计算公式和归并排序相同。

1 2	T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。 T(n) = 2*T(n/2) + n； n>1

进而时间复杂度为$O(nlogn)$。

但是并不是每一次划分都能够将数组划分为大小相同的两个部分。假设每次分区操作都将区间分成大小为$9:1$的区间。那么递归时间复杂度公式为：

1
2
3

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。

T(n) = T(n/10) + T(9*n/10) + n； n>1

该递归公式的求解方式比较复杂，再原文中作者未讲明，只是给出了：

快速排序在大部分情况下的时间复杂度都是$O(nlogn)$，只有极端情况下才是$O(n^2)$。

问题思考

有10个接口访问日志文件，每个日志文件约300MB，每个文件里的日志都按照时间戳从小到大进行排序。要求将这10个日志文件合并为一个日志文件，合并后的日志仍然按照时间戳从小到大进行排序。限定处理该任务的机器只有1Gb内存，如何“快速”将这10个日志文件合并？

解决这个问题可以借助归并排序中合并函数的做法，在合并函数中依次取两个子数组中的值，将较小的一个值放入合并数组中，再从较小的值对应的子数组中取下一个值，与上一次的残留值进行比较，较小的继续放入合并数组中。将上述过程交替进行即可得到最终的合并数组。

在本问题中有内存的限制，意味着我们无法以下把所有文件都读入到内存中。因而，我们可以借助合并函数的思想，一次分别从10个日志文件中读入10条日志，将这10条日志中最小的那个日志写入文件中，接着从最小的日志的文件中读入下一个数据，与剩余的9条数据进行比较选出最小值写入文件中。接着再读入一条数据，迭代进行上述步骤，直到有九个文件中的数据依次被读完，将剩余的一个文件中的剩余数据写入到合并文件的尾部即可。

桶排序

上面几个排序算法的时间复杂度要么是$O(n^2)$，要么是$O(nlogn)$，都是非线性的排序算法，接下来将了解几种线性排序算法。

所谓桶排序，就是借助“桶”进行排序，核心思想是将要排序的数据分到几个有序的桶里，再对每个桶里的数据单独进行排序，最后，将每个桶里的数据按照顺序取出，得到的序列就是有序的。

时间复杂度分析

假设要排序的数据有n个，将其平均划分到m个桶内，每个桶中有k-n/m个元素，对每个桶中的数据使用快速排序，时间复杂度为$O(klogk)$。m个桶排序的时间复杂度就是$O(mklogk)$，代入k=n/m，那么桶排序的时间复杂度为$O(n*log(n/m))$，当所使用的桶的数目接近数据个数n时，$log(n/m)$就会非常小，此时桶排序的时间复杂度就是$O(n)$。

通过上述分析过程，我们会发现有很多限制，

首先需要待排序的数据能够恰好被平均划分到m个桶中；
桶与桶之间存在一定的大小顺序，这样桶内排序完成后不需要对桶之间进行排序；
桶与桶之间的数据分布比较均匀，如果数据分布非常不均匀，桶与桶之间的排序时间复杂度相差就会非常大，极端情况下，所有的数据全部集中在单个桶中，此时如果使用快排进行桶内排序，总体的时间复杂度就是$O(nlogn)$。

桶排序适用于外部排序，即数据存储在外部磁盘中，数据量比较大，无法全部加载到内存中。

例如，有10GB的订单数据，希望按照订单金额（正整数）进行排序，内存有限，应该怎么办？

可以对文件进行扫描，按照订单大小范围将订单存放到100个桶中，这100个桶之间是有序的，比如第一个桶存放金额在1到1000元之间的订单，第二个桶存放1001到2000元之间的订单。每一个桶对应一个文件，按照金额范围的大小顺序给文件命名（00,01,02，…，99）。

如果订单分布均匀，就可以得到100个大小为100MB的文件，依次将这些文件加载到内存中，进行排序，完成排序后，按照文件顺序合并为一个文件即可。

当订单分布不均匀时，可以继续对订单数据较多的文件进行划分，直到所有文件都能被读入内存中。

计数排序

计数排序是桶排序的特例，当要排序的数据所处的范围不大时，假设最大值是k，便可以将数据划分到k个桶中，桶内的数据值相同，就不需要进行桶内排序。

需要做的就是，对数据进行两次遍历，第一次将数据放入对应的桶中，第二次遍历所有桶，依次取出放入到另一个数组中即可。因而，时间复杂度为$O(n)$。

那么，为什么称为“计数排序”？

假设有大小从0到5的数据，使用大小为6的数组表示桶，下标对应值，存储的元素为当前值的个数，对所有数据进行遍历便可以得到每一个下标对应的值的元素个数：

依据上述数组可以得到值为3的元素有3个，小于3的元素有4个，因而值为3的元素在排序后的数组中占的下标为4、5、6。

那么如何得到每个元素在排序后的数组中的位置呢？可以对C[6]数组进行累积求和，得到如下数组：

数组中的元素表示小于等于下标对应的值的元素个数。接从后往前（可以保证稳定性，从前往后不能保证稳定性）对原始数组进行扫描，当数值为3时，从上个数组中得到小于等于3的元素的个数，此时为7，则将3填入第7个位置，即下标为6，接着将C[3]的值减1。接着对剩下的元素依次执行上述过程，扫描完整个数组便可以得到最终的有序数组：

整个过程对原始数组进行了两次扫描，第一次扫描得到各个值的个数，第二次扫描将各个值填入其对应的位置；除此之外，对计数数组进行了三次遍历，第一次填入值个数，第二次计算累积个数，第三次依据值个数将原始数据的各个元素填入排序数组中，因而时间复杂度为$O(n)$。

计数排序最重要的思想便是使用一个数组来对原始数组中的元素的数目进行计数，按照元素的大小顺序依次记录其对应的个数。

计数排序只适用于数据范围不大的情况，如果数据的范围k比要排序的数据n大的多，就不适合使用计数排序。

计数排序只适用于非负整数（数要被用作计数数组的下标），如果要排序的数据是其它类型，要将其在不改变相对大小的情况下转换为非负整数。

基数排序

那么当待排序数组中的数据的范围过大时，有没有时间复杂度为$O(n)$的算法？

假设现在有十万个手机号码，要对这些手机号码从小到大进行排序。这个问题有这样的规律，如果在前几位号码中，一个手机号码已经大于另一个手机号码，就不需要比较后续的几位。

可以采用下面的思路，先按照最后一位进行排序，再按照倒数第二位进行排序，以此类推直到第一位。以字符串排序为例，基数排序的思路如下所示：

为了保证基数排序算法的有效性，每一位排序所采用的算法需要是稳定的，也就是说再对高位进行排序时，不能打乱低位的有序性。

通过使用基数排序，在对每一位进行排序时，所要处理的数据的范围将会很小，此时就可以借助桶排序或者计数排序实现单个位的排序。单个位的排序是$O(n)$，这样当原始数据的位数较少时，基数排序算法的时间复杂度就是$O(n)$，属于线性排序算法。

当待排序的数据并不是等长时，可以采取高位补零的方法将数据变为等长后，再使用基数排序算法。

基数排序对数据有要求：

需要可以分割出独立的“位”来比较，位之间有递进关系，高位大，则原始数据大。

每一位的范围不能太大，要可以使用线性算法进行排序。

桶排序、计数排序和基数排序都对数据有着较为严格的要求，应用不广泛。通排序和计数排序的排序思路很相似，都是针对范围不大的数据，将数据划分成不同的桶来实现排序。基数排序需要数据能够划分为高低位，并且高低位之间存在递进关系，且每一位的数据范围不能太大。

参考

王争-数据结构与算法之美