十大排序算法

0. 总览

1.冒泡排序 (Bubble Sort)

稳定性：稳定（相等元素之间不会相互交换，从而保证了它们的相对位置不变，因此冒泡排序被认为是稳定的排序算法）
时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$，平均：$O(n^2)$
空间复杂度：$O(1)$

/**
 * 冒泡排序
 * @param arr
 * @return arr
 */
public static int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    return arr;
}

2.选择排序 (Selection Sort)

稳定性：不稳定（5, 8, 5, 2, 9，使用选择排序进行升序排序，第一趟会将第一个 5 和 2 交换位置）
时间复杂度：最佳：$O(n^2)$ ，最差：$O(n^2)$，平均：$O(n^2)$
空间复杂度：$O(1)$
排序方式：In-place

/**
 * 选择排序
 * @param arr
 * @return arr
 */
public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    return arr;
}

3.插入排序 (Insertion Sort)

稳定性：稳定
时间复杂度：最佳：$O(n)$ ，最差：$O(n^2)$，平均：$O(n^2)$
空间复杂度：$O(1)$

/**
 * 插入排序
 * @param arr
 * @return arr
 */
public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex -= 1;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

4.希尔排序 (Shell Sort)

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 $O(n^2)$ 的第一批算法之一。

选择一个增量序列 $\lbrace t_1, t_2, \dots, t_k \rbrace$，其中 $t_i \gt t_j, i \lt j, t_k = 1$；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 $t$，将待排序列分割成若干长度为 $m$ 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$，最差：$O(n^2)$ 平均：$O(nlogn)$
空间复杂度：$O(1)$

/**
 * 希尔排序
 *
 * @param arr
 * @return arr
 */
public static int[] shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int current = arr[i];
            int preIndex = i - gap;
            // Insertion sort
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = current;

        }
        gap /= 2;
    }
    return arr;
}

5.归并排序 (Merge Sort)

如果输入内只有一个元素，则直接返回，否则将长度为 $n$ 的输入序列分成两个长度为 $n/2$ 的子序列；
分别对这两个子序列进行归并排序，使子序列变为有序状态；
设定两个指针，分别指向两个已经排序子序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
重复步骤 3 ~ 4 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

稳定性：稳定(对于相等的元素，归并排序会按照它们在原数组中的先后顺序进行合并，不会改变相同元素的相对顺序。)
时间复杂度：最佳：$O(nlogn)$，最差：$O(nlogn)$，平均：$O(nlogn)$
空间复杂度：$O(n)$(需要借助一个额外的辅助数组来暂存合并后的有序元素。)

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

6.快速排序 (Quick Sort)

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$，最差：$O(n^2)$，平均：$O(nlogn)$
空间复杂度：$O(logn)$ 快速排序是递归算法(运用了分治的思想，递归树是高度)

从序列中随机挑出一个元素，做为 “基准”(pivot)；
重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[ l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

7.堆排序 (Heap Sort)

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

稳定性：不稳定
时间复杂度：最佳：$O(nlogn)$，最差：$O(nlogn)$，平均：$O(nlogn)$
空间复杂度：$O(1)$

8.计数排序 (Counting Sort)

不是比较排序。

当输入的元素是 n 个 0 到 k 之间的整数时

稳定性：稳定
时间复杂度：最佳：$O(n+k)$ 最差：$O(n+k)$ 平均：$O(n+k)$
空间复杂度：$O(k)$

找出数组中的最大值 max、最小值 min；
创建一个新数组 C，其长度是 max-min+1，其元素默认值都为 0；
遍历原数组 A 中的元素 A[i]，以 A[i] - min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出现次数作为 C[A[i] - min] 的值；
对 C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；
创建结果数组 R，长度和原始数组一样。
从后向前遍历原始数组 A 中的元素 A[i]，使用 A[i] 减去最小值 min 作为索引，在计数数组 C 中找到对应的值 C[A[i] - min]，C[A[i] - min] - 1 就是 A[i] 在结果数组 R 中的位置，做完上述这些操作，将 count[A[i] - min] 减小 1。

/**
 * Gets the maximum and minimum values in the array
 *
 * @param arr
 * @return
 */
private static int[] getMinAndMax(int[] arr) {
    int maxValue = arr[0];
    int minValue = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        } else if (arr[i] < minValue) {
            minValue = arr[i];
        }
    }
    return new int[] { minValue, maxValue };
}

/**
 * Counting Sort
 *
 * @param arr
 * @return
 */
public static int[] countingSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int[] countArr = new int[maxValue - minValue + 1];
    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - minValue] += 1;
    }
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        int idx = countArr[arr[i] - minValue] - 1;
        result[idx] = arr[i];
        countArr[arr[i] - minValue] -= 1;
    }
    return result;
}

9.桶排序 (Bucket Sort)

稳定性：稳定
时间复杂度：最佳：$O(n+k)$ 最差：$O(n^2)$ 平均：$O(n+k)$
空间复杂度：$O(n+k)$

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

计数排序适用于范围较小且离散的数据，而桶排序适用于范围较大且均匀分布的数据（包括浮点数）。

设置一个 BucketSize，作为每个桶所能放置多少个不同数值；
遍历输入数据，并且把数据依次映射到对应的桶里去；
对每个非空的桶进行排序，可以使用其它排序方法(插入排序等)，也可以递归使用桶排序；
从非空桶里把排好序的数据拼接起来。

假设我们要对以下数组进行桶排序：[0.42, 0.32, 0.23, 0.75, 0.56, 0.12]

假设将数据分配到 5 个桶，每个桶的范围为 [0, 0.2), [0.2, 0.4), [0.4, 0.6), [0.6, 0.8), [0.8, 1)。
将每个元素放入相应的桶：
- [0.42] → 桶 [0.4, 0.6)
- [0.32] → 桶 [0.2, 0.4)
- [0.23] → 桶 [0.2, 0.4)
- [0.75] → 桶 [0.6, 0.8)
- [0.56] → 桶 [0.4, 0.6)
- [0.12] → 桶 [0, 0.2)
每个桶内的元素进行排序：
- 桶 [0, 0.2) 排序后：[0.12]
- 桶 [0.2, 0.4) 排序后：[0.23, 0.32]
- 桶 [0.4, 0.6) 排序后：[0.42, 0.56]
- 桶 [0.6, 0.8) 排序后：[0.75]
合并所有桶中的元素，得到排序后的结果：[0.12, 0.23, 0.32, 0.42, 0.56, 0.75]

10.基数排序 (Radix Sort)

取得数组中的最大数，并取得位数，即为迭代次数 $N$（例如：数组中最大数值为 1000，则 $N=4$）；
A 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；
将 radix 依次赋值给原数组；
重复 2~4 步骤 $N$ 次

稳定性：稳定
时间复杂度：最佳：$O(n×k)$ 最差：$O(n×k)$ 平均：$O(n×k)$
空间复杂度：$O(n+k)$

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

数据结构