黑马程序员技术交流社区
标题:
小白的快速排序
[打印本页]
作者:
仓耳
时间:
2019-5-24 16:57
标题:
小白的快速排序
public class QuicklySort {
public void quicklySort(int[] arr, int base, int tail){
/*
* 快速排序的核心:选取一个参考点,然后操作此数组,得到参考点的值左边的值全都比参考点值小,右边的值全都比参考点的大
* 然后将左边作一个子序列,右边看作另外一个子序列([XXXXXXXXX 参考值 XXXXXXXXXXXXXXXXXXXX]),然后分别对这两个子序列
* 做相同的事情(递归),直到子序列为长度1或者0(小于2个).[XXXXX参考值]-->此时右边子序列长度为0,[XXXXX参考值X]-->右边子序列长度为1;
*
* 在这个程序中,将原始数组操作的方法是:
* 1.设一个left索引点,从左边开始找,找到大于参考点值的记录为left(此时left左边的都比参考点小)#注:left不能超过此次要排序的片段的最右边对吧?;
* 同时设一个right索引点,从右边开始找,找到小于参考点的记录为right(此时tight右边的都比参考的大)#注:right不能超过此次要排序的片段的最左边对吧?;
* (如果想把与参考值相同的都一口气都放在左边,在则left遇到相等就跳过,right遇到相等就记录)别把全部相等放右边,因为这样第一个参考点必定会被left记录,虽然这总结果换过来一定是小于等于参考点的新参考点,不会报错,但是这样做会使得左子序列变短,导致降低排序效率
* (也可以把参考值相同的不管,都跳过,因为既可以当做大于参考值的,也可做小于参考值的) 这种效率应该最高
* 2.如果left<right,则交换 left和right指向的值. 然后继续寻找(重复第一步)
* 直到left>right,(不会出现left等于right的情况的--),因为不存在一个值既小于又大于参考值,与参考值相等时候,我们也会保证其中一个跳走,或者一起跳走
*
* 3.交换参考点和right的值(此时left记录的是比参考点值大的,right记录的是比参考点值小的,跟right交换则保证了左边全部小于参考值,右边全部大于)达到目的
*
* 4.当子序列长度大于1时候才进行递归 左边子序列(base--->right-1) right-1>base时候就长度超过1
* 右边子序列(right+1--->tail) tail>right+1时候就长度超过1
*
*
*/
int left=base; //base和tail是将传入数组的,本次递归需要排序的部分的,起始索引记录保存下来,
int right=tail;//并且以base的值为参考点(这个点值拿来参考作用,本身要参与排序的,所以left要从过这里开始).
int temp=0;// 交换数组中两个值用的暂存值
while (left<right) {//每次交换完后,只要还满足left<right就继续找
while (true) {//用死循环,在此次排序片段的范围内,找arr[left] > arr[base]的点处的索引,记录下left
if (left < tail && arr[left] <= arr[base]) {
left++;
} else {
break;
}
}
while (true) {//用死循环,在此次排序片段的范围内,找arr[right] <arr[base]的点处的索引,记录下
if (right > base && arr[right] >= arr[base]) {
right--;
} else {
break;
}
}
if (left < right) { //记录下来的left小于right时候交换值
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//交换base 和right
temp = arr[base];
arr[base] = arr[right];
arr[right] = temp;
if (right - 1 > base) {//子序列长度超过1
quicklySort(arr, base, right - 1);
}
if (right + 1 <tail) {//子序列长度超过1
quicklySort(arr, right + 1, tail);
}
}
}
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2