常用排序算法

在Java中存在如Arrays.sort(nums);这样的快捷方法，使得在实际刷题过程中很少需要自己手写排序算法。但是在面试中，一旦面试官问类似问题，回答不上来，就很容易被认为代码能力不过关。以下展示常用的一些排序算法。

冒泡排序：重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。这个过程持续对数列的末尾进行，直到整个数列都排序完成。其时间复杂度为O(n²)，空间复杂度为O(1)。

选择排序：其基本思想是每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始或结束位置，直到全部待排序的元素排完。其时间复杂度为O(n²)，空间复杂度为O(1)。

插入排序：其基本思想是将一个记录插入到已经排好序的有序表中。其时间复杂度为O(n²)，空间复杂度为O(1)。将当前值key和前面的值进行比较，如果前面的值大于key 则将值往后移1位，在不小于key的位置插入当前值。

归并排序：一种分治思想的排序算法，它的基本思想是将待排序的数组分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的数组。

归并排序图解.gif

具体实现代码如下：

public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
public static void merge(int[] arr, int left, int mid, int right) {
    // 左子数组 L 的大小
    int n1 = mid - left + 1;
    // 右子数组 R 的大小
    int n2 = right - mid;
    // 创建两个临时数组 L 和 R ，分别用来存储左子数组和右子数组的元素
    int[] L = new int[n1];
    int[] R = new int[n2];
    // 使用 for 循环将原始数组 arr 中的元素复制到临时数组 L 和 R 中，分别从 left 和 mid + 1 开始
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    // 初始化三个变量 i、j和k，分别指向数组 L 、R 和原始数组 arr 的起始位置
    int i = 0, j = 0, k = left;
    // 使用 while 循环，比较 L 和 R 的元素，并将较小的元素放回原始数组 arr 中
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 当 L 或 R 中的元素用完时，将剩余的元素依次放回原始数组 arr 中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    // merge方法执行完毕后，两个子数组范围内的元素已经按照从小到大的顺序合并到了原始数组 arr 中
}

代码内含一个递归调用，且每次都是n/2，同时每次调用过程中都做了n次比较，所以归并排序的时间复杂度为O( $n\log n$ )；每次都需要创建和为对应长度的左右子数组，其空间复杂度为O(n)。

快速排序：一种分治思想的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序图解.gif

其具体代码如下：

// 接收一个数组 arr，一个低索引 low ，和一个高索引 high 作为参数
    public static void quickSort(int[] arr, int low, int high) {
        // 检查 low 是否小于 high。如果不是，则意味着数组只有一个元素或为空，因此不需要排序
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }
/**
 * 取最后一个元素作为枢轴元素，将较小的元素放在左边，较大的元素放在右边
 * @param arr 输入数组
 * @param low 低位索引
 * @param high 高位索引
 * @return 枢轴所在位置
 */
private static int partition(int[] arr, int low, int high) {
    // 将最后一个元素作为枢轴元素
    int pivot = arr[high];
    // 将 i 初始化为 low - 1，用于跟踪较小元素的索引
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            // 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]
            i++;
            // 将当前元素 arr[j] 放在较小元素索引位置，将较小元素放在前面
            swap(arr, i, j);
        }
        // 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边
    }
    // 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换
    // 确保枢轴元素左边是较小元素，右边是较大元素
    swap(arr, i + 1, high);
    // 将 i + 1 作为枢轴索引返回，枢轴元素已是实际排序后的位置
    return i + 1;
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

代码内含递归调用，每次都将其分为2部分，同时调用过程中都做了n次比较，所以快速排序的时间复杂度为O( $n\log n$ )；在执行过程中并没有开辟额外的空间来存储数据，而是使用了原地排序，除了递归调用的栈空间外，算法本身只使用了常量的额外空间，其空间复杂度为O( $\log n$ )。注意快排在原先已有序的基础上时间复杂度为O(n²)，空间复杂度为O(n)，但是这样没啥意义，所以还是以前面的结论为公认。

桶排序：一种非比较排序算法，它的基本思想是将待排序的数组分到有限数量的桶里，然后对每个桶进行排序，最后依次将所有桶中的元素取出来，组成有序的数组。其本质是为每个目标值设立一个桶，桶内记录的是此值的出现次数（也可以是其他属性），然后对桶根据其元素值进行排序。

桶排序图解.gif

其时间复杂度为O(n²)，因为实际上它并没有进行比较，空间复杂度为O(n)，随着属性值增多空间也会扩大。

快速选择算法：

[215]数组中的第K个最大元素

题设：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路：快速选择类似于快速排序，只不过是找到第k大的pivot，而不需要对其左右进行排序。具体思路为设 N 为数组长度，如果某次哨兵划分后，基准数的索引正好是N−k ，则意味着它就是第 k 大的数字 。使用「三路划分」，即每轮将数组划分为三个部分：小于、等于和大于基准数的所有元素。这样当发现第 k 大数字处在“等于基准数”的子数组中时，便可以直接返回该元素。为了进一步提升算法的稳健性，可采用随机选择的方式来选定基准数。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) numList.add(num);
        return quickSelect(numList, k);
    }

    private int quickSelect(List<Integer> nums, int k) {
        Random random = new Random();
        int pivot = nums.get(random.nextInt(nums.size()));
        List<Integer> big = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot) big.add(num);
            else if (num < pivot) small.add(num);
            else equal.add(num);
        }
        //第 k大元素在 big中，递归划分
        if (k <= big.size()) return quickSelect(big, k);
        //第 k大元素在 small中，递归划分
        if (k > nums.size() - small.size()) return quickSelect(small, k - nums.size() + small.size());
        //第 k大元素在 equal中，直接返回
        return pivot;
    }
}

时间复杂度：对于长度为 n 的数组执行哨兵划分操作的时间复杂度为 O(n) 。其实就是遍历了数组中的每个元素，将其分到三个数组中。

空间复杂度： 划分函数的平均递归深度为 O(log n) 。

05.番外篇-排序算法

05.番外篇-排序算法

常用排序算法

快速选择算法：

[215]数组中的第K个最大元素