//聯(lián)系人:石虎QQ:1224614774 昵稱:嗡嘛呢叭咪哄
一狼速、概念:
快速排序: 是高快省的排序算法,在快速排序算法中，使用了分治策略卦停。首先把序列分成兩個子序列向胡，遞歸地對子序列進(jìn)行排序，直到整個序列排序結(jié)束惊完。
優(yōu)點:
快速排序之所比較快僵芹，因為相比冒泡排序，每次交換是跳躍式的小槐。每次排序的時候設(shè)置一個基準(zhǔn)點拇派，將小于等于基準(zhǔn)點的數(shù)全部放到基準(zhǔn)點的左邊，將大于等于基準(zhǔn)點的數(shù)全部放到基準(zhǔn)點的右邊本股。
這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換攀痊，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了拄显，速度自然就提高了苟径。
空間復(fù)雜度:
當(dāng)然在最壞的情況下，仍可能是相鄰的兩個數(shù)進(jìn)行了交換躬审。因此快速排序的最差時間復(fù)雜度和冒泡排序是一樣的都是O(N2)棘街，它的平均時間復(fù)雜度為O(NlogN)蟆盐。
代碼實現(xiàn)
voidsort(int*a,intleft,intright) {
if(left >= right)return;
inti = left;
intj = right;
intkey = a[left];
while(i < j) {
while(i < j && key >= a[j]) {
j--;
}
a[i] = a[j];
while(i < j && key <= a[i]) {
i++;
}
a[j] = a[i];
}
a[i] = key;
sort(a, left, i-1);
sort(a, i+1, right);
}
二、快速排序的原理圖
???? 快速排序的每一輪處理其實就是將這一輪的基準(zhǔn)數(shù)歸位遭殉，直到所有的數(shù)都?xì)w位為止石挂，排序就結(jié)束了。下面上個霸氣的圖來描述下整個算法的處理過程险污。
圖:幫助理解
注意:此圖非作者繪制;
