算法-排序算法

排序算法简介

排序算法一般有简单排序、归并排序、快速排序、堆排序、桶排序

排序算法根据时间复杂度可分为$O(n^2)$，$O(nlogn)$

• $O(n^2)$：简单排序时间
• O(nlogn)​：归并排序、快速排序、堆排序、桶排序

算法的稳定性：排序后相同大小的元素不改变其本来次序，则具有稳定性

简单排序

排序工具类：

public class SortTool {
    
    public static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

冒泡排序

时间复杂度 $O(n^2)$

空间复杂度 O(1)

稳定性：稳定

public class BubbleSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;

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

选择排序

时间复杂度 $O(n^2)$

空间复杂度 O(1)

稳定性：不稳定（最不可取）

public class SelectSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] > arr[minIndex] ? minIndex : j;
            }
            if (minIndex != i) {
                SortTool.swap(arr, i, minIndex);
            }
        }
    }
}

插入排序

时间复杂度 $O(n^2)$

空间复杂度 O(1)

稳定性：稳定

public class InsertSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;

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

归并排序

时间复杂度 O(nlogn)

空间复杂度 O(n)

稳定性：稳定

归并排序思想：先局部再整体有序。递归的将数组每次一分为二，两部分有序后再合并

public class MergeSort {

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

    public static void process(int[] arr, int l, int r) {
        if (l == r) return;
        // 计算中点，>> 优先级低
        int m = l + ((r - l) >> 1);
        process(arr, l, m);
        process(arr, m + 1, r);
        merge(arr, l, m, r);
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int[] tmp = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            tmp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            tmp[i++] = arr[p1++];
        }
        while (p2 <= r) {
            tmp[i++] = arr[p2++];
        }
        for (int j = 0; j < tmp.length; j++) {
            arr[l + j] = tmp[j];
        }
    }
}

经典快排

时间复杂度 O(nlogn)

空间复杂度 O(logn)

稳定性：不稳定

快速排序思想：选择一个基准，按基准将数组分为大小两部分，对每部分递归下去，当不可再分则整体有序

基准一般使用随机选择，相比固定选择某一位，在统计中时间复杂度的长期期望较低

快排 V1.0

public class QuickSort {

    public static void sort(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) {
            // 随机取一个元素，换到最后，作为基准
            int randomIdx = l + (int) (Math.random() * (r - l + 1));
            SortTool.swap(arr, randomIdx, r);
            int p = partition(arr, l, r);
            quickSort(arr, l, p - 1);
            quickSort(arr, p + 1, r);
        }
    }

    public static int partition(int[] arr, int l, int r) {
        // r 位置作为基准
        // less 区：小于等于基准
        int less = l - 1;
        int i = l;
        while (i < r) {
            // 小于等于基准，less 区右扩
            if (arr[i] <= arr[r]) {
                SortTool.swap(arr, ++less, i++);
                // 大于基准，跳过
            } else if (arr[i] > arr[r]) {
                i++;
            }
        }
        SortTool.swap(arr, less + 1, r);
        return less + 1;
    }
}

快排的基本步骤：

1. 数组 A 的下标区间是 [L, R]，随机选择一个下标作为基准值，将值换到数组的最后，基准即 A[R]

2. 设变量 less = L - 1，表示小于等于区域的边界，称为 less 区

3. 设变量 i 在数组的 [L, R] 区间内遍历

   当 A[i] <= 基准，交换 A[i] 和 less 区的下一个，即 A[less + 1]，LESS 区右括，i++

   当 A[i] > 基准，跳过，i++

4. 跳出循环时，i == R，此时可以将基准即 A[R] 与 A[less + 1] 交换，返回 less + 1，设为 p

5. 此时 p 的左边都小于等于 A[p]，右边都大于 A[p]

6. 对左边 [L, p - 1] 和右边 [p + 1, R] 递归下去，最终整体有序

快排 V2.0

public class QuickSort {

    public static void sort(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) {
            // 随机取一个元素，换到最后，作为基准
            int randomIdx = l + (int) (Math.random() * (r - l + 1));
            SortTool.swap(arr, randomIdx, 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) {
        // r 位置作为基准
        // less 区：小于基准
        int less = l - 1;
        // more 区：大于基准
        int more = r;
        int i = l;
        while (i < more) {
            // 小于基准，less 区右扩
            if (arr[i] < arr[r]) {
                SortTool.swap(arr, ++less, i++);
                // 大于基准，more 区左扩
            } else if (arr[i] > arr[r]) {
                SortTool.swap(arr, --more, i);
            } else {
                i++;
            }
        }
        SortTool.swap(arr, more, r);
        // 等于区域的边界
        return new int[]{less + 1, more};
    }
}

快排 2.0 的优化：

1. 引入大于区域，原来的 less（初始为 L - 1） 表示小区区域的边界，more （初始为 R）表示大于区域的边界

2. 设变量 i 在数组的 [L, R] 区间内遍历，基准为 A[R]

3. 当 A[i] < 基准，交换 A[i] 和 less 区的下一个，即 A[less + 1]，LESS 区右括，i++

4. 当 A[i] > 基准，交换 A[i] 和 more 区的上一个，即 A[more - 1]，more 区左扩，i 原地

5. 当 A[i] == 基准，跳过，i++

6. 跳出循环时，i == R，此时可以将基准即 A[R] 与 A[less + 1] 交换，返回 {less + 1, more}，即等于区域的边界，设为数组 p

7. 对左边 [L, p[0] - 1] 和右边 [p[1] + 1, R] 递归下去，最终整体有序

相比于快排 1.0 版本，免去了等于区域的重复处理，性能稍快一些

堆排序

时间复杂度 O(nlogn)

空间复杂度 O(1)

稳定性：不稳定

堆分为大顶堆和小顶堆，常用来维护一批数据的最大（小）值，利用特性，一批数据入堆再出堆，即可实现排序

在开发中，可以手写堆或者使用编程语言中自有的堆实现来完成这一过程

例如，Java 中的堆的实现是 PriorityQueue，可以构造出大顶堆和小顶堆

int[] nums = {3, 2, 5, 1, 4, 6, 2};
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
}
while (!minHeap.isEmpty()) {
    // 出堆
    nums[nums.length - minHeap.size()] = minHeap.poll();
}

System.out.println(Arrays.toString(nums));

堆排序和快排时间复杂度相同，空间复杂度优于快排，也都是不稳定的排序

但快排的性能往往更好，因为快排的复杂度常数项较低

一般编程语言中的排序函数在针对不要求稳定性的数据排序场景时会使用快排

桶排序

桶排序思想：将待排序的元素分到不同的桶中，然后分别对每个桶内的元素进行排序，最后按照桶的顺序将排序好的元素依次输出

桶排序并不基于比较，是一种基于数据状况来定制的排序

计数排序

计数排序是一种特殊的桶排序，假设输入的数据都是非负整数，并且数据的范围已知。创建一个长度等于数据范围的计数数组，统计每个元素出现的次数，然后根据计数数组中的信息，按顺序将元素输出到结果数组中

计数排序适用于元素范围较小的情况，且元素为非负整数。通常用于对一定范围内的整数进行排序，例如对成绩或年龄进行排序

时间复杂度：O(n + k)，其中 n 是待排序元素数量，k 是元素的取值范围

空间复杂度：O(n + k)，需要额外的空间来存储计数数组

基数排序

假设基数为 10，即有 10 个桶；先获取数字的最大位数 d，设变量 i 在 [1, d] 区间内遍历，i 代表数字从右往左数第几位，每次将 i 位置的数入桶，再遍历桶取出数据，直到所有位数都处理完毕

平均时间复杂度：O(d * (n + k))，d 是数字的最大位数，n 是待排序元素数量，k 是每一位的基数

空间复杂度：O(n + k)，需要额外的空间来存储桶和桶内元素

在上述基数排序思路基础上，优化得到代码：

public class RadixSort {

    public static void sort(int[] arr) {
        int[] bucket = new int[arr.length];
        // 获取最大的位数
        int maxBits = maxBits(arr);
        // 需要进出桶的次数，代表当前统计的位
        for (int i = 1; i <= maxBits; i++) {
            // 计数器
            int[] counter = new int[10];
            // 统计当前位的数量
            for (int j = 0; j < arr.length; j++) {
                int bit = getBit(arr[j], i);
                counter[bit]++;
            }
            // 前缀和，将统计当前位变成统计小于等于当前位的数量
            for (int j = 1; j < counter.length; j++) {
                counter[j] = counter[j] + counter[j - 1];
            }
            // 入桶出通
            for (int j = arr.length - 1; j >= 0; j--) {
                int bit = getBit(arr[j], i);
                bucket[counter[bit] - 1] = arr[j];
                counter[bit]--;
            }
            // 赋值
            System.arraycopy(bucket, 0, arr, 0, bucket.length);
        }
    }

    public static int maxBits(int[] arr) {
        int maxNum = Integer.MIN_VALUE;
        for (int a : arr) {
            maxNum = Math.max(maxNum, a);
        }
        int bits = 0;
        while (maxNum != 0) {
            maxNum = maxNum / 10;
            bits++;
        }
        return bits;
    }

    public static int getBit(int i, int b) {
        int divisor = (int) Math.pow(10, b - 1);
        return (i / divisor) % 10;
    }
}

优化的思路：

依然按数字的最大位数 d 遍历，不需要使用 10 个桶去装数，而是基于词频数组推断出桶位置

假设要排序的数组 A 是 [13, 21, 11, 52, 62]，准备词频数组 C，C[i] 表示当前位是 i 的数的数量

例如当第 1 次遍历时，是对个位上的数统计词频，C 为 [0, 2, 2, 1, 0, 0...]

对词频数组求前缀和，得到数组 C2 为 [0, 2, 4, 5, 5, 5...]，C2[j] 表示当前位小于等于 j 的数的数量

从右向左遍历数组 A，每次取出当前位的值为 a，根据 C2 得到，小于等于 a 的数量为 C2[a]，由于是从右向左遍历，C2[a] - 1 的值即为当前数的出桶后下标，更新 C2[a] = C2[a] - 1，如 62 应该在出桶后的 4 -1 = 3 下标上，52 在 3 -1 = 2 下标；当跳出循环时，已按该位排序完成，拷贝回原数组