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