算法高频面试之：快速排序

vlambda
2021-06-13

算法高频面试之：快速排序

不点蓝字，我们哪来故事？

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

核心思想:

在待排序的元素任取一个元素作为基准（通常选第一个元素，称为基准元素）
将待排序的元素进行分块，比基准元素大的元素移动到基准元素的右侧，比基准元素小的移动到作左侧，从而一趟排序过程，就可以锁定基准元素的最终位置
对左右两个分块重复以上步骤直到所有元素都是有序的（递归过程）

具体算法执行流程如下：

算法高频面试之：快速排序

把5拆出来作为与其他元素比较的基准元素，设两个“指针”：right和left

算法高频面试之：快速排序

right指针从右向左扫描，8 > 5，保持不变，right指针左移

算法高频面试之：快速排序

4和5比较，4 < 5，拆4，放到元素5的位置，左指针右移

算法高频面试之：快速排序

1和5比较，1 < 5，保持不变，左指针继续右移

算法高频面试之：快速排序

3和5比较，3 < 5，保持不变，左指针继续右移

算法高频面试之：快速排序

7和5比较，7 > 5，拆7，放到之前元素4的位置，右指针左移

算法高频面试之：快速排序

这时候左指针和右指针的位置重叠，则将基准元素补入到该位置，结束这一次的拆补流程。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。

为什么算法执行的时候需要左指针 left 和右指针 right 相互交换移动？

你仔细模拟一遍执行流程就会发现，快速排序每次移动都是相对于基准点的（a[left]，a[right]相互交互的关键），只有这样才能使得比基准小的到左边，比基准大的到右边，从而确定基准元素的最终位置。

代码实现

public class FastSortDemo { public static void main(String[] args) { int[] nums = {5, 1, 3, 7, 4, 8}; int startIndex = 0; int endIndex = nums.length - 1; FastSortDemo fastSortDemo = new FastSortDemo(); fastSortDemo.quickSort(nums, startIndex, endIndex); System.out.println(Arrays.toString(nums)); }
 public void quickSort(int[] nums, int startIndex, int endIndex) { int left = startIndex; int right = endIndex; // 基准元素 int pivot = nums[startIndex];  // 先根据基准元素，将元素分成两拨，比基准元素小的，放在基准元素的左边，大的在右边 while (left <= right) { // 寻找比基准元素大的元素 while (pivot > nums[left]) { left++; } // 寻找比基准元素小的元素 while (pivot < nums[right]) { right--; } if (left <= right) { swap(nums, left, right); left++; right--; } }
 if (startIndex < right) { quickSort(nums, startIndex, right); }
 if (left < endIndex) { quickSort(nums, left, endIndex); } }
 // 两数交换 public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}