快速排序记劈，可以稱得上是21世紀(jì)最偉大的算法之一，它的性能也是相當(dāng)不錯的并巍，它的平均時間復(fù)雜度是O(nlogn)是一種非常高效的算法目木，幾乎我們每門語言當(dāng)中的系統(tǒng)排序算法中都有一部分是基于快速排序算法實現(xiàn)的。
快速排序的思想也很簡單懊渡，就是每一次刽射，都將一個數(shù)送到它最終的位置上面华匾，并且它前面的數(shù)都比它小八秃，后面的數(shù)都比它大，每一輪都這樣然后遞歸執(zhí)行风范，最終就會實現(xiàn)整個數(shù)組完全有序的狀態(tài)肾档。
當(dāng)然快排的優(yōu)點肯定是平均性能好摹恰，但是快排對于已經(jīng)比較接進(jìn)完全有序的數(shù)組，會暴露出自己的問題怒见，這時它會達(dá)到自己的最壞的性能俗慈，目前解決這種問題的方法也有很多，當(dāng)然只能減少這中情況的發(fā)生遣耍，并不能避免闺阱，但在數(shù)學(xué)期望的角度上，會讓它的性能更優(yōu)舵变，具體做法：
1.我們可以在快速排序一個數(shù)組之前酣溃，運(yùn)行一個算法來打亂原數(shù)組
2.我們可以每次選定標(biāo)準(zhǔn)的時候，并不選擇第一個數(shù)棋傍，而是隨機(jī)選定一個待排序范圍內(nèi)的數(shù)字
我們現(xiàn)在就可以自己實現(xiàn)一個二路快速排序算法：
/**
* Created by linSir on 17/2/10.
*/
function paration(list, l, r) {
var first = list[l];
var left = l;
var right = r;
var temp;
while (left < right) {
while (list[right] > first && left < right) {
right--;
}
if (left < right) {
list[left] = list[right];
left++;
}
while (list[left] <= first && left < right) {
left++;
}
if (left < right) {
list[right] = list[left];
right--;
}
list[left] = first;
}
return left;
}
function quickSort(list, l, r) {
if (l >= r) {
return;
}
var temp;
temp = paration(list, l, r);
console.log(temp);
quickSort(list, l, temp - 1);
quickSort(list, temp + 1, r);
return list;
}
var list = [3, 1, 2, 4, 5, 6, 7];
console.log(quickSort(list, 0, 6));
結(jié)果：
運(yùn)行效果圖
現(xiàn)在我們所寫的算法就是基本的快速排序算法了救拉。
