力扣215（快排和堆排）_力扣怎么调用快速排序

1、题目

2、题解

2.1解法一：快速排序

思想：随机选取一个值作为中间值，比中间值小的排左边，大的排右边，那么当前值的具体位置就确定了，如果位置恰好是第k个最大元素的位置就可以直接返回值，否则继续选择性的递归

具体实现：

1、递归寻找

与直接进行快速排序的区别就在于可以选择递归区域，根据要找到第k大数的位置在已找到的位置前后进行相应的递归。

2、创造随机数

其中涉及到rand（）的用法，首先需要明确的是我们要在[left , right]之间去随机生成一个数，所以rand（）%（r - left + 1）就表示区间[0 , right - left]，两边同时加上left后区间就变成[left , right]，具体原因是因为一个数对另一个数取余，得到的值一定小于另一个数，如果等于另一个数就表明可以整除；如果大于另一个数则表明还可以继续除。

其次将随机选择的数放到数组最后，这是为了方便计算，待会儿会讲。

3、排序

首先用两个变量记录标志数的值和数组起始位置，遍历数组时，依次比较大小，如果小于或等于标志数就放到数组的左边，每放一个比标志数小的值起始位置变量就加一，当遍历完数组时，变量i就记录小于或等于标志数的最后一个位置，将最后一个数（标志数，创造随机数那里将标志数交换到最后）和变量i记录的下一个位置交换，就满足左边都比标志数小右边都比标志数大，也就完成了一次排序，再将排序得到的确定位置返回给递归入口，根据比较来决定下一次递归的左右边界是多少。

4、主函数

调用快速排序的递归入口。

5、整体

2.2解法二：堆排序

堆排序讲解，这篇文章讲的不错，其中遇到的几个问题记录一下：

1、遍历的起点是size / 2，这是因为遍历的都是以根节点、左右子结点三个为一组进行遍历，左右结点和根节点的关系是left = 2 * i + 1, right = 2 * i + 2，所以size / 2恰好是第一个没有左右结点的结点，相当于遍历的起点边界。

2、实现删除根节点的效果时，只需要将根节点和最后的叶结点交换，建立大顶堆的时候边界减一就可以让比之前的根节点的小一位的数字上来。