這裡給大家分享我在網上總結出來的一些知識,希望對大家有所幫助 瞭解排序演算法的優缺點和適用場景是非常重要的,因為在實際開發中,需要根據實際情況選擇最合適的排序演算法。不同的排序演算法適用於不同的場景,有的演算法適用於小規模的數據集,有的演算法適用於大規模的數據集,有的演算法適用於穩定排序,有的演算法適用於不穩定排 ...
這裡給大家分享我在網上總結出來的一些知識,希望對大家有所幫助
瞭解排序演算法的優缺點和適用場景是非常重要的,因為在實際開發中,需要根據實際情況選擇最合適的排序演算法。不同的排序演算法適用於不同的場景,有的演算法適用於小規模的數據集,有的演算法適用於大規模的數據集,有的演算法適用於穩定排序,有的演算法適用於不穩定排序,有的演算法時間複雜度低,有的演算法空間複雜度低,等等。瞭解這些演算法的特點和適用場景可以幫助我們更好地選擇演算法,提高代碼效率和性能。此外,瞭解排序演算法還可以幫助我們更好地理解電腦科學的基本概念和理論,提高我們的編程能力和思維水平。
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 = 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)。基數排序的時間複雜度較低,但它需要額外的空間來存儲桶和排序結果,因此在空間有限的情況下可能不適用。
寫在後面
這些排序演算法各有優缺點,應根據待排序數據的規模、排序的穩定性、時間複雜度和空間複雜度等多種因素進行選擇。對於小規模的數據集,可以考慮使用冒泡排序、選擇排序、插入排序或希爾排序等簡單的排序演算法;對於大規模的數據集,可以考慮使用歸併排序、快速排序或堆排序等高效的排序演算法。而計數排序、桶排序和基數排序適用於特定的排序場景,應根據具體情況選擇。
需要註意的是,排序演算法的實現可能會影響排序的效率和穩定性。因此,在選擇排序演算法時,應綜合考慮多種因素,並根據具體情況進行選擇。