用於排序包含 0、1 和 2 的連結串列的 JavaScript 程式

---

在本教程中，我們將學習用於排序包含 0、1 和 2 的連結串列的 JavaScript 程式。排序演算法對於任何程式語言都是必不可少的，JavaScript 也不例外。排序包含 0、1 和 2 的連結串列是一個常見問題，開發人員在編碼面試和實際應用中都會遇到。

因此，讓我們深入研究如何使用 JavaScript 程式設計對包含 0、1 和 2 的連結串列進行排序。

什麼是排序？

排序是按特定順序（升序或降序）排列元素的過程。它是計算機科學中的一項基本操作，在現實場景中有很多應用。排序演算法用於組織資料以進行高效搜尋，減少冗餘，並最佳化空間和時間複雜度。

以下是一些 JavaScript 中排序的示例

示例 1 − 按升序排序數字陣列

Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]

示例 2 − 按字母順序排序字串陣列

Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']

什麼是連結串列？

連結串列是一種線性資料結構，由透過指標連結在一起的節點組成。每個節點包含一個數據元素和對列表中下一個節點的引用。連結串列通常用於動態資料結構，其中資料的規模會頻繁變化。

問題陳述

目標是排列和顯示一個包含 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 

排序包含 0、1 和 2 的連結串列的演算法

使用計數排序演算法對包含 0、1 和 2 的連結串列進行排序的步驟：

步驟 1 − 定義一個函式 sortList(head)，它以連結串列的頭節點作為輸入。

步驟 2 − 初始化一個大小為 3 的計數陣列 count[]，所有元素都為 0。

步驟 3 − 遍歷連結串列，並將節點資料在計數陣列中相應索引的計數遞增。

步驟 4 − 再次遍歷連結串列，並用計數大於 0 的最低索引值替換節點資料。

步驟 5 − 對於每次替換，遞減節點資料的計數。

步驟 6 − 列印排序前和排序後的連結串列。

現在讓我們嘗試透過一個示例來理解上述演算法，在這個示例中，我們將使用 JavaScript 實現此演算法。

示例

下面的 JavaScript 程式使用計數排序演算法對包含 0、1 和 2 的連結串列進行排序。該演算法首先計算列表中 0、1 和 2 的頻率，然後根據每個值的計數更新列表中節點的值。

/* 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();

結論

總的來說，上述 Javascript 程式演示了一種使用計數技術對僅包含 0、1 和 2 的連結串列進行排序的有效方法。該演算法的時間複雜度為 O(n)，空間複雜度為 O(1)，使其成為此特定排序問題的最佳解決方案。