用于對 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)，它將鏈表的頭作為輸入。

STEP2 – 初始化一個大小為 3 的計數數組 count[]，所有元素均為 0。

STEP 3 – 遍歷鏈表并遞增計數數組中相應索引處的節點數據的計數。

STEP 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();

登錄后復制