這里給大家分享我在網上總結出來的一些知識，希望對大家有所幫助
了解排序演算法的優缺點和適用場景是非常重要的，因為在實際開發中，需要根據實際情況選擇最合適的排序演算法，不同的排序演算法適用于不同的場景，有的演算法適用于小規模的資料集，有的演算法適用于大規模的資料集，有的演算法適用于穩定排序，有的演算法適用于不穩定排序，有的演算法時間復雜度低，有的演算法空間復雜度低，等等，了解這些演算法的特點和適用場景可以幫助我們更好地選擇演算法，提高代碼效率和性能，此外，了解排序演算法還可以幫助我們更好地理解計算機科學的基本概念和理論，提高我們的編程能力和思維水平，
1. 冒泡排序
冒泡排序是一種簡單的排序演算法，它重復地遍歷要排序的串列，比較相鄰的兩個元素，如果它們的順序錯誤就交換它們，遍歷整個串列的作業會一遍又一遍地進行，直到串列沒有再需要交換的元素為止，
冒泡排序的代碼：
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) { // 外層回圈控制排序的趟數
for (var j = 0; j < len - 1 - i; j++) { // 內層回圈控制每趟排序的次數
if (arr[j] > arr[j+1]) { // 如果前一個元素比后一個元素大，就交換它們的位置
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]
冒泡排序的時間復雜度為O(n^2)，其中n是串列的長度，它的空間復雜度為O(1)，在實際應用中，冒泡排序的性能通常比其他排序演算法要差，因此很少被使用，
2. 快速排序
快速排序使用分治的思想來將一個大的問題分解成幾個小的問題，然后遞回地解決這些小問題，最終將它們組合起來得到答案，具體來說，快速排序使用一個元素作為“樞軸”，將串列分成兩個子串列，一個子串列所有元素都比樞軸小，另一個子串列所有元素都比樞軸大，然后遞回地對兩個子串列進行排序，
快速排序的代碼：
function quickSort(arr) {
// 如果陣列長度為1或0，則已經有序
if (arr.length <= 1) {
return arr
}
// 選擇一個基準元素
let mainIndex = parseInt(arr.length / 2);
let mainItem = arr.splice(mainIndex, 1)[0];
// 將陣列分為兩個子陣列，一個包含小于基準的元素，一個包含大于基準的元素
let left = [];
let right = [];
arr.forEach((item) => {
if (item > mainItem) {
right.push(item)
} else {
left.push(item)
}
})
// 遞回地對子陣列進行排序，并在基準元素中間將它們連接起來
return quickSort(left).concat([mainItem], quickSort(right))
}
// 測驗該函式
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr));
快速排序的時間復雜度為O(nlogn)，其中n是串列的長度，它的空間復雜度取決于具體實作，通常為O(logn)，
快速排序的優點是它的時間復雜度較低，通常為O(nlogn)，并且它可以原地排序，即不需要分配額外的空間，此外，快速排序的實作很簡單，易于理解和實作，
然而，快速排序也有一些缺點，對于小規模的資料集效果不佳，因為它的遞回深度較大，其次，快速排序是一種不穩定的排序演算法，這意味著在排序后相同的元素可能會被重新排序，最后，快速排序的性能可能會受到輸入資料的影響，如果資料已經有序或接近有序，快速排序的效率可能會明顯降低，
3. 插入排序
插入排序的基本思想是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增加1的有序表，具體來說，插入排序將串列分成兩部分：已排序和未排序，每次取出未排序部分的第一個元素，然后將它插入到已排序部分的正確位置，
插入排序的代碼：
function insertionSort(arr) {
var len = arr.length;
for (var i = 1; i < len; i++) {
var key = arr[i]; // 將要插入的元素存盤在變數key中
var j = i - 1; // 從已排序序列的最右邊開始比較
// 將所有比key大的元素向右移動一個位置
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = key; // 將key插入到正確的位置
}
return arr;
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr));
插入排序的時間復雜度為O(n^2)，其中n是串列的長度，它的空間復雜度為O(1)，
插入排序的優點是它的實作簡單，容易理解，此外，它在處理小規模的資料集時效果很好，插入排序是一種穩定的排序演算法，這意味著在排序后相同的元素不會被重新排序，
然而，插入排序也有一些缺點，在處理大規模的資料集時，插入排序的效率會明顯降低，此外，它是一種不適合外部排序的排序演算法，因為它需要頻繁地訪問串列中的元素，
4. 選擇排序
選擇排序的基本思想是每次從未排序的部分選出最小的元素，然后將它放到已排序部分的末尾，
選擇排序的代碼：
function selectionSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
var minIndex = i; // 先假設當前位置是最小值的索引
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 如果后面的元素比當前最小值還要小，更新最小值的索引
minIndex = j;
}
}
var temp = arr[minIndex]; // 將最小值與當前位置交換
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // [11, 12, 22, 25, 34, 64, 90]
對于一個長度為n的串列，選擇排序需要進行n-1趟排序，在第i趟排序中，程式會在未排序部分中找到最小的元素，并將它與第i個元素交換位置，最終，串列將按照從小到大的順序排列，
選擇排序的時間復雜度為O(n^2)，其中n是串列的長度，它的空間復雜度為O(1)，
選擇排序的優點是它的實作簡單，容易理解，此外，它是一種不需要額外的空間的排序演算法，因為它只需要一個額外的變數來存盤最小值的索引，選擇排序是一種穩定的排序演算法，這意味著在排序后相同的元素不會被重新排序，
然而，選擇排序也有一些缺點，它不適合外部排序的排序演算法，因為它需要頻繁地訪問串列中的元素，最后，選擇排序的性能可能會受到輸入資料的影響，如果資料已經有序或接近有序，選擇排序的效率可能會明顯降低，
5. 歸并排序
歸并排序是一種分治的排序演算法，它的基本思想是將一個大的問題分解成幾個小的問題，然后遞回地解決這些小問題，最終將它們組合起來得到答案，具體來說，歸并排序將串列分成兩個子串列，然后遞回地對這兩個子串列進行排序，并將它們合并成一個有序的串列，
歸并排序的代碼：
// 歸并排序
function mergeSort(arr) {
if (arr.length <= 1) { // 如果串列只有一個元素，已經有序，直接回傳
return arr;
}
var mid = Math.floor(arr.length / 2); // 找到串列的中間點
var left = arr.slice(0, mid); // 將串列分成左右兩部分
var right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right)); // 遞回地對左右兩部分進行排序，并將它們合并起來
}
function merge(left, right) {
var 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; // 回傳結果串列
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr));
歸并排序的時間復雜度為O(nlogn)，其中n是串列的長度，它的空間復雜度為O(n)，其中n是串列的長度，
歸并排序的優點是它的時間復雜度較低，通常為O(nlogn)，并且它可以處理大規模的資料集，此外，歸并排序是一種穩定的排序演算法，這意味著在排序后相同的元素不會被重新排序，最后，歸并排序可以用于外部排序，因為它可以將資料分成較小的塊，這些塊可以逐個讀取到記憶體中進行排序，
然而，歸并排序也有一些缺點，它需要額外的空間來存盤臨時串列和遞回呼叫堆疊，這對于記憶體受限的環境可能是一個問題，其次，歸并排序的實作比其他排序演算法復雜，因此它不如其他排序演算法易于理解和實作，歸并排序的常數因子較大，因此它的實際效率可能低于其他具有相同時間復雜度的排序演算法，
總之，歸并排序是一種高效、穩定的排序演算法，它適用于處理大規模的資料集，特別是記憶體受限的環境，但是，它的實作較為復雜，因此在實際應用中需要謹慎選擇，
6. 希爾排序
希爾排序是一種插入排序的變體，它的基本思想是設定一個增量序列，將串列分成若干個子串列，對每個子串列進行插入排序，每次縮小增量序列，直到增量為1，最后對整個串列進行插入排序，
通過將串列分成若干子串列來提高插入排序的性能，每個子串列使用插入排序進行排序，這些子串列的長度從原始串列長度的一半開始，每次迭代都將子串列長度除以2，直到長度為1，
希爾排序的代碼：
function shellSort(arr) {
var len = arr.length;
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = gap; i < len; i++) {
var j = i;
var temp = arr[i];
// 將當前元素與之前的元素進行比較，如果需要交換就交換它們的位置
while (j >= gap && arr[j-gap] > temp) {
arr[j] = arr[j-gap];
j = j - gap;
}
arr[j] = temp; // 將當前元素插入到正確的位置
}
}
return arr;
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(shellSort(arr)); // [11, 12, 22, 25, 34, 64, 90]
希爾排序的時間復雜度為O(n^2)，而它的空間復雜度為O(1)，雖然它比快速排序和歸并排序慢，但它的代碼實作比較簡單，也比較容易理解，
希爾排序的優點是它比插入排序更快，尤其是對于較大的資料集，它的時間復雜度為O(nlogn)，比選擇排序和插入排序都要快，此外，希爾排序是一種不穩定的排序演算法，這意味著在排序后相同的元素可能會被重新排序，
然而，希爾排序也有一些缺點，它的實作比插入排序更復雜，需要計算增量序列并對多個子串列進行排序，希爾排序的時間復雜度比快速排序和歸并排序高，因此它可能不適用于處理較大的資料集，最后，希爾排序的實作依賴于增量序列的選擇，不同的增量序列可能會導致不同的性能表現，
7. 堆排序
堆排序是一種選擇排序的變體，它的基本思想是將串列構建成一個堆，然后依次取出堆頂元素，并將剩余元素重新構建成一個堆，具體來說，堆排序首先將串列構建成一個大根堆或小根堆（本例使用大根堆），然后依次將堆頂元素與最后一個元素交換，然后重新構建堆，
堆排序的代碼：
function heapSort(arr) {
var len = arr.length;
for (var i = Math.floor(len/2)-1; i >= 0; i--) {
heapify(arr, len, i); // 將陣列構建成大頂堆
}
for (var j = len-1; j > 0; j--) {
var temp = arr[0];
arr[0] = arr[j]; // 將當前最大值放到陣列的末尾
arr[j] = temp;
heapify(arr, j, 0); // 重新將剩余的元素構建成大頂堆
}
return arr;
}
function heapify(arr, len, index) {
var left = 2 * index + 1;
var right = 2 * index + 2;
var largest = index;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != index) {
var temp = arr[index];
arr[index] = arr[largest];
arr[largest] = temp;
heapify(arr, len, largest); // 遞回地將子樹構建成大頂堆
}
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(heapSort(arr)); // [11, 12, 22, 25, 34, 64, 90]
堆排序的時間復雜度為O(nlogn)，它的空間復雜度為O(1)，
堆排序的優點是它的時間復雜度較低，對于大規模資料集的排序效率較高，此外，堆排序是一種穩定的排序演算法，即排序后相同的元素不會被重新排序，另外，堆排序可以用于外部排序，因為它可以將資料分成較小的塊，這些塊可以逐個讀取到記憶體中進行排序，
堆排序的缺點是它需要額外的空間來存盤堆，這對于記憶體受限的環境可能是一個問題，其次，堆排序的實作比其他排序演算法復雜，因此它不如其他排序演算法易于理解和實作，最后，堆排序的常數因子較大，因此它的實際效率可能低于其他具有相同時間復雜度的排序演算法，
8. 計數排序
計數排序是一種非比較排序演算法，它的基本思想是統計每個元素出現的次數，然后依次輸出元素，具體來說，計數排序首先找出串列中的最大值和最小值，然后創建一個計數陣列，統計每個元素出現的次數，再依次輸出元素，
計數排序的代碼：
function countingSort(arr) {
var len = arr.length;
var max = Math.max.apply(null, arr); // 找到最大值
var min = Math.min.apply(null, arr); // 找到最小值
var count = new Array(max - min + 1).fill(0); // 創建一個計數陣列，初始值為0
var output = new Array(len); // 創建一個與原陣列長度相同的輸出陣列
for (var i = 0; i < len; i++) {
count[arr[i] - min]++; // 計數陣列中對應元素的計數加1
}
for (var j = 1; j < count.length; j++) {
count[j] += count[j-1]; // 將計數陣列進行累加，得到每個元素的最終位置
}
for (var k = len-1; k >= 0; k--) {
output[count[arr[k]-min]-1] = arr[k]; // 將當前元素放到對應位置，并將計數陣列中對應元素的計數減1
count[arr[k]-min]--;
}
for (var m = 0; m < len; m++) {
arr[m] = output[m]; // 將輸出陣列復制回原陣列
}
return arr;
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(countingSort(arr));
計數排序需要額外的空間來存盤計數陣列，因此它的空間復雜度為O(k)，其中k是計數陣列的大小，計數排序的時間復雜度為O(n+k)，其中n是串列的長度，
計數排序的優點是它的時間復雜度較低，對于小范圍的資料集排序效率較高，此外，計數排序是一種穩定的排序演算法，即排序后相同的元素不會被重新排序，
然而，計數排序也有一些缺點，它只能用于非負整數排序，并且需要額外的空間來存盤計數陣列，因此它的空間復雜度較高，計數排序的實作比其他排序演算法復雜，因此不如其他排序演算法易于理解和實作，最后，計數排序的常數因子較大，因此它的實際效率可能低于其他具有相同時間復雜度的排序演算法，
總之，計數排序是一種效率較高、穩定的排序演算法，特別適用于小范圍的資料集，但是，它的實作較為復雜，因此在實際應用中需要謹慎選擇，
9. 桶排序
桶排序是一種非比較排序演算法，它的基本思想是將要排序的資料分到幾個有序的桶里，每個桶里的資料再單獨進行排序，具體來說，桶排序首先將串列分到有限數量的桶里，然后對每個桶里的資料進行排序，最后將每個桶里的資料按順序連接起來，
桶排序的代碼：
function bucketSort(arr, bucketSize) {
if (arr.length === 0) { // 如果陣列為空，直接回傳
return arr;
}
var i;
var minValue = https://www.cnblogs.com/smileZAZ/archive/2023/04/08/arr[0]; // 找到陣列中的最小值和最大值
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
var DEFAULT_BUCKET_SIZE = 5; // 設定默認的桶大小為5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; // 如果未指定桶大小，使用默認大小
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; // 計算需要的桶的數量
var buckets = new Array(bucketCount); // 創建桶陣列
for (i = 0; i < buckets.length; i++) { // 初始化桶陣列
buckets[i] = [];
}
for (i = 0; i < arr.length; i++) { // 將元素分配到桶中
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0; // 將原陣列清空
for (i = 0; i < buckets.length; i++) { // 對每個桶進行插入排序，并將它們合并到原陣列中
insertionSort(buckets[i]);
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr; // 回傳排序后的陣列
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bucketSort(arr)); // [11, 12, 22, 25, 34, 64, 90]
桶排序的時間復雜度為O(n+k)，其中n是串列的長度，k是桶的數量，桶排序的空間復雜度取決于桶的數量，通常為O(n)或O(k)，如果k較大，桶排序的空間復雜度將較高，如果k較小，桶排序的時間復雜度將較高，
桶排序是一種穩定的排序演算法，即排序后相同的元素不會被重新排序，另外，桶排序可以用于外部排序，因為它可以將資料分成較小的塊，這些塊可以逐個讀取到記憶體中進行排序，
然而，桶排序也有一些缺點，它需要額外的空間來存盤桶，因此它的空間復雜度較高，其次，桶排序的實作比其他排序演算法復雜，因此不如其他排序演算法易于理解和實作，最后，桶排序的常數因子較大，因此它的實際效率可能低于其他具有相同時間復雜度的排序演算法，另外，如果資料分布不均勻，桶的數量將不均勻，這可能會導致桶排序的性能下降，
總之，桶排序是一種效率較高、穩定的排序演算法，特別適用于小范圍的資料集，但是，它的實作較為復雜，因此在實際應用中需要謹慎選擇，
10. 基數排序
基數排序是一種非比較排序演算法，它的基本思想是將整個串列按照位數切割成不同的數字，然后按每個位數分別比較，具體來說，基數排序首先將所有的元素統一為同樣的位數，然后從最低位開始依次進行排序，直到最高位排序完畢，在每個位上，使用穩定排序演算法（如計數排序）對元素進行排序，
基數排序的代碼：
function radixSort(arr) {
var maxDigit = getMaxDigit(arr);
for (var i = 0; i < maxDigit; i++) {
arr = bucketSort(arr, i);
}
return arr;
}
// 獲取陣列中最大數字的位數
function getMaxDigit(arr) {
var maxDigit = 1;
for (var i = 0; i < arr.length; i++) {
var num = arr[i];
var digit = 1;
while (Math.floor(num/10) !== 0) {
digit++;
num = Math.floor(num/10);
}
if (digit > maxDigit) {
maxDigit = digit;
}
}
return maxDigit;
}
// 根據數字的某一位進行桶排序
function bucketSort(arr, digit) {
var buckets = new Array(10); // 創建10個桶
for (var i = 0; i < buckets.length; i++) {
buckets[i] = []; // 初始化每個桶
}
for (var j = 0; j < arr.length; j++) {
var num = arr[j];
var radix = getRadix(num, digit); // 獲取數字的某一位
buckets[radix].push(num); // 將數字放入對應的桶中
}
var result = [];
for (var k = 0; k < buckets.length; k++) { // 將所有桶中的數字按順序放入結果陣列中
result = result.concat(buckets[k]);
}
return result;
}
// 獲取數字的某一位
function getRadix(num, digit) {
return Math.floor(num / Math.pow(10, digit)) % 10;
}
var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(radixSort(arr));
基數排序的時間復雜度為O(kn)，其中k是最大數字的位數，n是串列的長度，它的空間復雜度為O(k+n)，基數排序的時間復雜度較低，但它需要額外的空間來存盤桶和排序結果，因此在空間有限的情況下可能不適用，
寫在后面
這些排序演算法各有優缺點，應根據待排序資料的規模、排序的穩定性、時間復雜度和空間復雜度等多種因素進行選擇，對于小規模的資料集，可以考慮使用冒泡排序、選擇排序、插入排序或希爾排序等簡單的排序演算法；對于大規模的資料集，可以考慮使用歸并排序、快速排序或堆排序等高效的排序演算法，而計數排序、桶排序和基數排序適用于特定的排序場景，應根據具體情況選擇，
需要注意的是，排序演算法的實作可能會影響排序的效率和穩定性，因此，在選擇排序演算法時，應綜合考慮多種因素，并根據具體情況進行選擇，
本文轉載于:
https://juejin.cn/post/7216936647505756215
如果對您有所幫助，歡迎您點個關注，我會定時更新技術檔案，大家一起討論學習，一起進步，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/549540.html
標籤：其他
上一篇：精靈圖