javascript資料結構之雙鍊錶插入排序實例詳解_javascript技巧-js教程-PHP中文網

首頁

web前端

js教程

javascript資料結構之雙鍊錶插入排序實例詳解_javascript技巧

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

May 16, 2016 pm 03:29 PM

javascript插入排序

本文實例講述了javascript資料結構之雙鍊錶插入排序實作方法。分享給大家參考，具體如下：

陣列儲存前提下，插入排序演算法，在最壞情況下，前面的元素需要不斷向後移，以便在插入點留出空位，讓目標元素插入。

換成鍊錶時，顯然無需做這種大量移動，根據每個節點的前驅節點“指針”，向前找到插入點後，直接把目標值從原鍊錶上摘下，然後在插入點把鍊錶斷成二截，然後跟目標點重新接上即可。

<!doctype html>
<html>
<head>
  <title>双链表-插入排序</title>
  <meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<script type="text/javascript">
  //节点类
  var Node = function (pData) {
    this.next = null; //后继“指针”
    this.prev = null; //前驱"指针"
    this.data = pData;
  }
  //单链表(约定：头节点不放内容，当哨兵位，有效元素从头节点后的第1个元素开始)
  var DbLinkList = function () {
    this.head = new Node(null); //头节点   
    //插入新元素
    this.insert = function (pNodeValue) {
      var newNode = new Node(pNodeValue);
      //如果只有头节点
      if (this.head.next == null) {
        this.head.next = newNode;
        newNode.prev = this.head;
        return;
      }
      //否则遍历找到尾节点
      var p = this.head;
      while (p.next != null) {
        p = p.next;
      }
      p.next = newNode;
      newNode.prev = p;
    }
    //获取第n个元素的数据值
    this.getData = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      while (p.next != null && i <= index) {
        p = p.next;
        i += 1;
      }
      return p.data;
    }
    //取尾节点
    this.getTail = function () {
      if (this.head.next == null) {
        return null;
      }
      var p = this.head.next;
      while (p.next != null) {
        p = p.next;
      }
      return p;
    }
    //删除指定位置的元素
    this.removeAt = function (index) {
      if (index < 1 || index > this.size) {
        return null;
      }
      var p = this.head;
      var i = 1;
      //从头开始遍历，找到index位置的前一个元素
      while (p.next != null && i < index) {
        p = p.next;
        i += 1;
      }
      p.next = p.next.next; //修改index位置前一个元素的后继指针
      p.next.prev = p;
      return p.data; //返回删除元素的值    
    }
    //打印所有元素
    this.print = function () {
      document.write("<br/>");
      if (this.head.next == null) {
        return;
      }
      var p = this.head.next;
      while (p.next != null) {
        document.write(p.data + " ");
        p = p.next;
      }
      document.write(p.data + " "); //最后一个元素，需要单独打印
      document.write("<br/>");
    }
    //从后打印所有元素
    this.printFromBack = function () {
      document.write("该链表共有" + this.size + "个元素，从后向前分别为:<br/>");
      var tail = this.getTail();
      var p = tail;
      if (p == null) {
        return;
      }
      while (p.prev != null) {
        document.write(p.data + " ");
        p = p.prev;
      }
      document.write("<br/>");
    }
    //插入排序
    this.insertSort = function () {
      if (this.head.next == null || this.head.next.next == null) {
        return;
      }
      var p = this.head.next;
      while (true) {
        if (p == null) {
          return;
        }
        var t = p.prev;
        //向前查找p之前的插入点
        while (t.prev != null && t.data > p.data) {
          t = t.prev;
        }
        //如果插入点就是p的前驱节点，不用调整，
        //忽略，直接进入下一轮
        if (t.next == p) {
          p = p.next;
          continue;
        }
        //将p的后续节点先保护起来，以便下一轮循环时确定起始位置
        var x = p.next;
        //将p从链表上摘下
        if (p.next != null) {
          p.next.prev = p.prev;
        }
        p.prev.next = p.next;
        //p插入到t之后
        t.next.prev = p;
        p.next = t.next;
        t.next = p;
        p.prev = t;
        this.print(); //打印输出，调试用  
        //重新将p定位到下一轮循环的"正确"起始节点
        p = x;
      }
    }
  }
  var linkTest = new DbLinkList();
  linkTest.insert(10);
  linkTest.insert(9);
  linkTest.insert(8);
  linkTest.insert(7);
  linkTest.insert(6);
  linkTest.insert(5);
  linkTest.insert(4);
  linkTest.insert(3);
  linkTest.insert(2);
  linkTest.insert(1);
  document.write("--排序前---<br/>")
  linkTest.print();
  linkTest.insertSort();
  document.write("<br/>--排序后---<br/>")
  linkTest.print();
</script>
</html>

運行結果如下：

 --排序前---

10 9 8 7 6 5 4 3 2 1 

9 10 8 7 6 5 4 3 2 1 

8 9 10 7 6 5 4 3 2 1 

7 8 9 10 6 5 4 3 2 1 

6 7 8 9 10 5 4 3 2 1 

5 6 7 8 9 10 4 3 2 1 

4 5 6 7 8 9 10 3 2 1 

3 4 5 6 7 8 9 10 2 1 

2 3 4 5 6 7 8 9 10 1 

1 2 3 4 5 6 7 8 9 10 

--排序后---

1 2 3 4 5 6 7 8 9 10

希望本文所述對大家JavaScript程式設計有所幫助。

陳述

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

Python vs. JavaScript：學習曲線和易用性Apr 16, 2025 am 12:12 AM

Python更適合初學者，學習曲線平緩，語法簡潔；JavaScript適合前端開發，學習曲線較陡，語法靈活。 1.Python語法直觀，適用於數據科學和後端開發。 2.JavaScript靈活，廣泛用於前端和服務器端編程。

Python vs. JavaScript：社區，圖書館和資源Apr 15, 2025 am 12:16 AM

Python和JavaScript在社區、庫和資源方面的對比各有優劣。 1)Python社區友好，適合初學者，但前端開發資源不如JavaScript豐富。 2)Python在數據科學和機器學習庫方面強大，JavaScript則在前端開發庫和框架上更勝一籌。 3)兩者的學習資源都豐富，但Python適合從官方文檔開始，JavaScript則以MDNWebDocs為佳。選擇應基於項目需求和個人興趣。

從C/C到JavaScript：所有工作方式Apr 14, 2025 am 12:05 AM

從C/C 轉向JavaScript需要適應動態類型、垃圾回收和異步編程等特點。 1）C/C 是靜態類型語言，需手動管理內存，而JavaScript是動態類型，垃圾回收自動處理。 2）C/C 需編譯成機器碼，JavaScript則為解釋型語言。 3）JavaScript引入閉包、原型鍊和Promise等概念，增強了靈活性和異步編程能力。

JavaScript引擎：比較實施Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和執行JavaScript代碼時，效果會有所不同，因為每個引擎的實現原理和優化策略各有差異。 1.詞法分析：將源碼轉換為詞法單元。 2.語法分析：生成抽象語法樹。 3.優化和編譯：通過JIT編譯器生成機器碼。 4.執行：運行機器碼。 V8引擎通過即時編譯和隱藏類優化，SpiderMonkey使用類型推斷系統，導致在相同代碼上的性能表現不同。

超越瀏覽器：現實世界中的JavaScriptApr 12, 2025 am 12:06 AM

JavaScript在現實世界中的應用包括服務器端編程、移動應用開發和物聯網控制：1.通過Node.js實現服務器端編程，適用於高並發請求處理。 2.通過ReactNative進行移動應用開發，支持跨平台部署。 3.通過Johnny-Five庫用於物聯網設備控制，適用於硬件交互。

使用Next.js（後端集成）構建多租戶SaaS應用程序Apr 11, 2025 am 08:23 AM

我使用您的日常技術工具構建了功能性的多租戶SaaS應用程序（一個Edtech應用程序），您可以做同樣的事情。首先，什麼是多租戶SaaS應用程序？多租戶SaaS應用程序可讓您從唱歌中為多個客戶提供服務

如何使用Next.js（前端集成）構建多租戶SaaS應用程序Apr 11, 2025 am 08:22 AM

本文展示了與許可證確保的後端的前端集成，並使用Next.js構建功能性Edtech SaaS應用程序。前端獲取用戶權限以控制UI的可見性並確保API要求遵守角色庫

JavaScript：探索網絡語言的多功能性Apr 11, 2025 am 12:01 AM

JavaScript是現代Web開發的核心語言，因其多樣性和靈活性而廣泛應用。 1)前端開發：通過DOM操作和現代框架（如React、Vue.js、Angular）構建動態網頁和單頁面應用。 2)服務器端開發：Node.js利用非阻塞I/O模型處理高並發和實時應用。 3)移動和桌面應用開發：通過ReactNative和Electron實現跨平台開發，提高開發效率。

See all articles