快速排序 & 堆排序 & 桶排序

快速排序 & 快速选择

基准点的选取

基准点（pivot）是快速选择和快速排序算法中的一个关键概念。基准点的选取方法可以有很多种，常见的策略包括：

固定基准点：通常选择数组的第一个元素或最后一个元素作为基准点。
随机基准点：随机选择数组中的一个元素作为基准点。
三数取中：选择数组的第一个元素、最后一个元素和中间元素的中值作为基准点。

基准点的选取会影响算法的性能。如果每次选取的基准点都能将数组近似平分，那么快速排序的性能会更好。

逆序和正序的区别

在快速选择和快速排序算法中，逆序和正序的主要区别在于分区过程中比较和交换的方向。

正序排序

正序排序是指从小到大排序。在分区过程中，目标是将所有小于基准点的元素放在基准点的左侧，将所有大于基准点的元素放在基准点的右侧。

具体步骤如下：

从左向右找到第一个大于等于基准点的元素。
从右向左找到第一个小于等于基准点的元素。
交换这两个元素。
重复上述步骤直到左右指针相遇。

逆序排序

逆序排序是指从大到小排序。在分区过程中，目标是将所有大于基准点的元素放在基准点的左侧，将所有小于基准点的元素放在基准点的右侧。

具体步骤如下：

从右向左找到第一个大于等于基准点的元素。
从左向右找到第一个小于等于基准点的元素。
交换这两个元素。
重复上述步骤直到左右指针相遇。

注意：

逆序和正序排序没有本质的区别，但是需要注意的是，如果最后基准数是被放置在了最左边，那么交换过程应该先从右边开始交换，同理，如果最后基准数是被放置在了最右边，那么交换过程应该先从左边开始交换，这一点，无论逆序和正序都是一样的。

左右指针法

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
 
    int i = left, j = right;
    int pivot = arr[left]; // 选择数组的第一个元素作为基准
 
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数
        while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数
        if (i < j) swap(arr, i, j); // 交换这两个数
    }
 
    swap(arr, left, i); // 把基准放到它正确的位置上，此时i=j
 
    quickSort(arr, left, i - 1); // 递归处理左半部分
    quickSort(arr, i + 1, right); // 递归处理右半部分
}
 
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

挖矿法

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
 
    int i = left, j = right;
    int pivot = arr[left]; // 挖一个坑，选择数组的第一个元素作为基准
 
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于pivot的数
        if (i < j) arr[i++] = arr[j]; // 把该数填到之前挖出来的坑中
 
        while (i < j && arr[i] <= pivot) i++; // 从左往右找到第一个大于pivot的数
        if (i < j) arr[j--] = arr[i]; // 把该数填到刚才挖出的坑中
    }
 
    arr[i] = pivot; // 将最初挖出来的坑填回去，此时i=j
 
    quickSort(arr, left, i - 1); // 递归处理左半部分
    quickSort(arr, i + 1, right); // 递归处理右半部分
}

数组中第K个最大的元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int ans = quickSelect(nums, 0, nums.length - 1, k - 1);
        return ans;
    }

    public int quickSelect(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return nums[k];
        }
        int mid = left + (right - left) / 2;
        int pivot = nums[mid];
        swap(nums, mid, right);
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && nums[l] >= pivot) {
                l++;
            }
            while (l < r && nums[r] <= pivot) {
                r--;
            }
            if (l < r) {
                swap(nums, l, r);
            }
        }
        swap(nums, l, right);
        if (l == k) {
            return nums[l];
        } else if (l < k) {
            return quickSelect(nums, l + 1, right, k);
        } else {
            return quickSelect(nums, left, l - 1, k);
        }

    }

    public void swap(int[] nums, int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }
}

算法分析

1、时间复杂度

快速排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。最坏情况下，快速排序的时间复杂度为O(n^2)，但这种情况出现的概率很小，可以通过一些优化措施来避免。

2、空间复杂度

快速排序的空间复杂度取决于递归栈的深度，在最坏情况下，递归栈的深度为O(n)，因此快速排序的空间复杂度为O(n)。但是，在一些实现中，可以使用非递归的方式来实现快速排序，从而避免递归栈带来的空间开销。

3、稳定性

快速排序是一种不稳定的排序算法。因为在排序过程中，可能会交换相同元素的位置，从而导致相同元素的相对顺序被改变。例如，对于数组[3, 2, 2, 1]，如果选择第一个元素3作为基准元素，那么经过第一次划分后，数组变成了[1, 2, 2, 3]，其中两个2的相对顺序被改变了。

应用场景

大规模数据排序：快速排序的时间复杂度为 O(nlogn)，在大规模数据排序时表现优秀。
数据重复性较少的排序：在排序的数据中，如果存在大量重复的元素，那么快速排序的效率会受到影响，因为这样会增加比较和交换的次数。
对数据随机性要求不高的排序：由于快速排序的分区过程是基于一个基准元素来完成的，因此如果待排序数据的分布比较随机，那么快速排序的效率会很高。

堆排序 (优先级队列)

构建大根堆

    public void buildMaxHeap(int[] nums, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; i--) { // 从第一个非叶子节点开始堆化
            heapify(nums, i, heapSize);
        }
    }

    public void heapify(int[] nums, int index, int heapSize) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(nums, index, largest);
            heapify(nums, largest, heapSize); // 递归堆化子树
        }
    }

    public void swap(int[] nums, int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }

构建小跟堆

    public void buildMinHeap(int[] nums) {
        int heapSize = nums.length;
        for (int i = heapSize / 2 - 1; i >= 0; i--) { // 从第一个非叶子节点开始堆化
            heapify(nums, i, heapSize);
        }
    }

    public void heapify(int[] nums, int index, int heapSize) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < heapSize && nums[left] < nums[smallest]) {
            smallest = left;
        }
        if (right < heapSize && nums[right] < nums[smallest]) {
            smallest = right;
        }

        if (smallest != index) {
            swap(nums, index, smallest);
            heapify(nums, smallest, heapSize); // 递归堆化子树
        }
    }

    public void swap(int[] nums, int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }

总结

堆排序使用堆来选数，相比直接选择排序效率就高了很多。堆排序中每一趟都有元素归位了
时间复杂度：最好/最环/平均时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
适用场景：元素较多的情况，因为建初始堆的所需的比较次数比较多，所有堆排序不适合元素较少的时候

数组中第K个最大的元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            swap(nums, 0, i);
            --heapSize;
            heapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] nums, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; i--) { // 从第一个非叶子节点开始堆化
            heapify(nums, i, heapSize);
        }
    }

    public void heapify(int[] nums, int index, int heapSize) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(nums, index, largest);
            heapify(nums, largest, heapSize); // 递归堆化子树
        }
    }

    public void swap(int[] nums, int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }
}

桶排序（计数排序）

 public static void bucketSort(float[] arr) {
        int n = arr.length;
        if (n <= 0) return;

        // 1. 创建空桶
        ArrayList<Float>[] buckets = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 2. 将数组元素分配到各个桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (arr[i] * n);
            buckets[bucketIndex].add(arr[i]);
        }

        // 3. 对每个桶中的元素进行排序
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]);
        }

        // 4. 合并所有桶中的元素
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (float num : buckets[i]) {
                arr[index++] = num;
            }
        }
    }

总结：

典型的空间换时间，适用于数据范围不大的集合

数组中第K个最大的元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] buckets = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            k = k - buckets[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
}