在本教程中，我們將學(xué)習(xí)對 0、1 和 2 的鏈表進行排序的 JavaScript 程序。排序算法對于任何編程語言都是必不可少的，JavaScript 也不例外。對 0、1 和 2 的鏈表進行排序是開發(fā)人員在編碼面試和實際應(yīng)用中遇到的常見問題。
那么，讓我們深入探討如何使用 JavaScript 編程對 0、1 和 2 的鏈接列表進行排序。
什么是排序？
排序是按照特定順序（升序或降序）排列元素的過程。它是計算機科學(xué)中的基本操作，并且在現(xiàn)實場景中有大量應(yīng)用。排序算法用于組織數(shù)據(jù)以進行高效搜索、減少冗余并優(yōu)化空間和時間復(fù)雜度。
以下是 JavaScript 中排序的一些示例：
示例 1 – 按升序?qū)?shù)字?jǐn)?shù)組進行排序：
Input: ar[]= [5, 3, 8, 1, 2, 9] Output: [1, 2, 3, 5, 8, 9]
登錄后復(fù)制
示例 2 – 按字母順序?qū)ψ址當(dāng)?shù)組進行排序：
Input: ['apple', 'banana', 'orange', 'grape'] Output: ['apple', 'banana', 'grape', 'orange']
登錄后復(fù)制
什么是鏈表？
鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，由通過指針鏈接在一起的節(jié)點組成。每個節(jié)點都包含一個數(shù)據(jù)元素和對列表中下一個節(jié)點的引用。鏈表通常用于動態(tài)數(shù)據(jù)結(jié)構(gòu)，其中數(shù)據(jù)大小經(jīng)常變化。
問題陳述
目標(biāo)是按順序排列并顯示由 0、1 和 2 組成的鏈表。讓我們通過示例來理解它：
示例
Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL
登錄后復(fù)制
對 0、1 和 2 的鏈表進行排序的算法
使用計數(shù)排序算法對 0、1 和 2 的鏈表進行排序的步驟 –
第 1 步 – 定義一個函數(shù) sortList(head)，它將鏈表的頭作為輸入。
STEP2 – 初始化一個大小為 3 的計數(shù)數(shù)組 count[]，所有元素均為 0。
STEP 3 – 遍歷鏈表并遞增計數(shù)數(shù)組中相應(yīng)索引處的節(jié)點數(shù)據(jù)的計數(shù)。
STEP 4 – 再次遍歷鏈表，并用計數(shù)大于0的最低索引值替換節(jié)點數(shù)據(jù)。
第 5 步 – 減少每次替換的節(jié)點數(shù)據(jù)計數(shù)。
第 6 步 – 打印排序前后的鏈表。
現(xiàn)在讓我們嘗試通過一個使用 JavaScript 實現(xiàn)該算法的示例來理解上述算法。
示例
下面的 JavaScript 程序使用計數(shù)排序算法對包含 0、1 和 2 的鏈表進行排序。該算法首先統(tǒng)計列表中0、1、2的出現(xiàn)頻率，然后根據(jù)每個值的計數(shù)更新列表中節(jié)點的值。
/* Link list node */
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
push(new_data) {
const new_node = new Node(new_data);
new_node.next = this.head;
this.head = new_node;
}
printList() {
let currentNode = this.head;
let value = "";
while (currentNode !== null) {
value += currentNode.data + " -> ";
currentNode = currentNode.next;
}
console.log(value + "null");
}
sortList() {
const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
let ptr = this.head;
while (ptr !== null) {
count[ptr.data] += 1;
ptr = ptr.next;
}
ptr = this.head;
let i = 0;
while (ptr !== null) {
if (count[i] === 0) {
++i;
} else {
ptr.data = i;
--count[i];
ptr = ptr.next;
}
}
}
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();
登錄后復(fù)制
結(jié)論
總的來說，上面的 Javascript 程序演示了一種使用計數(shù)技術(shù)對僅包含 0、1 和 2 的鏈表進行排序的有效方法。該算法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)，使其成為該特定排序問題的最優(yōu)解決方案。
以上就是用于對 0、1 和 2 的鏈接列表進行排序的 JavaScript 程序的詳細(xì)內(nèi)容，更多請關(guān)注www.92cms.cn其它相關(guān)文章！
