快排实现
- 1. 思路
- 2. 实现
1. 思路
- 快排是基于分治思想
在数组中选中某个数值为基准,左边大于等于基准,右边小于等于基准。
这里就不举例子了,网上类似的文章很多,这篇文章主要是剖析快排算法的实现。
2. 实现
这里将会罗列两种写法,可以仔细对比两者区别,就能够更好地理解快排的思想。
- 这是一种写法:
java">public class QuitSort {
public static void sort(int[] num) {
sort(num, 0, num.length - 1);
}
private static void sort(int[] num, int left, int right) {
//递归终止条件
if (left >= right) {
return;
}
//这里设置左边第一个元素为基准值,当然也可以设置右边为基准值,只是实现代码不一样
int pos = num[left];
//双指针法,分别指向 left 和 right
int l = left;
int r = right;
//双指针遍历终止条件
while (l < r) {
/**
* 这里有考究,可以看下面的例子,当上一次循环 left 和 right 指向如下
* 那么判断的顺序就至关重要了,如下代码,可以预测,当退出 while 循环时,
* left 和 right 同时指向了 0
*
* left right
* | |
* 1 2 0 4 6 3
*/
if (num[r] > pos) {
r--;
/**
* 这里的 >= 为什么不可以替换为 > ?
* 因为我们必须保准基准值nums[left] == pos
* 假如 替换成 >
* 那么 nums[left] != pos
* 将会导致我们无法将pos置于中间位置
*/
} else if (num[l] <= pos) {
l++;
} else {//交换数值
int tmp = num[l];
num[l] = num[r];
num[r] = tmp;
}
}
/**
* 此时nums[left] == pos
* nums[l] 指向 小于 pos 的值
* nums[l+i] 全都 大于 pos
* 我们把nums[left] 与 nums[l] 交换位置,就可以实现"nums[l] == pos,并且左边全都小于等于pos,右边全都大于pos"
*/
num[left] = num[l];
num[l] = pos;
/**
* 递归分治
*/
sort(num, left, l - 1);
sort(num, l + 1, right);
}
public static void main(String[] args) {
int CAPACITY = 100;
int[] test = new int[CAPACITY];
for (int i = 0; i < CAPACITY; i++) {
test[i] = (int) (Math.random() * CAPACITY);
}
sort(test);
System.out.println(Arrays.toString(test));
}
}
- 这是第二种实现
java">public class QuitSort {
public static void sort(int[] num) {
sort(num, 0, num.length - 1);
}
private static void sort(int[] num, int left, int right) {
if (left >= right) {
return;
}
int pos = num[right];
int l = left;
int r = right;
while (l < r) {
if (num[l] < pos) {
l++;
} else if (num[r] >= pos) {
r--;
} else {//交换数值
int tmp = num[l];
num[l] = num[r];
num[r] = tmp;
}
}
num[right] = num[l];
num[l] = pos;
sort(num, left, l - 1);
sort(num, l + 1, right);
}
public static void main(String[] args) {
int CAPACITY = 100;
int[] test = new int[CAPACITY];
for (int i = 0; i < CAPACITY; i++) {
test[i] = (int) (Math.random() * CAPACITY);
}
sort(test);
System.out.println(Arrays.toString(test));
}
}
咋一看,好像没什么区别,但是我把不同的代码截取下来,就会发现不一样的地方了
- 对比
这是第一种方法:
这是第二种方法:
所以看出来了吧,尽管两种不太一样的实现方法,它们的本质都是
- 为了保证基准值与中间值进行交换,
- 为了达到这个目的,还必须保证基准值的位置没有改变!,这就是在比较的时候必须使用
>=
或者<=
的理由!