【算法】快速排序及优化
一、荷兰国旗问题
在讲快速排序前，我们先来看看荷兰国旗问题。题目如下：
给定一个数组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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录