快速排序和堆排序模板总结

堆排序以及快速排序模板

堆排序使用，215.数组中的第k个最大元素：https://leetcode.cn/problems/kth-largest-element-in-an-array

快速排序使用， 75.颜色分类： https://leetcode.cn/problems/sort-colors/

堆排序模板

public class MaxHeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 一个一个从堆顶取出元素
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶元素（最大值）与当前末尾元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 重新调整堆，排除已经排序好的元素
            heapify(arr, i, 0);
        }
    }

    // 堆化函数
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 初始化当前节点为最大值
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 如果左子节点比父节点大，更新最大值索引
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 如果右子节点比父节点大，更新最大值索引
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值不是当前节点，则交换并递归调整子树
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组：");
        printArray(arr);

        heapSort(arr);

        System.out.println("排序后的数组：");
        printArray(arr);
    }

    // 辅助函数，打印数组
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

首先，通过从数组的最后一个非叶子节点开始向前遍历，来进行循环，叶子节点的索引范围是从 heapSize / 2 到 0（包括边界值）。对于循环中，使用heapify堆化函数来进行当前子堆的排序。

注意，从最后一个非叶子节点开始遍历的意义就在于，此时非叶子节点对应最小的最大堆，从最小单元向上递归，保证子堆的堆顶元素一定最大

在循环中，对于每个节点，调用 heapify 方法，这个方法负责将当前节点及其子树调整为最大堆。因为最后一个非叶子节点的索引之后的节点都是叶子节点，它们自身已经是最大堆，所以只需要从最后一个非叶子节点开始往前遍历调用 heapify 方法即可。

heapify中元素，当发现堆顶largest发生了改变后，则说明需要发生交换，此时由于可能存在，与一边子树交换了，但另一边子树尚未交换，可能会破坏了它下面的子树的最大堆性质。所以需要递归地对交换后的子树进行堆化操作。

最后，如果需要排序，由于最大堆只能保证堆顶元素最大，因此需要循环取出元素，并每次取出后向下调整。

题解

因此最终得到对应题解

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;
            maxHeapify(nums, 0, heapSize);
        }//上述循环内的三步骤其实就是删除堆元素的三部，1、将堆顶元素与堆底部交换。2、减少堆尺寸。3、执行最大堆，向下调整
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize); //最后一个非叶子节点为
        }
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        // 父节点的下标 = （子节点下标 - 1） >> 1;
        // 左子节点下标 = 父节点下标 * 2 + 1；
        // 右子节点下标 = 父节点下标 * 2 + 2；
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

快速排序

由于颜色分类本身就适合快排，因此直接介绍：

快速排序的基本思想： 通过一趟排序将待排序的序列分割为左右两个子序列，左边的子序列中所有数据都比右边子序列中的数据小，然后对左右两个子序列继续进行排序，直到整个序列有序。

具体实现步骤是这样的，首先从序列中任意选择一个元素，把该元素作为枢轴，然后将小于等于枢轴的所有元素都移到枢轴的左侧，把大于枢轴的元素都移到枢轴的右侧。这样，以枢轴为界，划分出两个子序列，左侧子序列所有元素都小于右侧子序列。枢轴元素不属于任一子序列，并且枢轴元素当前所在位置就是该元素在整个排序完成后的最终位置。这样一个划分左右子序列的过程就叫做快速排序的一趟排序，或称为一次划分。递归此划分过程，直到整个序列有序。

一般来说，初始值一般选择为数组得中间元素，但是也可以选择第一个元素，仅仅实现简单。

题解

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1;
        quickSelect(nums, 0, nums.length - 1);
    }

    public void quickSelect(int[] nums, int l, int r) {
        if (l == r) return;
        // left = l, right = r; 同时不是do-while循环的话，很可能出现两个数值相等，且与x相等的情况，导致死循环
        // left = l - 1主要是为了do-while第一次的时候，能取到边界值。
        int left = l - 1, right = r + 1, x = nums[(l + r)/2];
        while (left < right) {
            do left++; while (nums[left] < x);
            do right--; while (nums[right] > x);
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }

        quickSelect(nums, l , right);
        quickSelect(nums, right + 1, r);
    }
}