偶然看到阮一峰老師博客中幾年前的一個快速排序算法，每次循環一次都要創建兩個額外數組，如果數據量大的話要占用不少額外內存。但是數組是引用類型，是可修改的，可以直接操作原數組本身來節約內存。
下面自己寫了一個，當做練手。（除去標準的雙向分類外，還稍稍優化了代碼，也加了單項優化方法，使其更加簡潔）
快速排序方法的關鍵在于選取一個值，將整個數組分為兩部分，小的在左，大的在右，下面就是這個函數的寫法：
//該函數的主要目的是交換數組中兩個元素的位置function swap(arr, index1, index2) { let data = arr[index1]; arr[index1] = arr[index2]; arr[index2] = arr[index1]; //數組是引用類型，允許修改原數組。}//選取隨機值，將數組分為兩部分function partition(arr, start, end) { let keyIndex = end, key = arr[keyIndex]; //將隨機值(以后稱key值)定為最后一個數，也可以真的隨機選取，見下一行 // let keyIndex = Math.floor(Math.random() * (end - start)) + start; let i = start, j = end, order = true; //當order為true時正向篩選，當order為false時逆向篩選 //先從正向開始，因為我們把key值保存到了數組的結尾處。 while(i != j) { if(order) { //正向篩選 if (arr[i]>key) { swap(arr, i, j); //將大于key的數字和key進行交換 order = false; } else { i++; } } else { //逆向篩選 if(arr[j]<key) { swap(arr, i, j); //將小于key的數字和key進行交換 order = true; } else { j--; } } } return i;//返回key值最終的位置}觀察分組算法partition不難發現，其實i和j位置上始終有一個存著key值，然后和比它大或者比它小的值進行交換。那么我們也可以將其寫成一個單向的分組方法：
function partition2(arr, start, end) { let keyIndex = end, key = arr[end]; let i = start -1, j = start; for (;j<end;j++) { if (arr[j]< key) { // i位置的值永遠比key值小 i++; if (i != j) { swap(arr, i, j); } } } ++i; swap(arr, i, end); return i; //返回key值最終的位置}接下來遞歸調用分組函數，將整個數組排序：
function quickSort(arr, start, end) { if (start == end) return; let index = partition(arr, start, end); if (index > start){ quickSort(arr, start, index-1); } if (index<end) { quickSort(arr, index+1, end); }}代碼請見： https://github.com/jian-cui/algorithm/blob/master/quickSort.js
新聞熱點
疑難解答
