排序汇总

稳定性

如果完成排序后，原本有序的元素不会改变其相对的位置，表示该排序是稳定的；如果完成排序后，原本有序的元素会改变其相对的位置，表示该排序是不稳定的

举个简单的例子，如果对[1, 2, 2, 3, 4]进行排序，如下图所示：

冒泡排序


public int[] sort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {          // 进行 n - 1 轮遍历，每次都将值最大元素挪到最右边
        boolean isChange = false;              // 标记是否有交换操作
        for (int j = 0; j < n - i - 1; j++) {  // 从头开始两两进行交换
            if (nums[j] > nums[j + 1]) {
                int t = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = t;
                isChange = true;
            }
        }
        if (!isChange) break;                  // 如果一轮一次交换都没发送，表示元素均有序，直接退出循环
    }
    return nums;
}

$O(n^2)$ $O(1)$ ；稳定

注意： $O(n)$

选择排序


public int[] sort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int minId = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[minId] > nums[j]) minId = j;
        }
        int t = nums[i];
        nums[i] = nums[minId];
        nums[minId] = t;
    }
    return nums;
}

$O(n^2)$ $O(1)$ ；不稳定

关于不稳定，举个例子[7, 7, 2]，那么第一轮交换后为[2, 7, 7]，两个 7 的相对位置发生了变化

注意： $O(n^2)$

插入排序


public int[] sort(int[] nums) {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            int t = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] <= t) break;
                nums[j + 1] = nums[j];
                nums[j] = t;
            }
        }
        return nums;
    }
}

$O(n^2)$ $O(1)$ ；稳定

注意： $O(n)$

归并排序

详情可见详解归并排序及其应用

$O(nlogn)$ $O(n)$ ；稳定

快速排序

详情可见详解快排及其应用

$O(nlogn)$ $O(logn)$ -> 递归栈所需空间；不稳定

注意： $O(n^2)$

堆排序

详情可见详解堆排序「优先队列」

$O(nlogn)$ $O(1)$ ；不稳定

总结

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n)$	$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)$	不稳定