1 基本思想

快速排序英文 Quick Sort，是冒泡排序的一种改进，由 C. A. R. Hoare 在 1960 年提出。
快速排序的主要思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使整个数据变成有序序列。

2 原理

在数据集之中，选择一个元素作为“基准”(pivot)
所有小于“基准”的元素，都移到“基准”的左边；所有大于“基准”的元素，都移到“基准”右边。这个操作称为分区（partition）。

分区操作结束后，基准元素所处的位置就是最终排序后它的位置。

对“基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

Partition-挖坑法
Partition-指针交换法
3 怎么选择基准pivot

选择第一个元素作为基准
随机选择一个元素作为基准

快速排序的平均时间复杂度是，最坏情况下的时间复杂度是。

215 数组中的第K个最大元素
https://leetcode.com/problems/kth-largest-element-i n-an-array/
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第 k 个不同的元素。
示例1：
- 输入：[3,2,1,5,6,4] 和 k = 2
- 输出：5
示例2：
- 输入：[3,2,3,1,2,4,5,5,6] 和 k = 4
- 输出：4

思路：

选择一个初始基准。
使用划分算法将基准放在数组中的合适位置 pos。将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边。

比较 pos 和 N - k 以决定在哪边继续递归处理。

class Solution:
def findKthLargest(self, nums, k):
   # 快排
   self._k = len(nums) - k
   return self.quicksort(nums, 0, len(nums)-1)
def quicksort(self, nums, left, right):
   if left == right:
       return nums[left]
   pivot = self.partition(nums, left, right)
   if pivot == self._k:
       return nums[pivot]
   elif pivot < self._k:
       return self.quicksort(nums, pivot+1, right)
   else:
       return self.quicksort(nums, left, pivot-1)
def partition(self, nums, left, right):
   pivot = nums[left]
   i, j = left, right
   while i < j:
       while i < j and nums[j] >= pivot:
           j -= 1
       if i < j:
           nums[i] = nums[j]
           i += 1
       while i < j and nums[i] <= pivot:
           i += 1
       if i < j:
           nums[j] = nums[i]
           j -= 1
   nums[i] = pivot
   return i

面试刷题班

P1 快速排序

1 基本思想

2 原理

3 怎么选择基准pivot

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