国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 網站 > WEB開發 > 正文

JS實現快速排序(QuickSort)

2024-04-27 15:15:34
字體:
來源:轉載
供稿:網友

偶然看到阮一峰老師博客中幾年前的一個快速排序算法,每次循環一次都要創建兩個額外數組,如果數據量大的話要占用不少額外內存。但是數組是引用類型,是可修改的,可以直接操作原數組本身來節約內存。

下面自己寫了一個,當做練手。(除去標準的雙向分類外,還稍稍優化了代碼,也加了單項優化方法,使其更加簡潔)

快速排序方法的關鍵在于選取一個值,將整個數組分為兩部分,小的在左,大的在右,下面就是這個函數的寫法:

//該函數的主要目的是交換數組中兩個元素的位置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


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 宁乡县| 彭州市| 伊通| 谷城县| 巫山县| 新安县| 蒙山县| 台北市| 都安| 濮阳市| 无棣县| 于都县| 西盟| 长宁县| 徐闻县| 西乌珠穆沁旗| 景谷| 政和县| 惠州市| 深州市| 东安县| 额尔古纳市| 泰宁县| 刚察县| 溧水县| 辽宁省| 东平县| 枣庄市| 梁平县| 石景山区| 元朗区| 砀山县| 佛教| 车致| 邢台市| 西藏| 永登县| 寻甸| 岱山县| 闸北区| 中卫市|