冒泡排序
排序的效果圖
解法
當(dāng)前解法為升序
冒泡排序的特點(diǎn)，是一個(gè)個(gè)數(shù)進(jìn)行處理。第i個(gè)數(shù)，需要與后續(xù)的len-i-1個(gè)數(shù)進(jìn)行逐個(gè)比較。
為什么是 `len-i-1`個(gè)數(shù)？
因?yàn)閿?shù)組末尾的i個(gè)數(shù)，已經(jīng)是排好序的，確認(rèn)位置不變的了。
為什么確認(rèn)位置不變，因?yàn)樗鼈児潭ㄏ聛?lái)之前，已經(jīng)和前面的數(shù)字都一一比較過(guò)了。
1. function bubbleSort(arr){
2. const len = arr.length;
3. for(let i = 0; i < len - 1; i++){
4. for(let j = 0; j < len - i - 1; j++){
5. if(arr[j] > arr[j+1]){
6. const tmp = arr[j+1];
7. arr[j+1] = arr[j];
8. arr[j] = tmp;
9. }
10. }
11. }
12.
13. return arr;
14.}
快速排序
概要
快速排序，使用的是分治法的思想。
通過(guò)選定一個(gè)數(shù)字作為比較值，將要排序其他數(shù)字，分為 >比較值 和 <比較值，兩個(gè)部分。并不斷重復(fù)這個(gè)步驟，直到只剩要排序的數(shù)字只有本身，則排序完成。
效果圖
解法
1. function quickSort(arr){
2. sort(arr, 0, arr.length - 1);
3. return arr;
4. function sort(arr, low, high){
5. if(low >= high){
6. return;
7. }
8. let i = low;
9. let j = high;
10. const x = arr[i]; // 取出比較值x，當(dāng)前位置i空出，等待填入
11. while(i < j){
12. // 從數(shù)組尾部，找出比x小的數(shù)字
13. while(arr[j] >= x && i < j){
14. j--;
15. }
16. // 將空出的位置，填入當(dāng)前值， 下標(biāo)j位置空出
17. // ps：比較值已經(jīng)緩存在變量x中
18. if(i < j){
19. arr[i] = arr[j]
20. i++;
21. }
22. // 從數(shù)組頭部，找出比x大的數(shù)字
23. while(arr[i] <= x && i < j){
24. i++;
25. }
26. // 將數(shù)字填入下標(biāo)j中，下標(biāo)i位置突出
27. if(i < j){
28. arr[j] = arr[i]
29. j--;
30. }
31. // 一直循環(huán)到左右指針i、j相遇，
32. // 相遇時(shí)，i==j, 所以下標(biāo)i位置是空出的
33. }
34. arr[i] = x; // 將空出的位置，填入緩存的數(shù)字x，一輪排序完成
35. // 分別對(duì)剩下的兩個(gè)區(qū)間進(jìn)行遞歸排序
36. sort(arr, low, i - 1);
37. sort(arr, i+1, high);
38. }
39.}
希爾排序
概要
希爾排序是一種插入排序的算法，它是對(duì)簡(jiǎn)單的插入排序進(jìn)行改進(jìn)后，更高效的版本。由希爾（Donald Shell）于1959年提出。
特點(diǎn)是利用增量，將數(shù)組分成一組組子序列，然后對(duì)子序列進(jìn)行插入排序。
由于增量是從大到小，逐次遞減，所以也稱為縮小增量排序。
效果圖
解法
注意點(diǎn)
插入排序時(shí)，并不是一個(gè)分組內(nèi)的數(shù)字一次性用插入排序完成，而是每個(gè)分組交叉進(jìn)行。
執(zhí)行插入時(shí)，使用交換法
1. function shellSort(arr){
2. // 分組規(guī)則 gap/2 遞減
3. for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
4. for(let i = gap; i < arr.length; i++){
5. let j = i;
6. // 分組內(nèi)數(shù)字，執(zhí)行插入排序，
7. // 當(dāng)下標(biāo)大的數(shù)字，小于 下標(biāo)小的數(shù)字，進(jìn)行交互
8. // 這里注意，分組內(nèi)的數(shù)字，并不是一次性比較完，需要i逐步遞增，囊括下個(gè)分組內(nèi)數(shù)字
9. while(j - gap >= 0 && arr[j] < arr[j - gap]){
10. swap(j, j-gap);
11. j = j - gap;
12. }
13. }
14. }
15.
16. return arr;
17.
18. function swap(a, b){
19. const tmp = arr[a];
20. arr[a] = arr[b];
21. arr[b] = tmp;
22. }
23.}
執(zhí)行插入時(shí)，使用移動(dòng)法
1. function shellSort(arr){
2.
3. for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
4. for(let i = gap; i < arr.length; i++){
5. let j = i;
6. const x = arr[j]; // 緩存數(shù)字，空出位置
7.
8. while(j - gap >= 0 && x < arr[j-gap]){
9. arr[j] = arr[j - gap]; // 將符合條件的數(shù)字，填入空出的位置
10. j = j - gap;
11. }
12. arr[j] = x; // 最后，將緩存的數(shù)字，填入空出的位置
13. }
14. }
15.
16. return arr;
17.}
選擇排序
排序的效果圖
解法
當(dāng)前解法為升序
1. function selectionSort(arr){
2. const len = arr.length;
3.
4. for(let i = 0; i < len-1; i++){
5. let minIndex = i;
6. for(let j = i+1; j < len; j++){
7. if(arr[j] < arr[minIndex]){
8. minIndex = j; // 保存最小數(shù)的下標(biāo)
9. }
10. }
11.
12. const tmp = arr[i];
13. arr[i] = arr[minIndex];
14. arr[minIndex] = tmp;
15. }
16.
17. return arr;
18.}
歸并排序
概要
歸并排序，利用分治思想，將大的數(shù)組，分解為小數(shù)組，直至單個(gè)元素。然后，使用選擇排序的方式，對(duì)分拆的小數(shù)組，進(jìn)行回溯，并有序合并，直至合并為一個(gè)大的數(shù)組。
效果圖
小數(shù)組合并的過(guò)程
解法
1. function mergeSort(arr){
2. return sort(arr, 0, arr.length - 1); // 注意右區(qū)間是arr.length - 1
3. // sort方法，進(jìn)行遞歸
4. function sort(arr, left, right){
5. // 當(dāng)left !== right時(shí)，證明還沒分拆到最小元素
6. if(left < right){
7. // 取中間值，分拆為兩個(gè)小的數(shù)組
8. const mid = Math.floor((left+right) / 2);
9. const leftArr = sort(arr, left, mid);
10. const rightArr = sort(arr, mid+1, right);
11. // 遞歸合并
12. return merge(leftArr, rightArr)
13. }
14. // left == right, 已經(jīng)是最小元素，直接返回即可
15. return left >= 0 ? [arr[left]] : [];
16. }
17. // 合并兩個(gè)有序數(shù)組
18. function merge(leftArr, rightArr){
19. let left = 0;
20. let right = 0;
21. const tmp = [];
22. // 使用雙指針，對(duì)兩個(gè)數(shù)組進(jìn)行掃描
23. while(left < leftArr.length && right < rightArr.length){
24. if(leftArr[left] <= rightArr[right]){
25. tmp.push(leftArr[left++]);
26. }else{
27. tmp.push(rightArr[right++]);
28. }
29. }
30. // 合并剩下的內(nèi)容
31. if(left < leftArr.length){
32. while(left < leftArr.length){
33. tmp.push(leftArr[left++]);
34. }
35. }
36. if(right < rightArr.length){
37. while(right < rightArr.length){
38. tmp.push(rightArr[right++]);
39. }
40. }
41. return tmp;
42. }
43.}
插入排序
排序的效果圖
解法
當(dāng)前解法為升序
1. function insertionSort(arr){
2. const len = arr.length;
3. // 注意，i 從 1 開始
4. for(let i = 1; i < len; i++){
5. let preIndex = i - 1;
6. let current = arr[i];
7. // 位置i之前，是已排好序的數(shù)字，while的作用是找到一個(gè)坑位，給當(dāng)前數(shù)字current插入
8. while(preIndex >= 0 && arr[preIndex] > current){
9. arr[preIndex+1] = arr[preIndex]; // 對(duì)大于current的值，往后移一位，給current的插入騰出位置
10. preIndex--;
11. }
12. arr[preIndex+1] = current;
13. }
14. return arr;
15.}
堆排序
概要
堆的表示形式
邏輯結(jié)構(gòu)的表示如下：
在物理數(shù)據(jù)層的表示如下：
堆排序，是選擇排序的優(yōu)化版本，利用數(shù)據(jù)結(jié)構(gòu)——樹，對(duì)數(shù)據(jù)進(jìn)行管理。
以大頂堆為例:
通過(guò)構(gòu)建大頂堆
將堆頂?shù)淖畲髷?shù)拿出，與堆底的葉子節(jié)點(diǎn)進(jìn)行交換
接著，樹剪掉最大數(shù)的葉子
再對(duì)堆進(jìn)行調(diào)整，重新變成大頂堆
返回步驟2，以此循環(huán)，直至取出所有數(shù)
效果圖
在實(shí)現(xiàn)代碼時(shí)，構(gòu)建大頂堆時(shí)，先保證左右子樹的有序，再逐步擴(kuò)大到整棵樹。
構(gòu)建大頂堆
從第一個(gè)非葉子節(jié)點(diǎn)開始，調(diào)整它所在的子樹
調(diào)整下標(biāo)1節(jié)點(diǎn)的子樹后，向上繼續(xù)調(diào)整它的父節(jié)點(diǎn)（下標(biāo)0）所在的子樹
最后，完成整個(gè)樹的調(diào)整，構(gòu)建好大頂堆。
逐個(gè)抽出堆頂最大值
堆頂數(shù)字與最末尾的葉子數(shù)字交換，抽出堆頂數(shù)字9。
此時(shí)，數(shù)字9位置固定下來(lái)，樹剪掉9所在的葉子。然后，重新構(gòu)建大頂堆。
大頂堆構(gòu)建好后，繼續(xù)抽出堆頂數(shù)字8，然后再次重新構(gòu)建大頂堆。
最后，所有節(jié)點(diǎn)抽出完成，代表排序已完成。
解法
以大頂堆為例，對(duì)數(shù)組進(jìn)行升序排序
注意點(diǎn)
樹的最后一個(gè)非葉子節(jié)點(diǎn)：(arr.length / 2) - 1
非葉子節(jié)點(diǎn)i的左葉子節(jié)點(diǎn)： i*2+1
非葉子節(jié)點(diǎn)i的右葉子節(jié)點(diǎn)： i*2+2
1. function heapSort(arr){
2. // 初次構(gòu)建大頂堆
3. for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--){
4. // 開始的第一個(gè)節(jié)點(diǎn)是 樹的最后一個(gè)非葉子節(jié)點(diǎn)
5. // 從構(gòu)建子樹開始，逐步調(diào)整
6. buildHeap(arr, i, arr.length);
7. }
8. // 逐個(gè)抽出堆頂最大值
9. for(let j = arr.length -1 ; j > 0; j--){
10. swap(arr, 0, j); // 抽出堆頂（下標(biāo)0）的值，與最后的葉子節(jié)點(diǎn)進(jìn)行交換
11. // 重新構(gòu)建大頂堆
12. // 由于上一步的堆頂最大值已經(jīng)交換到數(shù)組的末尾，所以，它的位置固定下來(lái)
13. // 剩下要比較的數(shù)組，長(zhǎng)度是j,所以這里的值length == j
14. buildHeap(arr, 0, j);
15. }
16. return arr;
17. // 構(gòu)建大頂堆
18. function buildHeap(arr, i, length){
19. let tmp = arr[i];
20. for(let k = 2*i+1; k < length; k = 2*k+1){
21. // 先判斷左右葉子節(jié)點(diǎn)，哪個(gè)比較大
22. if(k+1 < length && arr[k+1] > arr[k]){
23. k++;
24. }
25. // 將最大的葉子節(jié)點(diǎn)，與當(dāng)前的值進(jìn)行比較
26. if(arr[k] > tmp){
27. // k節(jié)點(diǎn)大于i節(jié)點(diǎn)的值，需要交換
28. arr[i] = arr[k]; // 將k節(jié)點(diǎn)的值與i節(jié)點(diǎn)的值交換
29. i = k; // 注意：交換后，當(dāng)前值tmp的下標(biāo)是k，所以需要更新
30. }else{
31. // 如果tmp大于左右子節(jié)點(diǎn)，則它們的子樹也不用判斷，都是小于當(dāng)前值
32. break;
33. }
34. }
35. // i是交換后的下標(biāo)，更新為tmp
36. arr[i] = tmp;
37. }
38. // 交換值
39. function swap(arr, i, j){
40. const tmp = arr[i];
41. arr[i] = arr[j];
42. arr[j] = tmp;
43. }
44.}
計(jì)數(shù)排序
概要
計(jì)數(shù)排序的要點(diǎn)，是開辟一塊連續(xù)格子組成的空間，給數(shù)據(jù)進(jìn)行存儲(chǔ)。
將數(shù)組中的數(shù)字，依次讀取，存入其值對(duì)應(yīng)的下標(biāo)中。
儲(chǔ)存完成后，再按照空間的順序，依次讀取每個(gè)格子的數(shù)據(jù)，輸出即可。
所以，計(jì)數(shù)排序要求排序的數(shù)據(jù)，必須是有范圍的整數(shù)。
效果圖
解法
1. function countingSort(arr){
2. let maxValue = Number.MIN_VALUE;
3. let minValue = Number.MAX_VALUE;
4. let offset = 0; // 位移，用于處理負(fù)數(shù)
5. const result = [];
6. // 取出數(shù)組的最大值, 最小值
7. arr.forEach(num => {
8. maxValue = num > maxValue ? num : maxValue;
9. minValue = num > minValue ? minValue : num;
10. });
11. if(minValue < 0){
12. offset = -minValue;
13. }
14. const bucket = new Array(maxValue+offset+1).fill(0); // 初始化連續(xù)的格子
15. // 將數(shù)組中的每個(gè)數(shù)字，根據(jù)值放入對(duì)應(yīng)的下標(biāo)中，
16. // `bucket[num] == n`格子的意義：存在n個(gè)數(shù)字，值為num
17. arr.forEach(num => {
18. bucket[num+offset]++;
19. });
20. // 讀取格子中的數(shù)
21. bucket.forEach((store, index) => {
22. while(store--){
23. result.push(index - offset);
24. }
25. });
26. return result;
27.}
桶排序
概要
桶排序是計(jì)數(shù)排序的優(yōu)化版，原理都是一樣的：分治法+空間換時(shí)間。
將數(shù)組進(jìn)行分組，減少排序的數(shù)量，再對(duì)子數(shù)組進(jìn)行排序，最后合并即可得到結(jié)果。
效果圖
解法
對(duì)桶內(nèi)數(shù)字的排序，本文采用的是桶排序遞歸。其實(shí)它的本質(zhì)是退化到計(jì)數(shù)排序。
1. function bucketSort(arr, bucketSize = 10){
2. // bucketSize 每個(gè)桶可以存放的數(shù)字區(qū)間(0, 9]
3. if(arr.length <= 1){
4. return arr;
5. }
6. let maxValue = arr[0];
7. let minValue = arr[0];
8. let result = [];
9. // 取出數(shù)組的最大值, 最小值
10. arr.forEach(num => {
11. maxValue = num > maxValue ? num : maxValue;
12. minValue = num > minValue ? minValue : num;
13. });
14. // 初始化桶的數(shù)量
15. const bucketCount = Math.floor((maxValue - minValue)/bucketSize) + 1; // 桶的數(shù)量
16. // 初始化桶的容器
17. // 注意這里的js語(yǔ)法，不能直接fill([])，因?yàn)樯傻亩S下標(biāo)數(shù)組，是同一個(gè)地址
18. const buckets = new Array(bucketCount).fill(0).map(() => []);
19. // 將數(shù)字按照映射的規(guī)則，放入桶中
20. arr.forEach(num => {
21. const bucketIndex = Math.floor((num - minValue)/bucketSize);
22. buckets[bucketIndex].push(num);
23. });
24. // 遍歷每個(gè)桶內(nèi)存儲(chǔ)的數(shù)字
25. buckets.forEach(store => {
26. // 桶內(nèi)只有1個(gè)數(shù)字或者空桶，或者都是重復(fù)數(shù)字，則直接合并到結(jié)果中
27. if(store.length <= 1 || bucketSize == 1){
28. result = result.concat(store);
29. return;
30. }
31. // 遞歸，將桶內(nèi)的數(shù)字，再進(jìn)行一次劃分到不同的桶中
32. const subSize = Math.floor(bucketSize/2); // 減少桶內(nèi)的數(shù)字區(qū)間，但必須是最少為1
33. const tmp = bucketSort(store, subSize <= 1 ? 1: subSize);
34. result = result.concat(tmp);
35. });
36. return result;
}
基數(shù)排序
概述
基數(shù)排序，一般是從右到左，對(duì)進(jìn)制位上的數(shù)字進(jìn)行比較，存入[0, 9]的10個(gè)桶中，進(jìn)行排序。
從低位開始比較，逐位進(jìn)行比較，讓每個(gè)進(jìn)制位（個(gè)、十、百、千、萬(wàn)）上的數(shù)字，都能放入對(duì)應(yīng)的桶中，形成局部有序。
為什么10個(gè)桶？
因?yàn)槭M(jìn)制數(shù)，是由0-9數(shù)字組成，對(duì)應(yīng)的進(jìn)制位上的數(shù)字，都會(huì)落在這個(gè)區(qū)間內(nèi)，所以是10個(gè)桶。
基數(shù)排序有兩種方式：
MSD 從高位開始進(jìn)行排序
LSD 從低位開始進(jìn)行排序
效果圖
解法
當(dāng)前解法，只適用正整數(shù)的場(chǎng)景。
負(fù)數(shù)場(chǎng)景，需要加上偏移量解決。可參考 計(jì)數(shù)排序 的解法。
1. function radixSort(arr){
2. let maxNum = arr[0];
3. // 求出最大的數(shù)字，用于確定最大進(jìn)制位
4. arr.forEach(num => {
5. if(num > maxNum){
6. maxNum = num;
7. }
8. });
9. // 獲取最大數(shù)字有幾位
10. let maxDigitNum = 0;
11. while(maxNum > 0){
12. maxNum = Math.floor(maxNum / 10);
13. maxDigitNum++;
14. }
15. // 對(duì)每個(gè)進(jìn)制位上的數(shù)進(jìn)行排序
16. for(let i = 0; i < maxDigitNum; i++){
17. let buckets = new Array(10).fill(0).map(() => []); // 初始化10個(gè)桶
18. for(let k = 0; k < arr.length; k++){
19. const bucketIndex = getDigitNum(arr[k], i); // 獲取當(dāng)前進(jìn)制位上的數(shù)字
20. buckets[bucketIndex].push(arr[k]); // 排序的數(shù)字放入對(duì)應(yīng)桶中
21. }
22. // 所有數(shù)字放入桶中后，現(xiàn)從0-9的順序?qū)⑼爸械臄?shù)字取出
23. const res = [];
24. buckets.forEach(store => {
25. store.forEach(num => {
26. res.push(num); // 注意這里，先存入桶中的數(shù)字，先取出，這樣才能保持局部有序
27. })
28. });
29. arr = res;
30. }
31. return arr;
32. /**
33. 求出數(shù)字每個(gè)進(jìn)制位上的數(shù)字，只支持正整數(shù)
34. @param num 整數(shù)
35. @param digit 位數(shù)，從0開始
36. */
37. function getDigitNum(num, digit){
38. return Math.floor(num / Math.pow(10, digit) % 10)
39. }
40.}
算法復(fù)雜度
該文章在 2023/6/29 18:29:14 編輯過(guò)
400 186 1886
