- 時間復(fù)雜度：高效的排序算法迟赃，比較次數(shù)和移動次數(shù)都應(yīng)該盡可能的少诬辈。
- 空間復(fù)雜度：算法執(zhí)行期所需要輔助空間和待排序的數(shù)據(jù)量無關(guān)颓哮。理想空間復(fù)雜度為O(1)
簡述
快速排序可以說算是針對冒泡排序的一種優(yōu)化常摧，冒泡排序是順序交換磕洪，這樣交換次數(shù)順序增長吭练。如果我們做跳躍的交換，那么可以使得交換次數(shù)也是跳躍性析显，會有所降低
算法思想
- 找出一個樞軸鲫咽，用于做比較交換，并記下后用谷异。一般用第一個(用第一分尸、中間、最后三個取中后來效果會更好)歹嘹，定一個高位:high和底位:low
- 從表的高位開始箩绍，往左進(jìn)行比較，找到一個關(guān)鍵字小于樞軸尺上，則將high和樞軸交換材蛛。否則high--
- 從表的低位開始，往右進(jìn)行比較怎抛，找到一個關(guān)鍵字大于等于樞軸卑吭，則將low和樞軸交換。否則low++
- 重復(fù)2和3步马绝，直到low==high位置豆赏，此時low和high的位置則是樞軸在本趟排序在表的最終位置，成功將表分成比樞軸小和比樞軸大兩個字表在樞軸左右兩側(cè)。
以上2和3步驟河绽，每次交換己单，要做三次記錄：
一次移動low到high，一次移動high到low耙饰，加中間借助了temp這一類的纹笼。
我們可以減少移動記錄：
比如一開始記錄下樞軸值，在每次移動的時候苟跪，只移動要與樞軸交換的記錄廷痘，移動完成后，最后將開始記錄下的樞軸關(guān)鍵字放入最終的樞軸位置件已。
算法實(shí)現(xiàn)
private static class QuickSortClass {
/**
* 進(jìn)行快速排序
*/
public void quickSort() {
List<Integer> integers = new ArrayList<>();
int[] intArray = new int[]{1, 44, 3, 33, 77, 25, 98, 221, 33, 16};
for (int value : intArray) {
integers.add(value);
}
eSort(integers, 0, intArray.length - 1);
System.out.print(integers);
}
/**
* 計算樞軸位置笋额，通過進(jìn)行一輪交換得到新的樞軸位置
*
* @param ints
* @return 返回交換后的樞軸的位置
*/
private int evaluatePrivotPartition(List<Integer> ints, int l, int h) {
/*第一步：先選取樞軸記錄，使用三者取中原則篷扩，我們用第一個兄猩、中間一個、最后一個來比較大小鉴未，
取中間大小中間一個為樞軸記錄并與第一個交換*/
int low = l;
int high = h;
int oneValue = ints.get(low);
System.out.println("oneValue=" + oneValue);
int centerPart = (high + low) / 2;
int centerValue = ints.get(centerPart);
System.out.println("centerValue=" + centerValue);
int lastValue = ints.get(high);
System.out.println("lastValue=" + lastValue);
int privotDef = oneValue;
//取出中間一個枢冤，做中樞記錄,如果不用此步驟，那么默認(rèn)選第一個
if (oneValue > Math.min(centerValue, lastValue) && oneValue < Math.max(centerValue, lastValue)) {
privotDef = oneValue;
} else if (centerValue > Math.min(oneValue, lastValue) && oneValue < Math.max(oneValue, lastValue)) {
privotDef = centerValue;
//交換中樞位置
ints.set(low, centerValue);
ints.set(centerPart, oneValue);
} else {
privotDef = lastValue;
ints.set(low, lastValue);
ints.set(high, oneValue);
}
System.out.println("樞軸記錄:privotDef=" + privotDef);
/*重復(fù)第二三步铜秆，直到low==high為止*/
while (low < high) {
/*每一輪的交換執(zhí)行*/
//第二步：從high往左,如果high位置的值大于等于樞軸記錄淹真，那么high--
while (low < high
&& ints.get(high) >= privotDef) {
high--;
}
//小于樞軸值時候，需要和做交換连茧，將high移到low
if (low < high) {
ints.set(low, ints.get(high));
}
//第三步：從low往右,如果low位置的值小于等于樞軸記錄核蘸，那么low++
while (low < high
&& ints.get(low) <= privotDef) {
low++;
}
//找到比樞軸記錄大的值，那么low換到high
if (low < high) {
ints.set(high, ints.get(low));
}
}
//將記錄下來的樞軸放入low位置啸驯，樞軸記錄到位
ints.set(low, privotDef);
for (Integer value : ints) {
System.out.print(value + " ");
}
System.out.print("\n");
return low;
}
/**
* 執(zhí)行快速排序入口
*
* @param ints
* @param low
* @param high
*/
private void eSort(List<Integer> ints, int low, int high) {
//只要low和high不相等,就代表交換后子表長度依舊大于1
if (low < high) {
int privotP = evaluatePrivotPartition(ints, low, high);
eSort(ints, low, privotP - 1);//對左字表進(jìn)行遞歸排序
eSort(ints, privotP + 1, high);//對右字表進(jìn)行遞歸排序
}
}
}
- 客戶端調(diào)用
public static void main(String[] args) {
System.out.println("Hello World!");
new QuickSortClass().quickSort();
}
可以看到客扎，在evaluatePrivotPartition中有一個,取中間值的步驟，不加那一步也是可以坯汤，跑一下你就會發(fā)現(xiàn)虐唠，本次排序用了6趟。如果不加那一步惰聂，則默認(rèn)使用第一個為樞軸記錄疆偿，最后排序下來的趟數(shù)會是7趟。
不要小看只多了一趟搓幌，如果數(shù)更大杆故，優(yōu)勢會更明顯。
算法分析
- 時間復(fù)雜度
可以看下排序的遞歸樹：
image
大致也能看出溉愁，排序的躺數(shù)取決于遞歸樹的深度.
- 最好的情況：每一趟都能將記錄均勻分割成兩個長度大致相等的子表处铛，類似折半查找饲趋。n個序列，樞軸定位時間O(n)撤蟆，若T(n)是對n個元素進(jìn)行排序所需對時間奕塑，且每次定位，正好把序列劃分為長度相等的兩個子表家肯，設(shè)Cn是一個常數(shù)龄砰，表示n個元素進(jìn)行一趟快速排序的時間，則總時間：
T(n)=Cn+2T(n/2)
T(n) <=n+2T(n/2)
繼續(xù)往下得到T(n)約等于O(nlog2n)
- 最壞的情況：帶排序序列已經(jīng)排好的情況下讨衣，其遞歸數(shù)為單只樹换棚，每次劃分得到一個比上一個少的序列，這樣必須經(jīng)過n-1趟才能將所有記錄定位反镇，而且第i趟需要經(jīng)過n-i次比較固蚤，比較次數(shù)就為n2/2
為了避免最壞情況，所以我們可以使用三者取中原則進(jìn)行選取樞軸記錄歹茶，就是前面代碼用到的方式
- 空間復(fù)雜度
排序是遞歸的夕玩，所以需要有一個棧來存放相應(yīng)的數(shù)據(jù)。最大遞歸調(diào)用次數(shù)與遞歸樹的深度一致惊豺。為O(log2n)风秤，最壞情況下為O(n)
算法特點(diǎn)
- 不穩(wěn)定：記錄非順序次地移動導(dǎo)致
- 難用于鏈?zhǔn)浇Y(jié)構(gòu)：需要定位表的下界和上界，適合順序結(jié)構(gòu)
- 平均來說扮叨，快排可以說是內(nèi)部排序中最快的一種了，在初始無序领迈，n比較大的情況彻磁，使用快排是比較合適的。
