快速排序是對(duì)冒泡排序的一種改進(jìn)，他的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分料仗，其中的一部分的所有數(shù)據(jù)都比另一個(gè)部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行吗货，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
排序原理：
1.首先設(shè)定一個(gè)分界值狈网，通過(guò)該分界值將數(shù)組分成左右兩部分宙搬。
2.將大于或等于分界值的數(shù)據(jù)放到數(shù)組右邊，小于分界值的放到數(shù)組左邊拓哺。此時(shí)左邊部分中各元素都小于或等于分界值勇垛，而右邊部分中各元素都大于或等于分界值。
3.然后士鸥，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序闲孤。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值烤礁，將該部分?jǐn)?shù)據(jù)讼积，分成左右兩部分，同樣在左邊放置較小值鸽凶，右邊放置較大值币砂。右側(cè)的數(shù)組數(shù)據(jù)同樣做類似的處理。
4.重復(fù)上述過(guò)程玻侥，可以看出這是一個(gè)遞歸定義决摧。通過(guò)遞歸將左邊部分排序好，再將右邊部分排序好凑兰，這樣整個(gè)數(shù)組都排序完成了掌桩。
API設(shè)計(jì)：
//比較v與w的大小
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//交換索引i與索引j位置的元素
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
//遞歸調(diào)用sort的重載方法。
public static void sort(Comparable[] a) {
int low = 0;
int high = a.length-1;
sort(a,low,high);
}
private static void sort(Comparable[] a, int low, int high) {
//安全校驗(yàn)姑食，如果輸入的索引位置有誤波岛，直接break
if (high<=low){
return;
}
//分界值的索引（變換后的索引）
int partition = partition(a, low, high);
//以索引位置兩邊進(jìn)行排序
sort(a,low,partition-1);
sort(a,partition+1,high);
}
//切分
public static int partition(Comparable[] a, int low, int high) {
//確定分界值
Comparable key = a[low];
//定義兩個(gè)指針，分界指向待切分元素的最小索引處和最大索引處的下一個(gè)位置音半。
Integer left = low;
Integer right = high+1;
//循環(huán)掃描進(jìn)行切分则拷。
while (true){
//從右往左掃描，移動(dòng)right指針曹鸠，找到比分界值小的元素
while (less(key,a[--right])){
//當(dāng)兩個(gè)指針相遇煌茬，已經(jīng)掃描所有的元素，停止切分
if (right==low){
break;
}
}
//從左往右掃描彻桃，移動(dòng)left指針绍赛，找到比分界值大的元素
while (less(a[++left],key)){
if (left==high){
break;
}
}
//掃描完畢后雷，結(jié)束掃描
if (left>=right){
break;
}else {
exch(a,left,right);
}
}
exch(a,low,right);
return right;
}
測(cè)試類：
public class QuickTest {
public static void main(String[] args) {
Integer[] arr = {6,1,2,7,9,3,4,5,8};
Quick.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
image.png
