十大经典算法详解

本文整理十种常见排序算法，围绕时间复杂度、空间复杂度、稳定性、核心思路与适用边界展开。重点不只在于记住结论，更在于理解这些算法为何会得到对应的复杂度，以及在工程实践中适合处理什么样的数据分布。

冒泡、选择、插入、希尔属于基础内部排序；归并、快速、堆排序体现了分治与堆结构的典型思路；计数、桶、基数排序则展示了非比较排序在特定约束下的线性时间优势。文中参考了若干资料，其中包含这篇排序算法综述。

[TOC]

总览

算法	最好时间	平均/典型时间	最坏时间	额外空间	稳定性	适用特点
冒泡排序	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`	稳定	适合教学与近乎有序的小规模数据
选择排序	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`	不稳定	交换次数少，但整体效率低
插入排序	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`	稳定	小规模、局部有序数据表现较好
希尔排序	与增量序列相关	与增量序列相关	常见写法最坏 `O(n^2)`	`O(1)`	不稳定	插入排序的分组改进版
归并排序	`O(nlogn)`	`O(nlogn)`	`O(nlogn)`	`O(n)`	稳定	时间复杂度稳定，适合链表与外部排序
快速排序	`O(nlogn)`	`O(nlogn)`	`O(n^2)`	平均 `O(logn)`	不稳定	工程中常用，常数因子小
堆排序	`O(nlogn)`	`O(nlogn)`	`O(nlogn)`	`O(1)`	不稳定	原地排序，适合需要严格上界的场景
计数排序	`O(n + k)`	`O(n + k)`	`O(n + k)`	`O(k)`	标准实现可稳定	适合整数范围较小的场景
桶排序	`O(n + k)`	`O(n + k)`	`O(n^2)`	`O(n + k)`	取决于桶内排序	适合分布较均匀的数据
基数排序	`O(n * k)`	`O(n * k)`	`O(n * k)`	`O(n + k)`	稳定	适合位数有限的整数或字符串

从选型角度看，比较类排序的下界通常无法突破 O(nlogn)；如果已知键值范围有限、位数有限或分布较均匀，则可以利用非比较排序换取更低的时间复杂度，但前提是接受额外空间和更强的数据约束。

冒泡排序

时间复杂度O(n^2)，空间复杂度O(1)，稳定。

从头开始，每次两个相邻的元素，若大者在前，则交换两元素直至数组末尾此时最大元素为数组最后的元素重复以上步骤，从头开始至上一轮比较的末尾元素；

public static void bubbleSort(int[] array) {
    if (array.length < 2) {
        return;
    }
    // 每轮询一遍，都将最大的元素移到最后一位，所以end--
    for (int end = array.length - 1; end > 0; end--) {
        // 每次都从数组的第一位开始遍历
        for (int i = 0; i < end; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
            }
        }
    }
}

数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的设置标志位，防止后面不必要的遍历

 public static void bubbleSort2(int[] array) {
    if (array.length < 2) {
        return;
    }
    // 每轮询一遍，都将最大的元素移到最后一位，所以end--
    for (int end = array.length - 1; end > 0; end--) {
        // 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
        boolean ixExchanged = false;
        // 每次都从数组的第一位开始遍历
        for (int i = 0; i < end; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                ixExchanged = true;
            }
        }
        if (!ixExchanged) {
            break;
        }
    }
}

/**
 * 交换元素位置
 *
 * @param array
 * @param index
 * @param nextIndex
*/
private static void swap(int[] array, int index, int nextIndex) {
    int temp = array[index];
    array[index] = array[nextIndex];
    array[nextIndex] = temp;
}

选择排序

时间复杂度O(n^2)，空间复杂度O(1)，不稳定。

选择排序（Selection sort）是一种简单直观的排序算法第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾以此类推，直到全部待排序的数据元素的个数为零选择排序是不稳定的排序方法

public static void selectSort(int array[]) {
    // 每次遍历将最小值放到在下标 i 上
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[minIndex] > array[j]) {
                // 选出出最小值的下标
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(array, i, minIndex);
        }
    }
}

插入排序

时间复杂度O(n^2)，空间复杂度O(1)，稳定。

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法将第一个元素看作有序序列，后续元素当作无序序列，依次将无序序列元素插入有序序列当中；在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

InsertionSort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的进程相同。举例： Input: {4, 3, 8, 5, 2, 6, 1, 7} 首先拿起第一张牌, 手上有 {4}。拿起第二张牌 3, 把 3 insert 到手上的牌 {4}, 得到 {3 ，4}。拿起第三张牌 8, 把 8 insert 到手上的牌 {3，4 }, 得到 {3 ，4，8}。

插入排序由N-1趟排序组成。对于p=1到N-1趟排序后，插入排序保证从位置0到位置p上的元素为已排序状态。即插入排序利用了从位置0到p-1位置上已经有序的条件，将位置p上的元素向前查找适当的位置插入此元素。

public static void insertionSort(int[] array) {
    if (array.length <= 1) {
        return;
    }
    // i = 0 默认有序，所以从 i = 1 开始遍历
    for (int i = 1; i < array.length; i++) {
        // 其实就是一个往后插入的逆向冒泡排序的过程
        for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
            swap(array, j, j + 1);
        }
    }
}

// 为后面的希尔排序铺垫
public static void insertionSort2(int[] array) {
    if (array.length <= 1) {
        return;
    }
    // 待插入元素，array[0] 默认排好序，作为前序子数组
    int i = 1;
    while (i < array.length) {
        // 起始位置：获取前序子数组最后一位
        int j = i - 1;
        int waitInsert = array[i];
        while (j >= 0 && array[j] > waitInsert) {
            // j-- 遍历，找到需要插入的位置
            array[j + 1] = array[j];
            j--;
        }
        // 插入前序子数组的末尾
        array[j + 1] = waitInsert;
        i++;
    }
}

希尔排序

时间复杂度与增量序列有关；下文使用的折半增量写法最坏时间复杂度为O(n^2)，空间复杂度O(1)，不稳定。

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort）,是直接插入排序算法的一种更高效的改进版本

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

选择一个增量序列，初始增量gap=length/2，后续元素依次为前一元素除2，直至gap=1；每轮以gap为步长，将列表划分为若干组，并在组内执行插入排序；重复该过程，直至gap=1；辅助理解参考博客园

// 直接插入排序增量是 1 ，希尔排序增量是 gap
public static void shellSort(int[] array) {
    int length = array.length;
    for (int gap = length / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < length; i++) {
            // 使用插入排序算法，将元素依次插入所在小组的已排序列表中
            // 待插入元素
            int waitInsert = array[i];
            int j = i - gap;
            // 前序子数组已经排好序，反向遍历，找到合适的位置插入元素
            while (j >= 0 && array[j] >= waitInsert) {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = waitInsert;
        }
    }
}

归并排序

时间复杂度O(nlogn)，空间复杂度O(n)，稳定。

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

将列表从正中间分为两个子列表；按照第一步，递归拆分每个子列表，直至子列表最大长度为1；按照拆分层级，依次按大小合并各子列表，直至全部合并完成。

归并排序之所以稳定，关键在于合并两个有序子数组时，相等元素必须优先保留左侧子数组中的元素顺序。

基本思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

分解（Divide）：将 n 个元素分成两个各含 n/2 个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列以得到排序结果

实现逻辑：

迭代法

申请空间，使其大小为两个已经排序序列之和，该空间用来存合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并区间，并移动指针到下一位置
重复步骤3 直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

递归法

将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕

两两合并，先比较左右子数组头部元素（大或小），将小的头部元素移动到新数组（此时移动的旧子数组头部因为已经为空，所以同数组的下一个元素晋升为新的头元素）当一个子数组为空的时候，依次将另一个子数组剩余元素移动到新数组末尾

递归版本：

public static void main(String[] args) {
    int[] array = { 6, 4, 8, 9, 2, 3, 1};
    mergeSort(array);
    for (int num : array) {
        System.out.print(num + " ");
    }
}

 // 递归版，入口方法-1
public static void mergeSort(int[] array) {
    // 先开辟一个大小相同的空数组，防止频繁申请空间
    int[] tempArray = new int[array.length];
    mergeSort(array, 0, array.length - 1, tempArray);
}

// 递归版 方法-2
public static void mergeSort(int[] array, int left, int right, int[] tempArray) {
    if (left < right) {
        int mid = (left + right) >> 1;
        // 分为左右两个子数组
        // { 6, 4, 8, 9, 2, 3, 1}  left = 0 ,right = 6 , mid = 3
        // {6,4,8,9} left = 0, right = 3, mid = 1; {2,3,1} left = 4, right = 6, mid = 5;
        // {6，4} {8，9} {2，3} {1}
        // {6} {4} {8} {9} {2} {3} {1} 本应该分成这样，但此时left = right, 不满足 if 条件，所以执行上面的merge合并操作
        // 上一步merger操作的 left = 0;right = 1; mid = 0
        mergeSort(array, left, mid, tempArray);
        mergeSort(array, mid + 1, right, tempArray);
        merge(array, left, mid, right, tempArray);
    }
}

// 递归版 方法-3
// 子数组合并实现
public static void merge(int[] array, int left, int mid, int right, int[] tempArray) {
    int i = left; // 左数组头元素
    int j = mid + 1; // 右数组头元素
    int k = 0; // 中间数组有序存储合并后的元素
    // 将小的头部元素移动到新数组（此时移动的旧子数组头部因为已经为空，所以下一个元素晋升为新的头元素）
    // 合并[left,mid]、[mid+1,right]两个数组
    // 所以 i 的边界是 = mid,大于mid表示左数组遍历完毕（为空）
    // j 的边界是 = right，大于 right 表示右数组遍历完毕（为空）
    while (i <= mid && j <= right) {
        // 相等时优先保留左侧元素，归并排序才能保持稳定性
        if (array[i] <= array[j]) {
            tempArray[k++] = array[i++];
        } else {
            tempArray[k++] = array[j++];
        }
    }
    // 将未遍历完的子数组，依次添加到中间数组
    while (i <= mid) {
        tempArray[k++] = array[i++];
    }

    while (j <= right) {
        tempArray[k++] = array[j++];
    }

    // 将合并的有序中间数组替换到原数组位置中
    // 因为每次中间数组都是以 0 下标开始，所以先对 k 作初始化
    k = 0;
    while (left <= right) {
        array[left++] = tempArray[k++];
    }
}

迭代版本

// 第一次比2个元素，第二次4个元素，第三次8个元素，第四次16个元素，两两归并
public static void mergeSortIteration(int[] array) {
    int length = array.length;
    // 创建一个大小和目标数组相同大小的中间数组
    int[] tempArray = new int[length];
    for (int block = 1; block < length; block *= 2) { // 步长
        for (int start = 0; start < length - block; start += block * 2) {
            int leftMin = start;
            int leftMax = Math.min(leftMin + block, length); // 左子数组的边界
            int rightMin = leftMax; // 右子数组的起始位
            int rightMax = Math.min(rightMin + block, length); // 右子数组的边界
            // 中间数组下标
            int k = 0;
            while (leftMin < leftMax && rightMin < rightMax) {
                if (array[leftMin] <= array[rightMin]) { // 相等时先取左数组，保持稳定
                    tempArray[k++] = array[leftMin++];
                } else {
                    tempArray[k++] = array[rightMin++];
                }
            }
            while (leftMin < leftMax) { // 左子数组没遍历完
                tempArray[k++] = array[leftMin++];
            }

            while (rightMin < rightMax) { // 右子数组没遍历完
                tempArray[k++] = array[rightMin++];
            }
            // 将中间数组元素复制回目标数组[start,rightMax) 区间
            while (k > 0) {
                array[--rightMax] = tempArray[--k];
            }
        }
    }
}

迭代结果

交换前：9 8 6 4 3 2 1 
block:1 leftMin:0 leftMax:1 rightMin:1 rightMax:2
交换后8 9 6 4 3 2 1 

交换前：8 9 6 4 3 2 1 
block:1 leftMin:2 leftMax:3 rightMin:3 rightMax:4
交换后8 9 4 6 3 2 1 

交换前：8 9 4 6 3 2 1 
block:1 leftMin:4 leftMax:5 rightMin:5 rightMax:6
交换后8 9 4 6 2 3 1 

交换前：8 9 4 6 2 3 1 
block:2 leftMin:0 leftMax:2 rightMin:2 rightMax:4
交换后4 6 8 9 2 3 1 

交换前：4 6 8 9 2 3 1 
block:2 leftMin:4 leftMax:6 rightMin:6 rightMax:7
交换后4 6 8 9 1 2 3 

交换前：4 6 8 9 1 2 3 
block:4 leftMin:0 leftMax:4 rightMin:4 rightMax:7
交换后1 2 3 4 6 8 9 

快速排序

平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)；递归实现的平均空间复杂度O(logn)，最坏可退化为O(n)，不稳定。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序

从列表中选出一个元素，作为“基准”pivot，基准一般随机选择，或采用最左端、最右端和中间位置3元素的中值；
将小于基准的元素排在基准前面，大于基准的元素排在基准后面，此时基准元素所在位置即为其最终排序完成时的位置；
以基准元素为界，将列表分为两个子列表；
递归地对子列表重复上述操作。

在工程上是使用随机选择，从概率的角度讲，时间复杂度为O(nlogn)。划分值的值尽量可以等分数组，如果为边界值，则算法会退化成O(n^2)。

左程云算法：利用一个左边界小于区，最开始在-1位置，然后与最后一个数进行比较，然后左边的指针与最后一个数进行比较，如果比他更小，则当前的值与小于区的下一个位置进行交换，再将小于区的位置增加1。

递归版本：

简易版：

// 简易版，选数组的第一个元素作为基准
public static int[] quicksort(int[] array) {
    return quicksort(array, 0, array.length - 1);
}

public static int[] quicksort(int[] array, int left, int right) {
    int basic = array[left];
    int i = left;
    int j = right;
    // 第一趟排序，根据基准划分左右序列
    while (i < j) {
        while (i < j && array[j] > basic) { // 说明右值大于基准值，指针向前移动
            j--;
        }
        while (i < j && array[i] < basic) { // 说明左值小于基准值，指针后移
            i++;
        }
        if (i < j && array[i] == array[j]) {
            i++;
        } else {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    if (i - 1 > left) {
        array = quicksort(array, left, i - 1);
    }
    if (j + 1 < right) {
        array = quicksort(array, j + 1, right);
    }
    return array;
}

左程云版本：

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int[] p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}

public static int[] partition(int[] arr, int l, int r) {
    int less = l - 1;
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
        } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
        } else {
            l++;
        }
    }
    swap(arr, more, r);
    return new int[] { less + 1, more };
}

迭代版本：

// 快速排序 非递归(迭代版)
void quickSortIteration(vector<int>& array) {
	stack<vector<int>> boundaries;
	int left = 0, right = array.size() - 1;
	while (left < right || !boundaries.empty()) {
		if (left >= right) {
			vector<int> boundary = boundaries.top();
			boundaries.pop();
			left = boundary[0];
			right = boundary[1];
		}
		int pivotLoction = partition(array, left, right);
		if (pivotLoction + 1 < right) {
			boundaries.push({ pivotLoction + 1, right });
		}
		right = pivotLoction - 1;
	}
}

堆排序

时间复杂度O(nlogn)，空间复杂度O(1)，不稳定。

若采用自底向上的 heapify 建堆，建堆阶段时间复杂度为O(n)；若像下文代码这样逐个插入元素建堆，则建堆阶段为O(nlogn)。

按层将堆转换成数组后：大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想： 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到剩余元素中的次大值。如此反复执行，便能得到一个有序序列（一般升序采用大顶堆，降序采用小顶堆）。

将数字转化为一个堆；堆本质上是完全二叉树，并满足堆序性质：大顶堆中父节点值不小于子节点值，小顶堆中父节点值不大于子节点值。正因为它是完全二叉树，所以可以用数组高效表示。堆常作为优先队列的底层结构，但优先队列的语义是“按优先级出队”，并不是先进先出。
取出堆顶元素（最大元素），放到当前有序区间的末尾，并调整剩余元素使其重新满足堆的特性；
重复上一步骤，直到堆空为止；

左程云算法：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        // 插入，建立一个大根堆
        heapInsert(arr, i);
    }
    int size = arr.length;
    // 让第一个数和最后一个数交换位置
    // 最后一个元素不再动了
    swap(arr, 0, --size);
    // 重复调整大根堆
    while (size > 0) {
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }
}

public static void heapInsert(int[] arr, int index) {
    // 当前节点位置比父节点位置更大，则循环交换
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
// 跟自己的左右孩子比较，将大的数上移
public static void heapify(int[] arr, int index, int size) {
    // 左孩子下标
    int left = index * 2 + 1;
    while (left < size) {
        // 在右孩子不越界，然后找到左右孩子中更大的孩子下标
        int largest = left + 1 < size && arr[left + 1] > arr[left]
                            ? left + 1 
                            : left;
        // 获取左右孩子下标后，判断与父节点的大小，返回一个最大值的下标
        largest = arr[largest] > arr[index] ? largest : index;
        // 如果最大值为父节点，即无需调整，退出循环
        if (largest == index) {
            break;
        }
        // 需要调整大根堆
        swap(arr, largest, index);
        // 更换父节点的下标值，继续执行左右孩子的大小比较
        index = largest;
        left = index * 2 + 1;
    }
}

计数排序

时间复杂度O(n+k)，空间复杂度O(k)。标准实现可以保持稳定；下述代码是直接回写的简化版，不保留相等元素的原始相对顺序。

遍历待排序数组A，找出其最小值min和最大值max；
创建一个长度为max-min+1的数组B，其所有元素初始化为0，数组首位对应数组A的min元素，索引为i位置对应A中值为min+i的元素；
遍历数组A，在B中对应位置记录A中各元素出现的次数；
遍历数组B，按照之前记录的出现次数，输出几次对应元素；

// 计数排序
void countSort(vector<int>& array){
    if (array.empty()){
        return;
    }
    //找出最大最小值
    int min = array.front(),max = array.front();
    for (int i = 1; i < array.size(); i++){
        if (min > array[i]){
            min = array[i];
        }
        else if (max < array[i]){
            max = array[i];
        }
    }

    // 记录各元素出现次数
    vector<int> counts(max - min + 1);
    for (int i = 0; i < array.size(); i++){
        counts[array[i] - min]++;
    }

    // 根据记录的次数输出对应元素
    int index = 0;
    for (int j = 0; j < counts.size(); j++){
        int n = counts[j];
        while (n--){
            array[index] = j + min;
            index++;
        }
    }
}

桶排序

平均时间复杂度O(n+k)，最坏可退化为O(n^2)，空间复杂度O(n+k)。稳定性取决于桶内排序算法以及桶元素收集方式。

设置固定数量的空桶；
找出待排序数组的最大值和最小值；
根据最大最小值平均划分各桶对应的范围，并将待排序数组放入对应桶中；
为每个不为空的桶中数据进行排序（例如，插入排序或其他适合桶内数据规模的排序算法）；
拼接不为空的桶中数据，得到排序后的结果。

// 桶排序
void bucketSort (vector<int>& array, int bucketCount){
    if (array.empty()){
        return;
    }
    // 找出最大最小值
    int max = array.front(), min = array.front();
    for (int i = 1; i < array.size(); i++){
        if (min > array[i]){
            min = array[i];
        }
        else if (max < array[i]){
            max = array[i];
        }
    }

    // 将待排序的各元素分入对应桶中
    vector<vector<int>> buckets(bucketCount);
    int bucketSize = ceil((double)(max - min + 1) / bucketCount);
    for (int i = 0; i < array.size(); i++){
        int bucketIndex = (array[i] - min) / bucketSize;
        buckets[bucketIndex].push_back(array[i]);
    }

    // 对各桶中元素进行排序；桶排序是否稳定取决于这里选择的桶内排序算法
    int index = 0;
    for (vector<int> bucket : buckets){
        if (!bucket.empty()){
            // 这里为了演示直接复用选择排序
            selectSort(bucket);
            for (int value : bucket){
                array[index] = value;
                index++;
            }
        }
    }

}
// 桶排序
void bucketSort (vector<int>& array){
    bucketSort (array, array.size() / 2);
}

基数排序

时间复杂度O(n*k)，空间复杂度O(n+k)，稳定。

将各待比较元素数值统一数位长度，即对数位短者在前补零；
根据个位数值大小，对数组进行排序；
重复上一步骤，依次根据更高位数值进行排序，直至到达最高位；

jishu

// 基数排序：以下实现只讨论非负整数
void radixSort(vector<int>& array){
    // exp = 1 表示个位，10 表示十位，100 表示百位
    int exp = 1;
    // 当前位是否已超过最高位
    bool isOverHighest = false;
    while (!isOverHighest){
        isOverHighest = true;
        // 利用分桶的思想来实现按各位进行排序
        vector<vector<int>> buckets(10);
        for (int curVal : array){
            int bucketIndex = (curVal / exp) % 10;
            buckets[bucketIndex].push_back(curVal);
            if (isOverHighest && curVal / (exp * 10)){
                isOverHighest = false;
            }
        }
        // 按照桶的顺序，将各桶内元素拼接起来
        int index = 0;
        for (vector<int> bucket : buckets){
            for (int value : bucket){
                array[index] = value;
                index++;
            }
        }
        exp *= 10;
    }
}

Algorithm

总览