目錄
什麼是排序?
什麼是鍊錶?
問題陳述
範例
對 0、1 和 2 的鍊錶進行排序的演算法
結論
首頁 web前端 js教程 用於對 0、1 和 2 的連結清單進行排序的 JavaScript 程序

用於對 0、1 和 2 的連結清單進行排序的 JavaScript 程序

Sep 08, 2023 pm 09:05 PM

用于对 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();
登入後複製

結論

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

以上是用於對 0、1 和 2 的連結清單進行排序的 JavaScript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章標籤

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

在JavaScript中替換字符串字符 在JavaScript中替換字符串字符 Mar 11, 2025 am 12:07 AM

在JavaScript中替換字符串字符

jQuery檢查日期是否有效 jQuery檢查日期是否有效 Mar 01, 2025 am 08:51 AM

jQuery檢查日期是否有效

jQuery獲取元素填充/保證金 jQuery獲取元素填充/保證金 Mar 01, 2025 am 08:53 AM

jQuery獲取元素填充/保證金

10個jQuery手風琴選項卡 10個jQuery手風琴選項卡 Mar 01, 2025 am 01:34 AM

10個jQuery手風琴選項卡

10值得檢查jQuery插件 10值得檢查jQuery插件 Mar 01, 2025 am 01:29 AM

10值得檢查jQuery插件

HTTP與節點和HTTP-Console調試 HTTP與節點和HTTP-Console調試 Mar 01, 2025 am 01:37 AM

HTTP與節點和HTTP-Console調試

jQuery添加捲軸到Div jQuery添加捲軸到Div Mar 01, 2025 am 01:30 AM

jQuery添加捲軸到Div

自定義Google搜索API設置教程 自定義Google搜索API設置教程 Mar 04, 2025 am 01:06 AM

自定義Google搜索API設置教程

See all articles