【算法】快速排序及优化
- 2020 年 3 月 28 日
- 筆記
一、荷兰国旗问题
在讲快速排序前，我们先来看看荷兰国旗问题。题目如下：
给定一个数组arr，和一个数num，请把 小于num的数放在数组的左边， 等于num的数放在数组的中间， 大于num的数放在数组的 右边。 要求额外空间复杂度O(1)，时间复杂度O(N)， 例如： 对于数组3,5,4,5,8,1,9，以5进行分割 输出：3 4 1 5 5 9 8
其实，这就是快排的partition过程，通过三个指针，index，less，more进行的，初始less=左边界-1，more=右边界+1，说明一开始不存在less域和more域： 1）若arr[index] < num，less域增加，即less++，然后index和less位置的数交换后，index++继续指向下一个数 2）若arr[index] > num，more域增加，即more++，然后index和more的数交换后，继续判断交换后arr[index]和num的关系 3）若arr[index] == num，index++继续指向下一个数，不坐任何处理 4）重复以上过程，直至index==more
大致过程图：
代码实现
public static int[] partition(int[] arr, int l, int r, int num) { int less = l - 1; int more = r + 1; int index = l; // 循环至index到more相等 while (index < more) { if (arr[index] < num) { // 扩大less域 swap(arr, ++less, index++); }else if (arr[index] > num){ // 扩大more域，且交换后，继续判断当前index的数和num的关系 swap(arr, --more, index); }else { index++; } } int[] result = {less + 1, more - 1}; // 返回相等区间开始和结束的索引值 return result; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
二、经典快速排序
快排其实是冒泡排序的改进，其算法思路如下： 1）在数组中选取一个数作为基准元素 2）分区，把小于基准的数放左边，大于基准的数放右边 3）递归，对左右两个分区重复以上步骤
在网上找了一张图，如下所示（侵删）：
实现代码
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l >= r) { return; } int p = partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p + 1, r); } public static int partition(int[] arr, int l, int r) { // 取左边第一个数为基准 int pivot = arr[l]; int i = l; int j = r; while(i != j) { // 从右边找第一个小于基准的数 while(arr[j] >= pivot && i < j) { j--; } // 从左边找第一个大于基准的数 while(arr[i] <= pivot && i < j) { i++; } if (i < j) { swap(arr, i, j); } } // 将基准归位 swap(arr, l, j); // 返回基准的位置 return j; }
三、改进的快速排序
回顾经典的快速排序，可以优化的地方有两个：
1）基准的选取，若每次取数组的第一个作为基准，则可能出现基准是数组中最小的数，造成了多余的计算。因此，基准的选取可以进行随机选择 2）分区返回的边界，回顾荷兰国旗问题，分区时，可以发现基准可以是中间一片区域，而不是一个数，因此，分区时，返回的不在是基准的位置，而是基准的左边界和右边界，那么下次划分子问题时，就可以减少交换的次数了。
代码实现
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // quickSort2(arr, 0, arr.length - 1); quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < r) { // 从l~r中选一个数，放在r作为基准 swap(arr, l + (int) (Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } // 分割 public static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; int index = l; // 循环至index到more相等 while (index < more) { if (arr[index] < arr[r]) { // 扩大less域 swap(arr, ++less, index++); }else if (arr[index] > arr[r]){ // 扩大more域，且交换后，继续判断当前index的数和num的关系 swap(arr, --more, index); }else { index++; } } // 将基准归位，基准取的是最右边的数 swap(arr, more, r); int[] result = {less + 1, more}; // 返回相等区间开始和结束的索引值 return result; }
