快排与双轴快排
2023-05-08 21:40:56 424
传统快排
该方法的基本思想是：
- 先从数列中取出一个数作为基准数
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
- 再对左右区间重复第二步，直到各区间只有一个数
快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用另的方法排序以减小递归深度
示例代码如下, 没有进行任何优化操作, 便于更直观的理解
public class ArraysTest {
public static void main(String[] args) {
int[] arr = new int[]{5, 6, 1, 3, 9, 8, 0};
System.out.println(Arrays.toString(sort(arr)));
}
public static void sort(int[] arr, int i, int j) {
if (i < j) {
int start = i;
int end = j;
int pivot = arr[i];
while (true) {
while (true) {
if (i == j) {
break;
}
if (arr[j] <= pivot) {
arr[i] = arr[j];
break;
}
j--;
}
while (true) {
if (i == j) {
break;
}
if (arr[i] > pivot) {
arr[j] = arr[i];
break;
}
i++;
}
if (i == j) {
break;
}
}
arr[i] = pivot;
sort(arr, start, i - 1);
sort(arr, i + 1, end);
}
}
}
双轴快速排序(Dual Pivot Quicksort)
经典快排进行了更多的元素扫描动作，因此也就比较慢。
Dual-Pivot快排比经典快排节省了12%的元素扫描，从实验来看节省了10%的时间
双轴快排使用了两个pivot, 即双轴, 双轴隔断(partition)后
区间如下
[n < p1, p1 <= n <= p2, n > p2 ]
left为0, right为最后一位下标
Part I [left, i - 1]为 < P1 部分
Part II [i, k - 1]为 >= P1 且 <= P2 部分
Part III [j + 1, right - 1]为 > P2 部分
Part IV [k, j] 为还没有确定的部分
排序中, 通过k的遍历, 逐一确定每一个元素所在区间, 并进行对应交换
如下数组, 初始化i=0, j=length-1, k=i+1, 若p1>p2, 需要交换两个轴的位置, 即swap(arr[i], arr[j]), p1=arr[i], p2=arr[j]
因为当第一次寻找到第一区间的数时, k是与++i进行交换的, 即轴1的位置是暂时先固定, 保证i左边的数符合第一区间的条件, 最后将arr[0]这个轴放到第二区间的第一位上以符合轴左右的数的顺序.
同理, 当第一次寻找到第三区间的数时, k是与--j进行交换的. 轴2的位置固定, 保证j右边这个范围都是第三区间的数, 最后将arr[length-1]这个轴放到第二区间的最后一位上以符合轴左右的数的顺序.
第一次排序结果4, 3, 5, 6, 7, 8 | p1 = 5, p2 = 7
完成后, 可以发现p1左边都是小于等于p1的, p1/p2中间的都是大于p1, 小于等于p2的, p2右边都是大于p2的
最后将三个区间再进行递归排序即可
代码如下
public static void main(String[] args) {
int[] arr = {5, 5, 8, 6, 4, 3, 7};
// int[] arr = {4, 981, 10, -17, 0, -20, 29, 50, 8, 43, -5};
// int[] arr = {3, 5, 67, 54, 2, 56, 0, 7, 134, 23};
// int[] arr = {3, 5, 1, 6, 4, 7, 2, 8};
dualPivotQuickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void dualPivotQuickSort(int[] arr, int i, int j) {
if (i < j) {
if (arr[i] > arr[j]) {
swap(arr, i, j);
}
int k = i + 1;
int p1 = arr[i];
int p2 = arr[j];
int start = i;
int end = j;
while (k < j) {
if (arr[k] < p1) {
// 第一区间
// 先自增再交换
// 如果不自增直接交换, 可能会将轴放到错误的位置上
i++;
swap(arr, i, k);
// 指针k移动到下一位
k++;
} else if (arr[k] >= p1 && arr[k] <= p2) {
k++;
} else {
while (true) {
// 如果不自增直接交换, 可能会将轴放到错误的位置上或跳过元素
j--;
if (arr[j] <= p2 || k >= j) {
break;
}
}
// 指针重合 退出循环
if (k >= j) {
break;
}
swap(arr, k, j);
}
}
// 将两个轴放在隔断(partition)处
swap(arr, start, i);
swap(arr, end, j);
// 将两轴隔断形成的三区域再排序 两个轴不参与再排序, 因为本身就是有序的
dualPivotQuickSort(arr, start, i - 1);
dualPivotQuickSort(arr, i + 1, j - 1);
dualPivotQuickSort(arr, j + 1, end);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
