幾種經典排序演算法的JS實現

来源:http://www.cnblogs.com/HiuYanChong/archive/2016/03/25/5317938.html
-Advertisement-
Play Games

一.冒泡排序 二.選擇排序 三.插入排序 四.希爾排序 五.歸併排序 六.快速排序 ...


一.冒泡排序

 1 function BubbleSort(array) {
 2     var length = array.length;
 3     for (var i = length - 1; i > 0; i--) { //用於縮小範圍
 4         for (var j = 0; j < i; j++) { //在範圍內進行冒泡,在此範圍內最大的一個將冒到最後面
 5             if (array[j] > array[j+1]) { 
 6                 var temp = array[j];
 7                 array[j] = array[j+1];
 8                 array[j+1] = temp;
 9             }
10         }
11         console.log(array);
12         console.log("-----------------------------");
13     }
14     return array;
15 }
16 
17 
18 var arr = [10,9,8,7,7,6,5,11,3];
19 var result = BubbleSort(arr);
20 console.log(result); 
21 /*
22 [ 9, 8, 7, 7, 6, 5, 10, 3, 11 ]
23 -----------------------------
24 [ 8, 7, 7, 6, 5, 9, 3, 10, 11 ]
25 -----------------------------
26 [ 7, 7, 6, 5, 8, 3, 9, 10, 11 ]
27 -----------------------------
28 [ 7, 6, 5, 7, 3, 8, 9, 10, 11 ]
29 -----------------------------
30 [ 6, 5, 7, 3, 7, 8, 9, 10, 11 ]
31 -----------------------------
32 [ 5, 6, 3, 7, 7, 8, 9, 10, 11 ]
33 -----------------------------
34 [ 5, 3, 6, 7, 7, 8, 9, 10, 11 ]
35 -----------------------------
36 [ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
37 -----------------------------
38 [ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
39 */

 

二.選擇排序

 1 function SelectionSort(array) {
 2     var length = array.length;
 3     for (var i = 0; i < length; i++) { //縮小選擇的範圍
 4         var min = array[i]; //假定範圍內第一個為最小值
 5         var index = i; //記錄最小值的下標
 6         for (var j = i + 1; j < length; j++) { //在範圍內選取最小值
 7             if (array[j] < min) {
 8                 min = array[j];
 9                 index = j;
10             }
11         }
12         if (index != i) { //把範圍內最小值交換到範圍內第一個
13             var temp = array[i];
14             array[i] = array[index];
15             array[index] = temp;
16         }
17         console.log(array);
18         console.log("---------------------");
19     }
20     return array;
21 }
22 
23 var arr = [ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ];
24 var result = SelectionSort(arr);
25 console.log(result);
26 /*
27 [ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ]
28 ---------------------
29 [ 1, 2, 100, 90, 65, 5, 4, 10, 10, 4 ]
30 ---------------------
31 [ 1, 2, 4, 90, 65, 5, 100, 10, 10, 4 ]
32 ---------------------
33 [ 1, 2, 4, 4, 65, 5, 100, 10, 10, 90 ]
34 ---------------------
35 [ 1, 2, 4, 4, 5, 65, 100, 10, 10, 90 ]
36 ---------------------
37 [ 1, 2, 4, 4, 5, 10, 100, 65, 10, 90 ]
38 ---------------------
39 [ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
40 ---------------------
41 [ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
42 ---------------------
43 [ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
44 ---------------------
45 [ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
46 ---------------------
47 [ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
48 */

 

三.插入排序

 1 function InsertionSort(array) {
 2     var length = array.length;
 3     for (var i = 0; i < length - 1; i++) {
 4         //i代表已經排序好的序列最後一項下標
 5         var insert = array[i+1];
 6         var index = i + 1;//記錄要被插入的下標
 7         for (var j = i; j >= 0; j--) {
 8             if (insert < array[j]) {
 9                 //要插入的項比它小,往後移動
10                 array[j+1] = array[j];
11                 index = j;
12             }
13         }
14         array[index] = insert;
15         console.log(array);
16         console.log("-----------------------");
17     }
18     return array;
19 }
20 
21 var arr = [100,90,80,62,80,8,1,2,39];
22 var result = InsertionSort(arr);
23 console.log(result);
24 /*
25 [ 90, 100, 80, 62, 80, 8, 1, 2, 39 ]
26 -----------------------
27 [ 80, 90, 100, 62, 80, 8, 1, 2, 39 ]
28 -----------------------
29 [ 62, 80, 90, 100, 80, 8, 1, 2, 39 ]
30 -----------------------
31 [ 62, 80, 80, 90, 100, 8, 1, 2, 39 ]
32 -----------------------
33 [ 8, 62, 80, 80, 90, 100, 1, 2, 39 ]
34 -----------------------
35 [ 1, 8, 62, 80, 80, 90, 100, 2, 39 ]
36 -----------------------
37 [ 1, 2, 8, 62, 80, 80, 90, 100, 39 ]
38 -----------------------
39 [ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
40 -----------------------
41 [ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
42 */

 

四.希爾排序

 1 function ShellSort(array) {
 2     var length = array.length;
 3     var gap = Math.round(length / 2);
 4     while (gap > 0) {
 5         for (var i = gap; i < length; i++) {
 6             var insert = array[i];
 7             var index = i;
 8             for (var j = i; j >= 0; j-=gap) {
 9                 if (insert < array[j]) {
10                     array[j+gap] = array[j];
11                     index = j;
12                 }
13             }
14             array[index] = insert;
15         }
16         console.log(array);
17         console.log("-----------------------");
18         gap = Math.round(gap/2 - 0.1);
19     }
20     return array;
21 }
22 
23 var arr = [ 13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10 ];
24 var result = ShellSort(arr);
25 console.log(result); 
26 /*
27 [ 13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94 ]
28 -----------------------
29 [ 13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94 ]
30 -----------------------
31 [ 13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94 ]
32 -----------------------
33 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
34 -----------------------
35 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
36 */

 

五.歸併排序

  1 function MergeSort(array) {
  2     var length = array.length;
  3     if (length <= 1) {
  4         return array;
  5     } else {
  6         var num = Math.ceil(length/2);
  7         var left = MergeSort(array.slice(0, num));
  8         var right = MergeSort(array.slice(num, length));
  9         return merge(left, right);
 10     }
 11 }
 12 
 13 function merge(left, right) {
 14     console.log(left);
 15     console.log(right);
 16     var a = new Array();
 17     while (left.length > 0 && right.length > 0) {
 18         if (left[0] <= right[0]) {
 19             var temp = left.shift();
 20             a.push(temp);
 21         } else {
 22             var temp = right.shift();
 23             a.push(temp);
 24         }
 25     }
 26     if (left.length > 0) {
 27         a = a.concat(left);
 28     }
 29     if (right.length > 0) {
 30         a = a.concat(right);
 31     }
 32     console.log(a);
 33     console.log("-----------------------------");
 34     return a;
 35 }
 36 
 37 var arr = [ 13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10 ];
 38 var result = MergeSort(arr);
 39 console.log(result);
 40 /*
 41 [ 13 ]
 42 [ 14 ]
 43 [ 13, 14 ]
 44 -----------------------------
 45 [ 94 ]
 46 [ 33 ]
 47 [ 33, 94 ]
 48 -----------------------------
 49 [ 13, 14 ]
 50 [ 33, 94 ]
 51 [ 13, 14, 33, 94 ]
 52 -----------------------------
 53 [ 82 ]
 54 [ 25 ]
 55 [ 25, 82 ]
 56 -----------------------------
 57 [ 59 ]
 58 [ 94 ]
 59 [ 59, 94 ]
 60 -----------------------------
 61 [ 25, 82 ]
 62 [ 59, 94 ]
 63 [ 25, 59, 82, 94 ]
 64 -----------------------------
 65 [ 13, 14, 33, 94 ]
 66 [ 25, 59, 82, 94 ]
 67 [ 13, 14, 25, 33, 59, 82, 94, 94 ]
 68 -----------------------------
 69 [ 65 ]
 70 [ 23 ]
 71 [ 23, 65 ]
 72 -----------------------------
 73 [ 45 ]
 74 [ 27 ]
 75 [ 27, 45 ]
 76 -----------------------------
 77 [ 23, 65 ]
 78 [ 27, 45 ]
 79 [ 23, 27, 45, 65 ]
 80 -----------------------------
 81 [ 73 ]
 82 [ 25 ]
 83 [ 25, 73 ]
 84 -----------------------------
 85 [ 39 ]
 86 [ 10 ]
 87 [ 10, 39 ]
 88 -----------------------------
 89 [ 25, 73 ]
 90 [ 10, 39 ]
 91 [ 10, 25, 39, 73 ]
 92 -----------------------------
 93 [ 23, 27, 45, 65 ]
 94 [ 10, 25, 39, 73 ]
 95 [ 10, 23, 25, 27, 39, 45, 65, 73 ]
 96 -----------------------------
 97 [ 13, 14, 25, 33, 59, 82, 94, 94 ]
 98 [ 10, 23, 25, 27, 39, 45, 65, 73 ]
 99 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
100 -----------------------------
101 [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
102 */

 

六.快速排序

 1 function QuickSort(array) {
 2     var length = array.length;
 3     if (length <= 1) {
 4         return array;
 5     } else {
 6         var smaller = [];
 7         var bigger = [];
 8         var base = [array[0]];
 9         for (var i = 1; i < length; i++) {
10             if (array[i] <= base[0]) {
11                 smaller.push(array[i]);
12             } else {
13                 bigger.push(array[i]);
14             }
15         }
16         console.log(smaller.concat(base.concat(bigger)));
17         console.log("-----------------------");
18         return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));
19     }
20 }
21 
22 
23 var arr = [ 8, 10, 100, 90, 65, 5, 4, 10, 2, 4 ];
24 var result = QuickSort(arr);
25 console.log(result);
26 /*
27 [ 5, 4, 2, 4, 8, 10, 100, 90, 65, 10 ]
28 -----------------------
29 [ 4, 2, 4, 5 ]
30 -----------------------
31 [ 2, 4, 4 ]
32 -----------------------
33 [ 2, 4 ]
34 -----------------------
35 [ 10, 10, 100, 90, 65 ]
36 -----------------------
37 [ 90, 65, 100 ]
38 -----------------------
39 [ 65, 90 ]
40 -----------------------
41 [ 2, 4, 4, 5, 8, 10, 10, 65, 90, 100 ]
42 */

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 信號的多徑傳播對環境具有依賴性,呈現出非常強的特殊性。對於每個位置而言,該位置上通道的多徑結構是惟一的,終端發射的無線電渡經過反射和折射,產生與周圍環境密切相關的特定模式的多徑信號,這樣的多徑特征可以認為是該位置的“指紋”。基站天線陣列檢測信號的幅度和相位等特性,提取多徑干擾特征參數,將該參數與預先 ...
  • 原地址:http://www.cnblogs.com/BoyXiao/archive/2010/05/07/1729376.html 首先來明確一個問題,那就是在某些情況下,有些對象,我們只需要一個就可以了, 比如,一臺電腦上可以連好幾個印表機,但是這個電腦上的列印程式只能有一個, 這裡就可以通 ...
  • join() 函數 join()函數是將兩個列表連接合併成一個列表。 >>join(10px 20px, 30px 40px) (10px 20px 20px 40px) >>join((blue,red),(#abc,#def)) (#0000ff,#ff0000,#aabbcc,#ddeeff) ...
  • Merge是一個非常有用的功能,類似於Mysql里的insert into on duplicate key. Oracle在9i引入了merge命令, 通過這個merge你能夠在一個SQL語句中對一個表同時執行inserts和updates操作. 當然是update還是insert是依據於你的指定 ...
  • js中不允許出現“ - ” 頁面中改變文字大小-案例: class 點擊按鈕變成覆選框checkbox 改變DIV的浮動 判斷註意事項 所有的相對路徑都別拿來做判斷。。。 img src href="css.css" 絕對路徑可以: img src="http://........jpg" 顏色值不 ...
  • 出處:http://blog.csdn.net/dyllove98/article/details/8957232 CSS3中和動畫有關的屬性有三個 transform、 transition 和 animation。下麵來一一說明: transform 從字面來看transform的釋義為改變,使 ...
  • 1:基本雛形 <html><head> <meta charset="UTF-8"> <title></title></head><body><!--標題標簽--> <h1>11111111111111111</h1> <h2>11111111111111111</h2> <h3>111111111 ...
  • 今天編碼時遇到一個問題,通過後臺查詢的數據設置前端checkbox的選中狀態,設置選中狀態為.attr('checked','true');沒有問題,但是當數據重新載入時,checkbox應清空即所有checkbox為未選中狀態,使用.attr('checked','false');無效果,且全部為 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...