資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 JavaScript 中實現計數排序
在給定的任務中，我們的目標是建立一個計數排序技術，並藉助 Javascript 功能來實現此問題。
什麼是計數排序？
計數排序是一種根據鍵對物件資料集進行排序的過程。它透過計算具有不同鍵值的專案的數量並查詢每個物件在排序輸出中的位置來工作。計數排序的思想是將專案直接放置到輸出陣列中的正確位置。
在演算法開始時，我們需要找到輸入陣列中的最大值和最小值。藉助這些值，我們需要建立一個與輸入陣列中值長度相等的計數陣列。計數陣列將儲存陣列中每個不同值的出現次數。
該演算法使用計數陣列的字首和。因此，該演算法以相反的順序遍歷輸入陣列，並根據其計數將每個專案放置到輸出陣列中的正確位置，並相應地遞減計數。
給定問題的邏輯
在給定的問題陳述中，我們必須使用上面提到的計數排序來完成對給定陣列的專案進行排序的任務。因此，我們首先將獲取一個輸入陣列，並將其作為新陣列返回，該陣列已排序且與輸入陣列的長度相同。
根據計數排序技術，我們需要找出輸入陣列中的最大值和最小值。然後，我們將迭代陣列元素並計算每個專案的出現次數。然後計算計數陣列的字首和。然後再次遍歷陣列並將每個專案放在其正確的位置。
演算法
步驟 1 - 檢查給定陣列是否有元素。
步驟 2 - 宣告計數和輸出陣列。計數陣列將用於計算每個值出現的次數。排序陣列將用於儲存輸出陣列。
步驟 3 - 使用 for 迴圈遍歷給定陣列，並計算其中每個值的重複次數。
步驟 4 - 根據計數排序演算法計算陣列的字首和。
步驟 5 - 以相反的順序遍歷給定陣列，將每個專案放在正確的位置。
步驟 6 - 最後，我們必須將輸出顯示為排序陣列。
演算法程式碼
function countingSort(arr) {
if (arr.length === 0) {
return arr;
}
// Define the range of values in the input array
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
// initialize the required arrays
const count = new Array(max - min + 1).fill(0);
const output = new Array(arr.length);
// count the number of occurrences
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// calculate the prefix sum of the count array
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// the output array in sorted order
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
const arr = [30, 10, 40, 10, 50, 90, 20, 60, 50, 30, 50];
console.log(countingSort(arr));
複雜度
計數排序函式的時間複雜度為 O(n+m)，其中 n 是輸入陣列的長度，m 是輸入陣列中值的範圍。如程式碼所示，我們迭代過一次陣列以計算每個值的重複次數。然後，我們迭代過一次計數陣列以計算字首和。因此，執行程式碼的總時間為 O(n+m)。空間複雜度也為 O(n+m)。因為我們建立了兩個陣列，一個是計數陣列，另一個是輸出陣列。
結論
我們看到的用於對陣列中的元素進行排序的程式碼利用了基本的 JavaScript 操作來完成任務。該演算法根據給定的問題陳述使用計數排序。
1K+ 瀏覽量
