JS—關於排序:冒泡、選擇、歸併、快排

来源:https://www.cnblogs.com/liu-jh/archive/2022/03/29/16074012.html
-Advertisement-
Play Games

一、冒泡排序 原理:相鄰兩元素之間兩兩比較,比較出大值進行賦值互換,再依次與相鄰的元素比較,層層遞進。#互換元素位置,相互賦值。 時間複雜度:最好O(n),最差O(n^2) 1、比較相鄰的兩個元素,如果前一個比後一個大,則交換位置。2、比較完第一輪的時候,最後一個元素是最大的元素。3、這時候最後一個 ...


一、冒泡排序

原理:相鄰兩元素之間兩兩比較,比較出大值進行賦值互換,再依次與相鄰的元素比較,層層遞進。#互換元素位置,相互賦值。

時間複雜度:最好O(n),最差O(n^2)

1、比較相鄰的兩個元素,如果前一個比後一個大,則交換位置。
2、比較完第一輪的時候,最後一個元素是最大的元素。
3、這時候最後一個元素是最大的,所以最後一個元素就不需要參與比較大小。

const bubbleSort = (arr)=>{
    for(let i = 0 ; i < arr.length - 1 ; i++){
        for(let j = 0 ; j < arr.length - 1 - i ; j++){
            if(arr[j] > arr[j + 1]){
                var temp = 0;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

解析

兩個迴圈,當i=0的時候,裡面的迴圈完整執行,從j=0執行到j=7,結果是將最大的數排到了最後。當i=1的時候,裡面的迴圈再次完整執行,由於最大的數已經在最後了,沒有必要去比較數組的最後兩項,這也是j<arr.length-1-i的巧妙之處。
二、選擇排序

原理:先定義一個元素的最大值或最小值,拿每個元素與最值比較,取大值放到數組最右端,或者最小值放到數組最左端,層層比較。#互換元素下標位置,再賦值。

時間複雜度:O(n^2)

const selectionSort = (arr)=>{
    let minIndex,temp;
    for(let i = 0 ; i < arr.length ; i++){
        minIndex = i;
        for(let j = i + 1 ; j < arr.length ; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j; 
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

console.log(selectionSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]
解析
首先從原始數組中找到最小的元素,並把該元素放在數組的最前面,然後再從剩下的元素中尋找最小的元素,放在之前最小元素的後面,直到排序完畢。
minIndex始終保存著最小值的位置的索引,隨著i的自增,遍歷的數組長度越來越短,直到完成排序。
三、歸併排序

歸併排序(MERGE-SORT)是利用歸併的思想實現的排序方法,
該演算法採用經典的分治(divide-and-conquer)策略
(分治法將問題分(divide)成一些小的問題然後遞歸求解,
而治(conquer)的階段則將分的階段得到的各答案"修補"在一起,即分而治之)。

歸併排序採用的是分治的思想,首先是“分”,將一個數組反覆二分為兩個小數組,直到每個數組只有一個元素;其次是“治”,從最小數組開始,兩兩按大小順序合併,直到併為原始數組大小,下麵是圖解:

 

“分”就是將原始數組逐次二分,直到每個數組只剩一個元素,一個元素的數組自然是有序的,所以就可以開始“治”的過程了。

時間複雜度分析:分的過程需要三步:log8 = 3,而每一步都需要遍歷一次8個元素,所以8個元素共需要運行 8log8 次指令,那麼對於 n 個元素,時間複雜度為 O(nlogn)。

 “治”實際上是將已經有序的數組合併為更大的有序數組。那怎麼做呢?就是創建一個新數組,比較left[0]和right[0] ,那個比較小就將那個的值放進新數組,然後再繼續比較left[0]和right[1],或者是left[1]和right[0]。可以看出數組left,right都只需遍歷一遍,所以對兩個有序數組的排序的時間複雜度為O(n)。

一、遞歸分解

 

 二、合併為有序數組

 

const mergeSort = (arr)=>{
    let len = arr.length;
    if(len < 2){
        return arr;
    }
    let mid = Math.floor(len/2);
    //拆分成兩個子數組
    let left = arr.slice(0,mid);
    let right = arr.slice(mid,len);
    //遞歸拆分
    let mergeSortLeft = mergeSort(left);
    let mergeSortRight = mergeSort(right);
    //組合
    return merge(mergeSortLeft,mergeSortRight)
}

const merge = (left,right)=>{
    const arr1 = [];
    while(left.length && right.length){
        // 註意: 判斷的條件是小於或等於,如果只是小於,那麼排序將不穩定.
        if(left[0]<=right[0]){
            //每次都要刪除left或者right的第一個元素,將其加入arr1中
            arr1.push(left.shift());
        }else{
            arr1.push(right.shift());
        }
    }
    //將剩下的元素加上
    while(left.length) arr1.push(left.shift());
    while(right.length) arr1.push(right.shift());

    return arr1;
}


console.log(mergeSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

參考: https://www.cnblogs.com/lyt0207/p/12489144.html

四、快速排序

"快速排序"的思想很簡單,整個排序過程只需要三步:

(1)在數據集之中,選擇一個元素作為"基準"(pivot)。

(2)所有小於"基準"的元素,都移到"基準"的左邊;所有大於"基準"的元素,都移到"基準"的右邊。

(3)對"基準"左邊和右邊的兩個子集,不斷重覆第一步和第二步,直到所有子集只剩下一個元素為止。

//首先,定義一個quickSort函數,它的參數是一個數組。
const quickSort = (arr)=>{
    //然後,檢查數組的元素個數,如果小於等於1,就返回。
    if(arr.length <= 1){
        return arr;
    }
    //接著,選擇"基準"(pivot),並將其與原數組分離,再定義兩個空數組,用來存放一左一右的兩個子集。
    var pivotIndex = Math.floor(arr.length / 2);
    var pivot = arr.splice(pivotIndex,1)[0];
    var left = [];
    var right = [];
    //然後,開始遍曆數組,小於"基準"的元素放入左邊的子集,大於基準的元素放入右邊的子集。
    for(let i = 0 ; i < arr.length ; i++){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    //最後,使用遞歸不斷重覆這個過程,就可以得到排序後的數組。
    return quickSort(left).concat([pivot],quickSort(right));
}

console.log(quickSort([25,1,0,8,30,100,55,66]));//[0, 1, 8, 25, 30, 55, 66, 100]

 


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

-Advertisement-
Play Games
更多相關文章
  • 鏡像下載、功能變數名稱解析、時間同步請點擊 阿裡雲開源鏡像站 export命令用於將shell變數輸出為環境變數,或者將shell函數輸出為環境變數。 一個變數創建時,它不會自動地為在它之後創建的shell進程所知。而命令export可以向後面的shell傳遞變數的值。 命令語法 export [參數] 命 ...
  • 寫在前面 Clickhouse 從 21.11 版本開始,除了提供類似SqlServer、MySQL CREATE FUNCTION 的自定義函數之外,還有一個用戶自定義函數(UDF),與其說是“用戶自定義函數”,為了避免混淆,稱之為”用戶自定義外部函數“更為準確。官方對此功能的解釋: ClickH ...
  • MySQL版本:5.7.34-log *通過創建函數的方法,目前可以實現整數金額的轉換,網上暫未找到MySQL版本的故自己參照其他資料庫版本的改編了一下,*僅供參考!!! 使用方法:select rmb(10000) CREATE DEFINER = `root`@`%` FUNCTION `rmb ...
  • 最近Jetpack Compose發佈了Beta版本,抽時間瞭解了一下Compose帶來的改變和其中的一些原理。本文不會講解具體API,只是比較隨意的分享自己的一些疑問以及在探尋答案過程中的一些收穫。 ...
  • 基於大家都期望的更美好的未來世界,數字管家必定會為實現更便捷、更具幸福感的生活體驗而不斷努力,期待作為開發者的你加入併為之貢獻一臂之力。 ...
  • 在涉及團購、外賣、快遞、家政、物流、搬家等生活服務類的App、小程式中,填寫收貨地址是用戶高頻使用的功能。這一功能通常採取讓用戶手動填寫的解決方案,例如上下拉動選擇浙江省-->杭州市-->西湖區-->西溪街道,再切換到姓名輸入框輸入姓名-->電話輸入框輸入電話等一系列的操作。從中我們不難發現手動輸入 ...
  • 平時想記錄的東西太多了,關於日常感知,莫明其妙的小想法、隨筆,這些發到公眾號又不太合適。 索性擼起袖子加油乾。埋頭苦幹了一周多 ...
  • 前言 元宇宙正在如火如荼地發展,大有引領未來潮流之勢。對於我們這麼專業的(web 前端)團隊來說,元宇宙是一個大 (wan) 顯 (quan) 身 (bu) 手 (dong) 的領域,因此團隊在這方面投入了很多人力進行預研和總結,請隨本文一起踏入元宇宙的神秘世界。 元宇宙與 3D 元宇宙,或稱為後設 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...