十大排序总结（js实现、稳定性、内外部排序区别、时间空间复杂度、冒泡、快速、直接选择、堆、直接插入、希尔、桶、基数、归并、计数排序）
目錄
排序相關概念
穩定性
?內部排序
外部排序
?十種排序算法特點總結
交換排序
冒泡排序（數組sort方法的原理）
圖解
?js實現
特點
快速排序
圖解
js實現
特點
選擇排序
直接選擇排序
圖解
?js實現
特點
堆排序
大（小）頂堆
非葉節點
js實現?
特點
插入排序?
直接插入排序
圖解
js實現?
特點
希爾排序
圖解
js實現
特點
其它排序
桶排序
圖解
js實現
特點
基數排序
圖解
js實現
特點
歸并排序
圖解
?js實現
特點
計數排序
圖解
?js實現
特點
排序相關概念
穩定性
不改變相同數值的順序為穩定。例如在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的(記錄的相對次序保持不變)；否則稱為不穩定的。
?內部排序
指待排序列完全存放在內存中所進行的排序過程，適合不太大的元素序列。有冒泡、選擇、插入、希爾、快速、堆排序（通常快速排序為最好的）。
外部排序
外部排序指的是大文件的排序，即待排序的記錄存儲在外存儲器上，待排序的文件無法一次裝入內存，需要在內存和外部存儲器之間進行多次數據交換，以達到排序整個文件的目的。有歸并、計數、桶、基數排序。
?十種排序算法特點總結
交換排序
冒泡排序（數組sort方法的原理）
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。
3.針對所有的元素重復以上的步驟，除了最后一個。
4.持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
圖解
?js實現
function swap(arr, x, y) {let tmp = arr[x]arr[x] = arr[y]arr[y] = tmp
}
function bubbleSort(arr) {let len = arr.length;for (let i = 0; i < len - 1; i++) {//比較出一輪中的最大值放入最后for (let j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1)}}}return arr;
}
特點
快速排序
1.以數組第一位為基準值，將小于的元素放在左邊，大于的元素放在右邊，分為左右兩塊。
2.在左右2塊中重復第一步，不斷循環，直到分區的大小為1則停止。
圖解
注意左右分區，我們可以通過將基準元素和左邊分區最右端元素交換實現
js實現
function swap(arr, x, y) {let tmp = arr[x]arr[x] = arr[y]arr[y] = tmp
}
//用于一次以基準值進行排序
function partition(arr, left, right) {//設定基準值pivotlet pivot = leftlet index = pivot + 1for (let i = index; i <= right; i++) {//小于基準值的放左邊，大于的不變if (arr[i] < arr[pivot]) {swap(arr, i, index)index++}}//和小于基準值的最右邊一個交換位置，實現左邊小于基準值，右邊大于基準值swap(arr, pivot, index - 1)//返回基準值的位置return index - 1
}
function quickSort(arr, left, right) {let len = arr.lengthleft = typeof left != 'number' ? 0 : leftright = typeof right != 'number' ? len - 1 : rightif (left < right) {//進行一次排序let partitionIndex = partition(arr, left, right)//遞歸對左邊進行排序quickSort(arr, left, partitionIndex - 1)//遞歸對右邊進行排序quickSort(arr, partitionIndex + 1, right)}return arr
}
console.log(quickSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))
特點
選擇排序
直接選擇排序
每一次遍歷待排序的數據元素從中選出最小（或最大）的一個元素，存放在序列的起始（或者末尾）位置（和原存放位置上的元素交換順序），直到全部待排序的數據元素排完。
圖解
?js實現
//交換數組下標x位和y位的元素
function swap(arr, x, y) {arr[x] = arr[x] - arr[y]arr[y] = arr[y] + arr[x]arr[x] = arr[y] - arr[x]return arr
}
function selectionSort(arr) {let t = arr.lengthlet x = 0while (x != t) {let min = 0;let tmp = Number.MAX_VALUE//選出最小的元素的下標for (let i = x; i < t; i++) {if (tmp > arr[i]) {tmp = arr[i]min = i}}//不是當前位置，則交換順序if (x != min) {swap(arr, x, min)}x++}return arr
}
console.log(selectionSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))
特點
堆排序
1.將元素排序為一個大（小）頂堆，則頂部元素為最大（小）元素，將其與元素尾（頭）部元素交換順序。
2.重新排序剩下元素，再次形成大（小）頂堆，重復1操作，直到只剩一個元素。
大（小）頂堆
每個節點的值都大于（小于）或等于其子節點的值，在堆排序算法中用于升（降）序排列；
代碼中表示為：
大頂堆arr[i]>=arr[2i+1]和arr[i]>=arr[2i+2]????????父節點大于左右子節點
小頂堆arr[i]<=arr[2i+1]和arr[i]<=arr[2i+2]?????????父節點小于左右子節點
非葉節點
有孩子節點的節點。最后一個非葉節點在數組中的序號為元素個數除以2向下取整。
js實現?
// 建立大頂堆
function buildMaxHeap(arr) {let len = arr.length;//Math.floor(len/2)表示最后一個非葉節點（含有子節點的節點），//從后往前調整每一個非葉子節點的順序，使堆變為大頂堆for (let i = Math.floor(len / 2); i >= 0; i--) {heapify(arr, i, len);}
}
// 調整堆
function heapify(arr, i, len) {let left = 2 * i + 1,right = 2 * i + 2,largest = i;//通過2次判斷選出父節點和2個子節點中最大的一個if (left < len && arr[left] > arr[largest]) {largest = left;}if (right < len && arr[right] > arr[largest]) {largest = right;}//將最大的節點和父節點交換順序if (largest != i) {swap(arr, i, largest);//遞歸對換順序的節點進行調整，使其還是大頂堆heapify(arr, largest, len);}
}
function swap(arr, i, j) {var temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
function heapSort(arr) {// 建立大頂堆buildMaxHeap(arr);let len = arr.length//每次建立一個大頂堆，將最大的元素（堆頂元素）放入尾部達到排序效果for (let i = len - 1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0, len);}return arr;
}
console.log(heapSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))
特點
插入排序?
直接插入排序
每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序（默認是從后向前比較）。
圖解
藍色部分為無序表，黃色部分為有序表：
js實現?
使用的是一個數組，將數組下標為i之前的為有序，之后為無序。
?注意用的是改變原數組的方法，可以不用返回。
//將數組下標為的x元素取出插入為y的 function popInsert(arr,x,y){arr.splice(y,0,...arr.splice(x,1)) } function insertSort(arr){let t=arr.lengthfor (let i=1;i<t;i++){let j=i-1do{if(arr[j]<arr[i]){popInsert(arr,i,j+1)break}j--//比較到下標為0的時候直接插入if(j<0){popInsert(arr,i,0)}}while(j>=0)}return arr } console.log(insertSort([3,1,2,3134,113,342,123412,55,111,4,234,5,5]))
特點
希爾排序
希爾排序在直接排序之前，進行預排列，將某些極端數據更快的排列到數列前面，構成一個接近排列好的序列，最后再進行一次直接插入排序。
預排列的原理也是插入排列，只不過這里的將數組分成了gap組，分別對每一個小組進行插入排序。
圖解
對于升序，當gap從5 – 2 – 1的過程中，排在后面的數值小的數能更快排到前面，當gap為1的時候實際上就是進行了一次插入排序
js實現
每次將下標位置差為gap的數進行直接排序，其中第一次gap=Math.floor(arr.length/2)，之后每次gap=Math.floor(gap/2)。
function shellsSort(arr){let t=arr.lengthlet gap=tlet tmp//gap取不同值的排序do{//每次的分組gap=Math.floor(gap/2)for(let i=gap;i<t;i++){//只和上一個間距為gap的元素進行比較，判斷是否要插入，還是維持原順序if(arr[i-gap]>arr[i]){tmp = arr[i]let j=i-gap//將插入位置之后的元素整體后移do{arr[j+gap]=arr[j]j-=gap}while(j>=0&&arr[j]>tmp)//插入對應位置arr[j+gap]=tmp}}}while(gap>1)return arr } console.log(shellsSort([3,1,2,3134,113,342,123412,55,111,4,234,5,5]))
特點
其它排序
桶排序
選出待排序元素中的最大最小值，根據最大最小值劃分多個區域（桶），通過映射函數將元素分到不同區域（桶）中，對區域（桶）中的元素進行排序后，依次取出即可。
圖解
將排序的元素放入對應的桶中
?對桶中的元素進行排序
js實現
//插入排序
function insertionSort(arr) {let len = arr.length;let preIndex, current;for (let i = 1; i < len; i++) {preIndex = i - 1;current = arr[i];while (preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex];preIndex--;}arr[preIndex + 1] = current;}return arr;
}
function bucketSort(arr, bucketSize) {let minValue = arr[0];let maxValue = arr[0];//找到數組中的最大和最小值for (let i = 1; i < arr.length; i++) {if (arr[i] < minValue) {minValue = arr[i];} else if (arr[i] > maxValue) {maxValue = arr[i];}}//桶的初始化let DEFAULT_BUCKET_SIZE = 5;// 設置一個桶能存儲的默認數量為5bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;//桶的個數let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;let buckets = new Array(bucketCount);for (let i = 0; i < buckets.length; i++) {buckets[i] = [];}//利用映射函數將元素分配到各個桶中for (let i = 0; i < arr.length; i++) {buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);}//刪除arr數組中的所有元素arr.length = 0;for (let i = 0; i < buckets.length; i++) {// 對每個桶進行排序，這里使用了插入排序insertionSort(buckets[i]);// 將每個桶的數據從小到大拿出 for (let j = 0; j < buckets[i].length; j++) {arr.push(buckets[i][j]);}}return arr;
}
console.log(bucketSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))
特點
基數排序
確定最大數的位數，先按第一位進行排序，在按第二位進行排序，直到按最后一位進行排序為止。
圖解
js實現
function radixSort(arr) {let counter = [];//獲取元素的最大位數let maxDigit = `${Math.max(...arr)}`.lengthlet mod = 10;let dev = 1;//從小到大依次對元素的每一位進行循環排序for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {for (let j = 0; j < arr.length; j++) {//獲取元素對應位上的數值let bucket = parseInt((arr[j] % mod) / dev);if (counter[bucket] == null) {counter[bucket] = [];}//根據對應的數值，將元素放入對應的桶中counter[bucket].push(arr[j]);}let pos = 0;//從0~9的桶中將元素取出，完成一次排序for (let j = 0; j < counter.length; j++) {let value = null;if (counter[j] != null) {while ((value = counter[j].shift()) != null) {arr[pos++] = value;}}}}return arr;
}
console.log(radixSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5], 6))
特點
歸并排序
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
重復步驟 3 直到某一指針達到序列尾；
將另一序列剩下的所有元素直接復制到合并序列尾。
圖解
?js實現
function mergeSort(arr) { // 采用自上而下的遞歸方法let len = arr.length;if (len < 2) {return arr;}let middle = Math.floor(len / 2),left = arr.slice(0, middle),right = arr.slice(middle);return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {let result = [];while (left.length && right.length) {if (left[0] <= right[0]) {result.push(left.shift());} else {result.push(right.shift());}}while (left.length)result.push(left.shift());while (right.length)result.push(right.shift());return result;
}
console.log(mergeSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5], 6))
特點
計數排序
1.找出待排序的數組中最大和最小的元素
2.統計數組中每個值為i的元素出現的次數，存入數組C的第i項
3.對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
4.反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1
圖解
?js實現
function countingSort(arr) {let maxValue = Math.max(...arr)let bucket = new Array(maxValue + 1),sortedIndex = 0;arrLen = arr.length,bucketLen = maxValue + 1;for (let i = 0; i < arrLen; i++) {if (!bucket[arr[i]]) {bucket[arr[i]] = 0;}bucket[arr[i]]++;}for (let j = 0; j < bucketLen; j++) {while (bucket[j] > 0) {arr[sortedIndex++] = j;bucket[j]--;}}return arr;
}
console.log(countingSort([3, 1, 2, 3134, 113, 342, 123412, 55, 111, 4, 234, 5, 5]))
特點
---------------------
作者：YF-SOD
來源：CSDN
原文：https://blog.csdn.net/AIWWY/article/details/121346132
版權聲明：本文為作者原創文章，轉載請附上博文鏈接！
內容解析By：CSDN,CNBLOG博客文章一鍵轉載插件
總結
以上是生活随笔為你收集整理的十大排序总结（js实现、稳定性、内外部排序区别、时间空间复杂度、冒泡、快速、直接选择、堆、直接插入、希尔、桶、基数、归并、计数排序）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Win11 的日历 替代
- 下一篇： 达摩院年终预测出炉：2022 十大科技趋