转载声明:文章来源https://blog.csdn.net/Swofford/article/details/122263215
一.概述
快速排序是对冒泡排序的一种改进。
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
二.原理
1.首先设定一个分界值(默认为第一个数),通过该分界值将数组分成左右两部分;
2.将大于或等于分界值的数据放到到数组右边,小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值;
3.然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了。
具体的切分过程:
1.找一个基准值(默认为第一个元素),用两个指针分别指向数组的头部和尾部;
2.先从右向左开始搜索一个比基准值小的元素,搜索到即停止,并记录指针的位置;
3.再从左向右开始搜索一个比基准值大的元素,搜索到即停止,并记录指针的位置;
4.交换当前左边指针位置和右边指针位置的元素;
5.重复2,3,4步骤,直到左边指针的值大于右边指针的值停止。
例:
设定基准值,并准备两个指针,left指针指向分界值所在的索引lo处,right指针指向hi+1。
思路:right指针从右往左走,找到比6小的元素;然后left从左往右走,找到比6大的元素(双向排查),而后两数交换。
第一次,right指针左移一位,指向8,8>6,不满足。再左移来到5,5<6,满足,指针暂停在5处。
同理,left指针右移,寻找比6大的元素,依次移到 1 2 都不满足,直到指向7,7>6,满足条件。
交换right指针指向的“5”和left指针指向的“7”。
将两个指针指向的元素交换之后,right指针继续左移找到4<6,然后left左移找到9>6,交换4和9。
Again,right指针左移找到3<6,指针停在3。left指针右移到3也就是right指针的位置,此时满足条件 (left>=right) ,left和right指针重合,即代表此时两个指针扫描完毕,这时交换分界值6 和两个指针共同指向的值3。
到此这一数组的切分完成,然后以分界值为界,将其分为两个数组,再重复以上步骤。
三.Java代码实现
public class quick {
public static void sort(int[] a){
int lo=0;
int hi=a.length-1;
sort(a,lo,hi);
}
public static void sort(int[]a,int lo,int hi){
if(lo>=hi){//安全校验,即递归出口
return;
} //前序遍历
int partition=partition(a,lo,hi); //排序并返回分界值交换后的索引
//先排序,再切分! 即前序遍历
sort(a,lo,partition-1);
sort(a,partition+1,hi);
}
private static int partition(int[] a, int lo, int hi) {
//确定分界值
int key=a[lo];
//定义两个指针,分别指向分界值的索引处和最大索引处下一位
int left=lo;
int right=hi+1;
//切分
while(true) {
//先右
while (a[--right]>key) {//找的是right < key ,循环条件相反。
if(right==lo){
break;} // 越界,跳出while
}
//后左
while(a[++left]<key){ //找的是left>key,循环条件相反
if(left==hi){
break; // 越界,跳出while
}
}
if(left>=right){ //指针重合,跳出最外层循环
break;
}else{ //指针还未重合,则交换左、右指针处元素
swap(a,left,right);
}
}
swap(a,lo,right); //最后交换分界值和重合处元素
return right; //返回分界值交换后的索引
}
public static void swap(int[] a,int lo,int hi){
int k=a[lo];
a[lo]=a[hi];
a[hi]=k;
}
public static void main(String[] args) {
int[]a={6, 1, 2, 7, 9, 3, 4, 5, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
运行结果:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
注意:
快速排序是先排序!并返回一个分界值的索引 int值,再进行递归,当递归到最后时,数组已经排序完成(分组的过程中就已经排序了,分完组的时候也就排好序了);
归并排序是先使用递归来分组,分组完成后 再调用merge进行归并排序。(自底向上,分组完之后才开始依次使用merge进行归并)
判断左右指针是否重合的条件必须是if(left>=right){ break;}
而不能是if(left==right){ break;} 。因为左右指针都在移动,如果使用left==right来判断有可能错开。
partition 返回的必须是right ,不能是left !
进我收藏夹吃灰去吧