快速排序
排序原理
1、先假定一个分界值,通过该分界值将数组分成左右两个部分;
2、将大于或等于分界值的数据放到数组右边,小于分界值的数据放到数组的左边,此时左边部分中各元素都小于或等于分界值,而右边 部分中各元素都大于或等于分界值。
3、然后,左边和右边的数据可以独立排序,对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放 置最小值,右边放置最大值,右侧的数组数据也可以做类似处理。
4、重复上述过程,可以看出,这是一个递归定义,通过递归将左侧部分排好序后,在递归排好右侧部分的顺序、当左侧和右侧两个部分 的数据排序完毕后,整个数组的排序也就完成了。
原始数据
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
6 | 1 | 2 | 7 | 9 | 3 | 4 | 5 | 8 |
最终代码
public class QuickSort {
public static void main(String[] args) {
int[] value = {6,1,2,7,9,3,4,5,8};
new QuickSort().sort(value);
for (int item : value) {
System.out.print(item + ",");
}
}
public void sort(int[] value){
int right = value.length - 1;
System.out.println("right:" + right);
this.quickSort(value, 0, right);
}
public void quickSort(int[] value, int left, int right){
int l = left;
int r = right;
int baseValue = value[(left+right)/2];
int temp;
while (l < r){
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
System.out.println("l:" + l + " r:" + r);
//交换
temp = value[r];
value[r] = value[l];
value[l] = temp;
if (value[l] == baseValue){
r = r -1;
}
if (value[r] == baseValue){
l = l + 1;
}
}
if (l == r){
l = l + 1;
r = r - 1;
}
if (left < r){
quickSort(value, left, r);
}
if (right > l){
quickSort(value, l, right);
}
}
}
流程分析
上面蓝色箭头代表左指针,右边箭头代表右指针,下面粉红色箭头代表分界值指针。
先从(0,8)这个区间开始, 判断左侧索引是否小于右侧索引,成立则继续执行
让左边指针不停的向右移动,只要数字比参考值小,就继续向右移动,小于或者等于参考值则停下。
让右边指针不停的向左移动,只要数字比参考值大,就继续向左移动,小于或者等于参考值则停下。
......
while (l < r){ //----> l代表左侧索引,----->r代表右侧索引
while (value[l] < baseValue){ //baseValue代表参考值,参考值计算为(l+r) / 2
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
......
左边指针停在 数字(9)上面,说明数字大于或者等于参考值
右边指针停在数字(8)上面,说明数字小于或者等于参考值
判断左指针是否大于或者等于右边指针,如果大于或者相同则停止操作,如果不同则交换两个数字
......
while (l < r){
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){ //就是这个判断
break;
}
//此时左边指针的数字大于参考值,右边指针的数字小于参考值
temp = value[r];
value[r] = value[l];
value[l] = temp;
......
左指针显然没有大于或者等于右边指针,交换数字(9)和(8)的位置
此时判断左边指针的值是否和参考值相等,如果相等就将右边指针向左移动一位
判断右边指针的值是否和参考值相等,如果相等就将左边指针向右移动一位
规律:左边相等,右边指针向左移动一位,右边相等,左边指针向右移动一位
while (l < r){
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
temp = value[r];
value[r] = value[l];
value[l] = temp;
//如果左指针的数和参考值相等,则将右指针向左移动一位
if (value[l] == baseValue){
r = r -1;
}
//如果右指针的数和参考值相等,则将左指针向右移动一位
if (value[r] == baseValue){
l = l + 1;
}
}
左边指针右移一位,继续向右移动,只要数字比参考值小,就继续向右移动,小于或者等于参考值则停下。
while (l < r){ //当l<r时,可以继续执行外层的while循环
//左指针右移继续寻找
while (value[l] < baseValue){
l = l + 1;
}
//右指针此时与参考值相同,不会移动
while (value[r] > baseValue){
r = r - 1;
}
}
找到数字9
判断左指针是否大于或者等于右边指针,如果大于或者相同则停止操作,如果不同则交换两个数字
很显然,左边指针和右边指针相同,停止本次操作
if (l >= r){
break;
}
两边指针相同 ,需要将左边指针向右移动一位,将右边指针向左移动一位(看下图)
若左侧索引小于右边指针,则确定排序范围是(左侧索引,右边指针) ----------->也就是(0,8),这里递归调用了自身
若右侧索引大于左边指针,则确定排序范围(左边指针,右侧索引) --------------------->这里显然就不成立,递归回来不会再调用自身方法
提示这里有递归,判断右侧索引大于左侧指针这一步还没有执行,给个编号:未执行步骤一
public void quickSort(int[] value, int left, int right){
int l = left; //------------------------------->这次left:0
int r = right; //------------------------------->这次right:7
int baseValue = value[(left+right)/2];
int temp;
while (l < r){
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
//交换
temp = value[r];
value[r] = value[l];
value[l] = temp;
if (value[l] == baseValue){
r = r -1;
}
if (value[r] == baseValue){
l = l + 1;
}
}
if (l == r){
l = l + 1;
r = r - 1;
}
if (left < r){ //left:0,r:7
quickSort(value, left, r); // ---->本次执行的是这一步
}
if (right > l){
quickSort(value, l, right); // ----->这一步还没有执行
}
}
在(左侧索引,右边指针)这个区间里进行排序也就是(0,7)
......
while (l < r){ //这里显然是成立的
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
......
条件满足
左边指针依然向右移动,只要数字比参考值小,就继续向右移动,小于或者等于参考值则停下。
右边指针依然向左移动,只要数字比参考值大,就继续向左移动,小于或者等于参考值则停下。
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
左边指针停在 数字(7)上面,说明数字大于或者等于参考值
右边指针停在数字(5)上面,说明数字小于或者等于参考值
左边指针小于右边指针,交换两个数字的位置
if (l >= r){ //不成立,不需要退出循环
break;
}
右边指针 = 参考数字,左侧指针向左移动一位,并继续向右寻找
if (value[l] == baseValue){
r = r -1;
}
if (value[r] == baseValue){
l = l + 1;
}
找到 数字8
if (l >= r){ // 条件不成立
break;
}
左边指针小于右边指针,交换两个数字的位置
此时,左边指针的值 = 参考值 右边指针向左移动一位,并且继续向左移动,直到寻找到小于或者等于参考值的数
这里外层循环while(l<r)成立,继续循环
找到数字4
if (l >= r){ // 条件不成立
break;
}
左边指针小于右边指针,交换两个数字的位置
此时,右边指针的值 = 参考值,左侧指针向右移动,寻找大于或者等于参考值的数
找到数字7
if (l >= r){
break;
}
两边指针相同 ,需要将左边指针向右移动一位,将右边指针向左移动一位
若左侧索引小于右边指针,则确定排序范围是(左侧索引,右边指针)----------------------------->也就是(0,7)
若右侧索引大于左边指针,则确定排序范围(左边指针,右侧索引)------------------------->
if (l == r){
l = l + 1;
r = r - 1;
}
提示这里有递归,判断右侧索引大于左侧指针这一步还没有执行,
public void quickSort(int[] value, int left, int right){
int l = left;
int r = right;
int baseValue = value[(left+right)/2];
int temp;
while (l < r){
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
//交换
temp = value[r];
value[r] = value[l];
value[l] = temp;
if (value[l] == baseValue){
r = r -1;
}
if (value[r] == baseValue){
l = l + 1;
}
}
if (l == r){
l = l + 1;
r = r - 1;
}
if (left < r){ //left:0 r:5
quickSort(value, left, r); // ---->本次执行的是这一步
}
if (right > l){
quickSort(value, l, right); // ----->这一步还没有执行
}
}
在(左侧索引,右边指针)这个区间里进行排序也就是(0,5)
条件成立
......
while (l < r){
while (value[l] < baseValue){
l = l + 1;
}
while (value[r] > baseValue){
r = r - 1;
}
if (l >= r){
break;
}
......
左边指针依然向右移动,只要数字比参考值小,就继续向右移动,小于或者等于参考值则停下。
右边指针依然向左移动,只要数字比参考值大,就继续向左移动,小于或者等于参考值则停下。
这里外层循环显然成立
找到数字6和数字2
左边指针小于右边指针
if (l >= r){
break;
}-
交换位置,右边指针向左移动一位,并继续寻找
找到数字2和数字1
左指针小于右指针
交换位置,左侧指针右移一位,继续寻找
找到数字2
两边指针相同 ,需要将左边指针向右移动一位,将右边指针向左移动一位
移动之后,左指针大于右指针,停止操作。
外层while循环不成立,退出循环 while(l<r)
开始执行递归,执行未操作步骤三
当时的执行区间是(0,5)right的值是5,在上一步左边指针向后移动一位,此时left的值是2
所以未执行步骤三的区间是(2,5)
这里的外层循环显然是成立的
这里很显然我们左边指针停在数字6上面,右边指针停在3上面,交换两个数字
找到数字后的判断不成立,向下执行,交换位置
if (l >= r){
break;
}
很显然下面要找的数字是 5 和 4
显然外层循环成立
while(l<r)
找到数字后的循环判断不成立,交换位置
if (l >= r){
break;
}
交换位置,这里右边指针的值 = 参考值,左指针向右移动一位
if (l >= r){ //找到数之后的判断,成立
break; //退出循环
}
//这里两个指针重合,左指针向右移动,右指针向左移动
if (l == r){
l = l + 1;
r = r - 1;
}
if (left < r){ left:2 r:3
quickSort(value, left, r); ------>调用自身
}
if (right > l){
quickSort(value, l, right); ------>这个暂时没有执行
}
很显然,我们这轮操作什么都没有做,就退出了循环
退出循环后的r:1, l:3
if (left < r){ //--------left:2 r:1
quickSort(value, left, r);
}
if (right > l){ //------right:3 l:3
quickSort(value, l, right);
}
if (right > l){
quickSort(value, l, right); //递归执行:right:5,l:5
}
if (right > l){
quickSort(value, l, right);//递归执行:right:7,l:7
}
if (right > l){
quickSort(value, l, right);//递归执行:right:8,l:9
}
到此,执行完毕,执行main方法中的打印语句