十大排序算法

下图展示了十大排序的名字和大致用法

说到排序，首先要用到就是交换数字，接下来谈谈三次交换方法

// 方法一: 利用临时数tmp
private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
// 方法二: 利用加减运算
private void swapCal(int[] arr, int i, int j) {
    if(i == j) return; // 若无法保证swapCal被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
    arr[i] = arr[i] + arr[j]; // a = a + b
    arr[j] = arr[i] - arr[j]; // b = a - b
    arr[i] = arr[i] - arr[j]; // a = a - b
}
// 方法三: 利用异或运算
private void swapXOR(int[] arr, int i, int j) {
    if(i == j) return; // 若无法保证swapXOR被调用时满足 i != j，则需有此句，否则i == j时此数将变为0
    arr[i] = arr[i] ^ arr[j]; // a = a ^ b，也可写成 arr[i] ^= arr[j];
    arr[j] = arr[i] ^ arr[j]; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a， 也可写成 arr[j] ^= arr[i];
    arr[i] = arr[i] ^ arr[j]; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b， 也可写成 arr[i] ^= arr[j];
}
方法一: 利用一个临时数 tmp 来交换 arr[i] ，arr[j] 。
方法二: 利用 arr[i] 和和 arr[j] 的加减运算避免临时数 tmp 的开销，但由于涉及到加减法可能导致数字 「提前溢出」 。
方法三: 利用位运算中的 异或 运算，能够避免 tmp 的开销且不会导致数字溢出。

冒泡排序

从第一位开始向后依次比较，如果前者大则交换（实际根据大小方向），循环arr.length-1次

最笨的形式

public int[] bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 1; j < arr.length - i; j++) {
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
            }
        }
    }
    return arr;
}

优化

提前结束优化

当某一轮比较均未发生交换，说明排序已完成，可设置一个布尔值记录一轮排序是否有发生交换，若无则提前退出循环结束程序。

public int[] bubbleSort(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1轮次执行，当前 n - 1 个元素排好后，最后一个元素无需执行，故i < arr.length - 1
    for (int i = 0; i < arr.length - 1; i++) {
        // 本轮执行是否有交换的标志，若无则false，若有则true
        boolean swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        for (int j = 1; j < arr.length - i; j++) {
            // 若左大于右则交换，并将swapped置为true
            if (arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
                swapped = true;
            }
        }
        // 若无交换，表示当前数组已完全排序，退出大循环
        if (!swapped) break;
    }
    return arr;
}

冒泡界优化

记录前一轮交换的最终位置，说明该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。

public int[] bubbleSort(int[] arr) {
    if (arr.length < 2) return arr;
    boolean swapped = true;
    int lastSwappedIdx = arr.length - 1 ;
    int swappedIdx = -1;
    // lastSwappedIdx表示前一轮交换的最终位置，即下标为lastSwappedIdx是未排序部分中的最后一个数的下标，
    // 因此for中的界是i < lastSwappedIdx而不需要写成i <= lastSwappedIdx
    while (swapped) { // 当swapped = false时，排序完成
        // 本轮执行是否有交换的标志，若无则true，若有则false
        swapped = false;
        // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右
        for (int i = 0; i < lastSwappedIdx; i++) {
            // 若左大于右则交换，并将swapped置为true
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                swapped = true;
                swappedIdx = i;
            }
        }
        lastSwappedIdx = swappedIdx;
    }
    return arr;
}

平均时间复杂度:O(n^2)

空间复杂度:O(n)

稳定

选择排序

每一轮循环选一个最小（或者最大）的数放到第i位，循环arr.length-1次

单元选择排序

public int[] selectSort(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1 轮次执行,当前 n - 1 个元素排好后，最后一个元素无需执行，故 i < arr.length - 1
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        // 找到本轮执行中最小的元素，将最小值下标赋值给min
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx])  minIdx = j;
        }
        // 若本轮第一个数字不是最小值，则交换位置
        if (minIdx != i) swap(arr, i, minIdx);
    }
    return arr;
}

双元选择排序

public int[] selectSortDouble(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length;
    // 每轮确定两个数字，因此界也会动态变化
    for (int i = 0; i < n - 1 - i; i++) {
        int minIdx = i, maxIdx = i;
        // 找到本轮执行中最小和最大的元素
        for (int j = i + 1; j < n - i; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
            if(arr[j] > arr[maxIdx]) maxIdx = j;
        }
        // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序
        if(minIdx == maxIdx) break;
        // 若本轮第一个数字不是最小值，则交换位置（将最小值与本轮第一个数字交换位置）
        if (minIdx != i) swap(arr, i, minIdx);
        // 在交换i和minIdx时，有可能出现i即maxIdx的情况，此时需要修改maxIdx为minIdx
        if(maxIdx == i) maxIdx = minIdx;
        // 若本轮最后一个数字不是最大值，则交换位置（将最大值与本轮最后一个数字交换位置）
        if (maxIdx != n - 1 - i) swap(arr, n - 1 - i, maxIdx);
    }
    return arr;
}

平均时间:O(n^2)

空间:O(1)

不稳定

插入排序

对于待排序数组，从第2个元素开始(称作插入对象元素)，比较它与之前的元素(称作比较对象元素)，当插入对象元素小于比较对象元素时，继续往前比较，直到不小于(≥)比较对象，此时将插入对象元素插入到该次比较对象元素之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作。

简单插入排序

public int[] insertSort(int[] arr) {
    if (arr.length < 2) return arr;
    for (int i = 1; i < arr.length; i++) { // N-1轮次执行
        int target = arr[i], j = i - 1;
        for (; j >= 0; j--) {
            if(target < arr[j]) arr[j + 1] = arr[j];
            else break;
        }
        arr[j + 1] = target; // 若发生移动，此时的插入对象数字≥j位置的数字，故插入位置为j + 1，若未移动也成立，无需判断
        // if(j != i - 1) arr[j + 1] = target; // 也可以用这种写法，表示发生移动才插入，否则不必插入(赋值)，但不判断效率更高
    }
    return arr;
}

折半插入优化(利用二分来减少中间比较次数)

注意到插入排序的每一轮向前插入都使得该元素在完成插入后，从第一个元素到该元素是排序状态（指这部分的相对排序状态，在它们中间后续可能还会插入其他数字），利用这一点，对一个新的插入对象向前执行折半插入，能够显著减少比较的次数。另一种优化是增量递减插入排序，也叫希尔排序，将在希尔排序章节中介绍。

折半插入的关键在于找到插入位置，折半过程代码如下。这实际上是二分查找「模版一」中的「小于等于」情形。

public int[] insertSortBinary(int[] arr) {
    if (arr.length < 2) return arr;
    // n - 1 轮次执行
    for (int i = 1; i < arr.length; i++) {
        // 若当前插入对象大于等于前一个对象，无需插入
        if (arr[i - 1] <= arr[i]) continue;
        int target = arr[i];
        // 折半查找 (二分查找「模版一」)
        int low = 0, high = i - 1;
        // while结束后，target要插入的位置为low或high + 1 (low = high + 1)
        while (low <= high) {
            int center = low + (high - low) / 2;
            if (arr[center] <= target) low = center + 1;
            else high = center - 1;
        }
        for (int j = i; j > low; j--) { // 移动
            arr[j] = arr[j - 1];
        }
        arr[low] = target; // 插入
    }
    return arr;
}

平均时间:O(n^2)

空间:O(1)

不稳定

希尔排序

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

Shell增量

// 希尔排序：采用Shell增量 N / 2^k
public int[] shellSortShell(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) { // gap 初始为 n/2，缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < n; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) { 
                     if (target < arr[j]) {
                         arr[j + gap] = arr[j];
                     } else break; 
                }                 
                if (j != i - gap) arr[j + gap] = target;
            }
        }
    }
    return arr;
}

Hibbard增量

// 希尔排序： 采用Hibbard增量 {1, 3, 7, 15,...}
public int[] shellSortHibbard(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length, gap = 1; 
    while (gap < n / 2) gap = gap * 2 + 1; // 初始化gap (Hibbard增量序列)
    for (; gap > 0; gap /= 2) { // 缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) { 
                     if (target < arr[j]) {
                         arr[j + gap] = arr[j];
                     } else break; 
                }                 
                if (j != i - gap) arr[j + gap] = target;
            }
        }
    }
    return arr;
}

Knuth增量

// 希尔排序： 采用Knuth增量 {1, 4, 13, 40,...}
public int[] shellSortKnuth(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length, gap = 1; 
    while (gap < n / 3) gap = gap * 3 + 1; // 初始化gap (Knuth增量序列)
    for (; gap > 0; gap /= 3) { // 缩小gap直到1
        for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序
            for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序
                int target = arr[i], j = i - gap;
                for (; j >= 0; j -= gap) { 
                     if (target < arr[j]) {
                         arr[j + gap] = arr[j];
                     } else break; 
                }                 
                if (j != i - gap) arr[j + gap] = target;
            }
        }
    }
    return arr;
}

简单插入排序和希尔排序比较

归并排序

归并排序是 分治思想 的应用，即将原待排数组 递归或迭代地 分为左右两半，直到数组长度为1，然后对左右数组进行合并(merge)，在合并中完成排序。

自顶向下(top-down)：从输入数组出发，不断二分该数组，直到数组长度为1，再执行合并。适合用 递归 实现。

自底向上(bottom-up)：从输入数组的单个元素出发，一一合并，二二合并，四四合并直到数组有序。适合用 迭代 实现。

自顶向下非原地归并

public int[] mergeSort(int[] arr) {
    if (arr.length < 2) return arr;
    int[] tmpArr = new int[arr.length];
    mergeSort(arr, tmpArr, 0, arr.length - 1);
    return arr;
}

private void mergeSort(int[] arr, int[] tmpArr, int left, int right) {
    if(left < right) {
        int center = left + (right - left) / 2;
        mergeSort(arr, tmpArr, left, center);
        mergeSort(arr, tmpArr, center + 1, right);
        merge(arr, tmpArr, left, center, right);
    }
}

// 非原地合并方法
private void merge(int[] arr, int[] tmpArr, int leftPos, int leftEnd, int rightEnd) {
    int rightPos = leftEnd + 1;
    int startIdx = leftPos;
    int tmpPos = leftPos;
    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        if (arr[leftPos] <= arr[rightPos]) {
            tmpArr[tmpPos++] = arr[leftPos++];
        }
        else {
            tmpArr[tmpPos++] = arr[rightPos++];
        }
    }
    // 比较完成后若左数组还有剩余，则将其添加到tmpArr剩余空间
    while (leftPos <= leftEnd) {
        tmpArr[tmpPos++] = arr[leftPos++];
    }
    // 比较完成后若右数组还有剩余，则将其添加到tmpArr剩余空间
    while (rightPos <= rightEnd) {
        tmpArr[tmpPos++] = arr[rightPos++];
    }
    // 容易遗漏的步骤，将tmpArr拷回arr中
    // 从小区间排序到大区间排序，大区间包含原来的小区间，需要从arr再对应比较排序到tmpArr中，
    // 所以arr也需要动态更新为排序状态，即随时将tmpArr拷回到arr中
    for(int i = startIdx; i <= rightEnd; i++) {
        arr[i] = tmpArr[i];
    }
}

自顶向下原地归并

public int[] mergeSort(int[] arr) {
    if (arr.length < 2) return arr;
    mergeSort(arr, 0, arr.length - 1);
    return arr;
}

private void mergeSort(int[] arr, int left, int right) {
    if(left < right) {
        int center = left + (right - left) / 2;
        mergeSort(arr, left, center);
        mergeSort(arr, center + 1, right);
        merge(arr, left, center, right);
    }
}

// 原地归并（手摇算法）
private void merge(int[] arr, int leftPos, int leftEnd, int rightEnd) {
    int i = leftPos, j = leftEnd + 1; // #1
    while(i < j && j <= rightEnd) {
        while(i < j && arr[i] <= arr[j]) i++; // #2
        int index = j; // #3
        while(j <= rightEnd && arr[j] < arr[i]) j++; // #4 注意是 arr[j] < arr[i]，即找到j使得arr[j] 为第一个大于等于 arr[i]值
        exchange(arr, i, index - 1, j - 1); // #5
    }
}

// 三次翻转实现交换
private void exchange(int[] arr, int left, int leftEnd, int rightEnd) {
    reverse(arr, left, leftEnd);
    reverse(arr, leftEnd + 1, rightEnd);
    reverse(arr, left, rightEnd);
}

private void reverse(int[] arr, int start, int end) {
    while(start < end) {
        swap(arr, start, end);
        start++;
        end--;
    }
}

自底向上非原地归并

public int[] mergeSortBU(int[] arr) {
    if (arr.length < 2) return arr;
    int[] tmpArr = new int[arr.length];
    // 间隔，注意不能写成gap < arr.length / 2 + 1，此种写法只适用于元素个数为2的n次幂时
    for(int gap = 1; gap < arr.length; gap *= 2) {
        // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...)
        for(int left = 0; left < arr.length - gap; left += 2 * gap) {
            // 调用非原地合并方法。leftEnd = left+gap-1; rightEnd = left+2*gap-1;
            merge(arr, tmpArr, left, left + gap - 1, Math.min(left + 2 * gap - 1, arr.length - 1));
        }
    }
    return arr;
}

自底向上原地归并

public int[] mergeSortBUInPlace(int[] arr) {
    if (arr.length < 2) return arr;
    // 间隔，注意不能写成gap < arr.length / 2 + 1，此种写法只适用于元素个数为2的n次幂时
    for(int gap = 1; gap < arr.length; gap *= 2) {
        // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...)
        for(int left = 0; left < arr.length - gap; left += 2 * gap) {
            // 调用原地合并方法。leftEnd = left+gap-1; rightEnd = left+2*gap-1;
            merge(arr, left, left + gap - 1, Math.min(left + 2 * gap - 1, arr.length - 1));
        }
    }
    return arr;
}

平均时间复杂度:O(nlogn)

空间复杂度:O(n)

稳定

快速排序

与归并排序一样，快速排序也是一种利用 分治思想 的排序方法，确定 主轴及分区 是快速排序的核心操作。首先在数组中确定一个主轴元素(下标记为 pivot)，然后将数组分为两部分，小于主轴的放在（确定最终位置的）主轴左侧，大于等于主轴的放在主轴右侧。递归地对主轴左右两侧数组执行这个过程，每次递归都传入待排序数组 arr 和本次要处理的部分的左右界，只处理这个范围内的序列。当所有递归都到达基准情形时，排序完成。因为是原地交换，递归过程中 arr总是在动态排序，递归过程无需返回，为尾递归形式。

递归快排

// 三数取中快排
public int[] quickSortMedian3(int[] arr) {
    if (arr.length < 2) return arr;
    quickSortMedian3(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}

private void quickSortMedian3(int[] arr, int left, int right) {
      if (left < right) { 
        // 执行median3将左，中，右三数中值放到left位置上
        median3(arr, left, right);
        int pivot = partition(arr, left, right);
        quickSortMedian3(arr, left, pivot - 1);
        quickSortMedian3(arr, pivot + 1, right);
    }
}


// 将left, center, right下标三个数中，大小居中者放到left下标处
private void median3(int[]arr, int l, int r) {
    int c = l + (r - l) / 2;
    if (arr[l] > arr[c]) swap(arr, l, c); // 左中，大者居中
    if (arr[c] > arr[r]) swap(arr, c, r); // 中右，大者居右，此时最大者居右
    if (arr[c] > arr[l]) swap(arr, l, c); // 左中，大者居左，此时中者居左
}

// 随机主轴快排
public int[] quickSortRandom(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    quickSortRandom(arr, 0, arr.length - 1);
    return arr;
}

private void quickSortRandom(int[] arr, int left, int right) {
    if (left < right) {
        // 取区间内随机下标，注意Random().nextInt(int x)方法的使用（含0不含x）
        int randomIndex = new Random().nextInt(right - left) + left + 1; // 在[left + 1, right]范围内的随机值
        // 交换随机取得的下标元素与当前起始元素
        swap(arr, left, randomIndex); // arr[left]与它之后的某个数交换
        int pivot = partition(arr, left, right);
        quickSortRandom(arr, left, pivot - 1);
        quickSortRandom(arr, pivot + 1, right);
    }
}

// 朴素快排(首位为主轴)
public int[] quickSortSimple(int[] arr) {
    if (arr.length < 2) return arr;
    quickSortSimple(arr, 0, arr.length - 1); // 后两个参数是下标值
    return arr;
}

private void quickSortSimple(int[] arr, int left, int right) {
    // 若left == right，表示此时arr只有一个元素，即为基准情形，完成递归(准确说是完成递进)
    // (尾递归，“回归”过程中不做任何事情）
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSortSimple(arr, left, pivot - 1);
        quickSortSimple(arr, pivot + 1, right);
    }
}

//　partition方法
private int partition(int[] arr, int left, int right) {
    int pivot = left, index = pivot + 1;
    // 注意此时right是坐标，要执行到最后一个元素，所以是<=
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, index, i);
            index++;
        }
    }
    // 最后一个小于主轴元素的元素下标是index - 1
    swap(arr, pivot, index - 1);
    return index - 1;
}

非递归快排 (迭代快排)

public int[] quickSortStack(int[] arr) {
    // 用于保存区间左右边界的栈，按right到left的顺序将初始区间界入栈
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(arr.length - 1);
    stack.push(0);
    // 判断栈是否空，不空则弹出一对left，right界
    while(!stack.isEmpty()) {
        int left = stack.pop(), right = stack.pop();
        if(left < right) { // 执行partition的前提是left小于right
            // 对[left, right]区间执行partition方法，得到pivot
              // 加入后续两行实现随机轴快排
            // int randomIndex = new Random().nextInt(right - left) + left + 1; // 在[left + 1, right]范围内的随机值
            // swap(arr, left, randomIndex); // arr[left]与它之后的某个数交换
              // 加入下行实现三数取中快排
            median3(arr, left, right);
            int pivot = partition(arr, left, right);
            // 当前pivot的左区间存在则将该区间right，left界入栈
            if(pivot > left) {
                stack.push(pivot - 1);
                stack.push(left);
            }
            // 当前pivot的右区间存在则将该区间right，left界入栈
            if(right > pivot) {
                stack.push(right);
                stack.push(pivot + 1);
            }
        }
    }
    return arr;
}

平均时间复杂度:O(nlogn)

空间复杂度:O(logn)

不稳定

堆排序

将输入数组建立为一个 大顶堆，之后反复取出堆顶并对剩余元素重建大顶堆，将依次取出的堆顶逆序排列，即可将原数组从小到大排列完成排序。

public int[] heapSort(int[] arr) {
    if (arr.length < 2) return arr;
    heapify(arr, arr.length - 1); // 构建大顶堆
    for (int i = arr.length - 1; i > 0; i--) { // i > 0即可，无需写成i >= 0，当n - 1个元素排序时，最后一个元素也已排序
        swap(arr, 0, i); // 交换堆顶和当前未排序部分最后一个元素
        // 此时除当前堆顶元素外都是保持堆序的，只需要对该堆顶调用一次下滤操作
        siftDown(arr, 0, i - 1); // i - 1是未排序部分最后一个元素下标，确保下滤不会超过此范围
    }
    return arr;
}

private void heapify(int[] arr, int endIdx) {
    for (int hole = (endIdx - 1) / 2; hole >= 0; hole--) { // (endIdx - 1) / 2伪最后一个非叶子节点下标
        siftDown(arr, hole, endIdx);
    }
}

private void siftDown(int[] arr, int hole, int endIdx) {
    int target = arr[hole]; // target是要下滤的节点
    int child = hole * 2 + 1;
    while(child <= endIdx) {
        // 满足第一个条件child < endIdx表示hole有右孩子，不满足则hole无右孩子，跳过
        // 第二个条件arr[child + 1] > arr[child]只在第一个条件成立前提下进行判断（因此不必担心arr[child + 1]越界），
        // 若满足，表示hole有右孩子且右孩子更大，令child为右孩子下标。
        // 因此此if过后使得child是hole的孩子中较大的那个
        if (child < endIdx && arr[child + 1] > arr[child]) {
            child++;
        }
        // 若child大于target，则child上移到当前hole，hole下滤到child位置 
        if (arr[child] > target) {
            arr[hole] = arr[child];
            hole = child;
            child = hole * 2 + 1; // 当然也可以写成child = child * 2 + 1
        } else break; // 若无需交换hole与child，说明hole已经满足堆序(无需/无法再下滤)，退出while
    }
    arr[hole] = target; // 将target填入hole中
}

平均时间复杂度:O(nlogn)

空间复杂度:O(1)

不稳定

计数排序

计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

算法的步骤如下：

• （1）找出待排序的数组中最大和最小的元素
• （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

不稳定计数排序

public int[] countSortUnstable(int[] arr) {
    if (arr.length < 2) return arr;
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    int[] countArr = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < countArr.length; i++) { // 遍历countArr
        for (int j = 0; j < countArr[i]; j++) { // countArr[i]可能有多个相同数字
            arr[index] = i + min; // 复用了原输入数组arr
            index++;
        }
    }
    return arr; 
}

稳定计数排序

public int[] countSort(int[] arr) {
    if (arr.length < 2) return arr;
    int n = arr.length, min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    int[] countArr = new int[max - min + 1]; // arr最多有max-min+1种数字
    for (int i = 0; i < n; i++) {
        countArr[arr[i] - min]++; // arr[i]的值出现一次，则countArr[arr[i]-min]加1
    }
    for (int i = 1; i < countArr.length; i++) { // 变形
        countArr[i] += countArr[i - 1];
    }
    int[] sortedArr = new int[n]; // 根据sortedArr, nums, countArr三者关系完成sortedArr的输出
    for (int i = n - 1; i >= 0; i--) {
        sortedArr[countArr[arr[i] - min] - 1] = arr[i];
        countArr[arr[i] - min]--;
    }
    return sortedArr;
}

平均时间复杂度:O(n+k)

空间复杂度:O(n+k)

稳定

基数排序

非比较排序，「基」指的是数的位，例如十进制数 123，共有百十个位，共 3 个位。基数排序 按数字的位进行循环，每一轮操作都是对当前位（基数）的计数排序，使得输出到 arr 后所有数字在截止到当前位上（即去掉未考察的位后）是排序状态，考察完最大位后完成排序。具体过程如下：

• 遍历待排序数组 arr ，找到最大值，计算其位数，例如 arr 中最大数为 123 ，则 maxDigitLen = 3 。
• 数组的数字为 n 进制，就创建大小为 n 的计数数组 countArr ，也可以称为 n 个桶。
• 开始「位」的 for 循环，循环次数等于 maxDigitLen ，每一轮对 当前所有数字的当前位 执行一次 计数排序。
• 每次计数排序结束后将结果写回 arr 。
• for循环结束后返回排序结果 arr。

以计数排序为基础

public int[] radixSort(int[] arr) {
    if (arr.length < 2) return arr;
    int max = Math.abs(arr[0]); // 找到arr中绝对值最大者
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, Math.abs(arr[i]));
    }
    int maxDigitLen = 0, base = 10; // 最大位数 & 基（几进制就是几）
    while (max != 0) {
        maxDigitLen++;
        max /= base;
    }
    // 在接下来的for中，每一轮都对当前位(基数)执行一次计数排序
    int[] sortedArr = new int[arr.length];
    for (int i = 0; i < maxDigitLen; i++) {
        int[] countArr = new int[19]; // 处理负数优化
        // 根据每一个数字当前位的数字，累计相应位置的计数
        for (int j = 0; j < arr.length; j++) {
            // 此步处理要注意，当base大于10时，例如base=100时，1234%100=34
            // 还需要再除以(base/10)，得到的3，然后再+9（考虑负数）才是本次的bucketIdx
            int bucketIdx = (arr[j] % base) / (base / 10) + 9;
            countArr[bucketIdx]++;
        }
        // countArr变形，得到每个下标所代表的arr中的数的当前位在arr中的最大位置（从1开始）
        for (int j = 1; j < countArr.length; j++) {
            countArr[j] += countArr[j - 1];
        }
        // 逆序输出保持稳定性
        for (int j = arr.length - 1; j >= 0; j--) {
            int thisBase = (arr[j] % base) / (base / 10) + 9;
            // countArr[thisBase]得到的从1开始计算的位置，转成下标要-1
            sortedArr[countArr[thisBase] - 1] = arr[j]; 
            countArr[thisBase]--;
        }
        // 完成当前位的计数排序后将排序结果拷贝回原数组
        arr = Arrays.copyOf(sortedArr, sortedArr.length);
        // base进一位，准备下一轮对下一位的计数排序
        base *= 10;
    }
    return arr;
}

不以计数排序为基础

public int[] radixSort(int[] arr) {
    if (arr.length < 2) return arr;
    // 找到arr中绝对值最大者
    int max = Math.abs(arr[0]);
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, Math.abs(arr[i]));
    }
    int maxDigitLen = 0, base = 10; // 最大位数 & 基
    while (max != 0) {
        maxDigitLen++;
        max /= base;
    }
    // arr.length + 1的作用是令每个桶的第0位保存该桶的元素个数。
    int[][] buckets = new int[19][arr.length + 1]; // 处理负数优化
    // 在每一位上将数组中所有具有该位的数字装入对应桶中
    for (int i = 0; i < maxDigitLen; i++) {
        for (int j = 0; j < arr.length; j++) {
            // 此步处理要注意，当base大于10时，例如base=100时，1234%100=34
            // 还需要再除以(base/10)，得到的3才是本次的bucketIndex
            int bucketIdx = (arr[j] % base) / (base / 10) + 9; // +9使其可以处理负数
            int currentBucketQuantity = buckets[bucketIdx][0];
            buckets[bucketIdx][currentBucketQuantity + 1] = arr[j];
            buckets[bucketIdx][0]++;
        }
        // 将当前所有桶的数按桶序，桶内按低到高输出为本轮排序结果
        int arrIdx = 0;
        for (int j = 0; j < buckets.length; j++) {
            for (int k = 1; k <= buckets[j][0]; k++) {
                arr[arrIdx++] = buckets[j][k];
            }
        }
        // 每一轮过后将桶计数归零
        for (int[] bucket : buckets) bucket[0] = 0;
        base *= 10; // 调整base
    }
    return arr;
}

平均时间复杂度:O(d(n+k))

空间复杂度:O(n+k)

稳定

桶排序

桶排序将原数组划分到称为 「桶」 的多个区间中，然后对每个桶单独进行排序，之后再按桶序和桶内序输出结果。适合于分布较均匀的数据，具体做法如下。

• 根据数据规模按照 一定的方法 将待排序数组arr划分为多个区间，每个区间称作一个桶。

• 每个桶可以是数组，也可以是泛型容器，用于保存arr中落在该桶范围内的数。

• 对每一个桶都单独排序，需要 以适当的排序 方法支持，例如插入排序，快速排序等。

• 所有桶完成排序后，按桶序，桶内序依次输出所有元素，得到arr的排序结果。

  稳定性：取决于桶内排序方法的稳定性。

public int[] bucketSort(int[] arr) {
    int min = arr[0], max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    // 用泛型List存储所有桶，每个桶是一个ArrayList<Integer>，并初始化所有桶。
    // arr.length/3表示设置数组大小三分之一数量的桶
    List<ArrayList<Integer>> buckets = new ArrayList<>(arr.length / 3);
    for (int i = 0; i < arr.length; i++) {
        buckets.add(new ArrayList<>());
    }
    // 遍历arr，根据元素值将所有元素装入对应值区间的桶中
    for (int i = 0; i < arr.length; i++) {
        // (arr[i] - min)/D为arr[i]元素应该装入的桶的下标，间隔D = (max-min)/(arr.length-1)
        // 虽可写成(arr[i] - min)*(arr.length-1)/(max-min)的形式，但当输入数组取值范围较大且元素较多时
        // (arr[i] - min)*(arr.length-1)可能会超过int上限，因此先做除法求出double类型的D
        // 再做一次除法求出bucketIndex，可以避免计算精度不够高带来的问题
        double interval = (double)(max - min) / (double)(arr.length - 1);
        int bucketIdx = (int) ((arr[i] - min) / interval);
        buckets.get(bucketIdx).add(arr[i]);
    }
    // 桶内排序(调用库函数，从小到大)
    for (int i = 0; i < buckets.size(); i++) {
        Collections.sort(buckets.get(i));
    }
    int index = 0;
    for (ArrayList<Integer> bucket : buckets) {
        for (int sortedItem : bucket) {
            arr[index] = sortedItem; // 复用输入数组arr
            index++;
        }
    }
    return arr;
}

平均时间复杂度:O(n)

空间复杂度:O(n)

稳定