簡單理解冒泡排序

来源:http://www.cnblogs.com/loveyoume/archive/2016/12/18/6194591.html
-Advertisement-
Play Games

關於排序,其實不管是哪種語言,都有它內置的排序函數,我們要用的時候調用就行了,既然如此,我們為什麼還要講這個東西呢?我想,其實,我們講排序更多是在於排序中包含的思想演算法,因為,演算法對於電腦來說相當重要,一個好的演算法能夠讓電腦的效率達到事半功倍的效果,所以,演算法是電腦語言中一門相當熱門的課程,它 ...


  關於排序,其實不管是哪種語言,都有它內置的排序函數,我們要用的時候調用就行了,既然如此,我們為什麼還要講這個東西呢?我想,其實,我們講排序更多是在於排序中包含的思想演算法,因為,演算法對於電腦來說相當重要,一個好的演算法能夠讓電腦的效率達到事半功倍的效果,所以,演算法是電腦語言中一門相當熱門的課程,它所代表的電腦思維也是很值得我們去深入研究的。

  我也知道,關於我標題中的排序,博客園中的很多作者都寫過詳細解釋的文章,可能,筆者本人認為自己的理解更能體現出這個排序的工作原理吧,所以,筆者也就大慚不愧的在這裡再次寫下關於冒泡排序的文章,有需要的讀者可以看一下。

  再進入正題之前,我給大家介紹一下谷歌瀏覽器一個很有用的調試程式代碼的功能,如果你已經知道,請略過。

  首先,打開谷歌瀏覽器,輸入我們的代碼腳本:

  

  右鍵,點擊檢查,

  

  按順序點擊,獲取腳本的運行代碼:

  

  我的腳本是bubble.html,存儲在www.test.com功能變數名稱下麵的js/f目錄下麵,每個人的腳本不一樣,存儲的目錄也不一樣,請根據自己的情況來。

  調出腳本的內容後,下麵就是調試代碼了。

  

  選擇好了斷點之後,接下來在谷歌瀏覽器中再次運行腳本,就是對下麵的www.test.com/js/f/bubble.html再回車運行

  

  再次運行之後,你會看到這樣的東西:

  

  看到上面的那個藍色矩形框了嗎?這個藍色矩形框就是腳本正在運行的代碼位置,那我們怎麼讓腳本的代碼一步步的運行呢?

  這裡之所以對這個腳本的for迴圈代碼進行斷點監控,其實,我是為了查看冒泡排序到底是怎麼迴圈操作的,對於新手來說,這樣子直觀的查看冒泡排序代碼的運行情況會更好的瞭解演算法的執行過程。

  對於這個調試小功能就介紹到這裡了,下麵進入正題,沒辦法直接想象出冒泡排序的執行情況的話,你可以按我上面的步驟調出谷歌的調試功能,直觀的查看冒泡排序的整個過程。

  介紹一下兩個變數互相調換的思維,我們藉助中間變數來調換:

//交互元素,這裡的代碼是從腳本中截取出來的,這麼簡單,應該不影響理解
if(arr[j] > arr[j+1]){
mark = false;
var temp = arr[j];//temp是中間變數,把要交換的第一個元素arr[j]賦值給中間變數,也是把第一個元素存儲起來
arr[j] = arr[j+1];//第二個元素賦值給第一個元素,因為第一個元素我們已經存儲在中間變數中了,所以我們不用擔心它的值會被覆蓋掉
arr[j+1] = temp;//temp存儲了第一個元素的值,把它賦值給第二個元素,就是把第一個元素賦值給第二個元素了,到這一步,兩個元素已經交換位置了
}

    再介紹一下,冒泡排序的演算法過程:

  冒泡排序:通過對相鄰元素的對比,並交換位置,一步一步的把一個元素給挑選出來。

  舉個例子,對下麵的數組進行排序:

  這是一個無序的數組:2,9,4,8,5,1,0,7,3,6

  比較規則:大於>

  第一輪:

  第一次比較:我們把2和9作比較:2>9嗎 ?2和9比較是假,那麼我們不管它,繼續向前。

  第二次比較:9和4做比較,9>4嗎 ? 是真,那麼我們讓它們交換值,交換了值,它們的位置不就變了嗎,是吧?怎麼交換值上面已經講過,這裡不再重覆了。

  經過這次交換值,原來的數組已經變成:2,4,9,8,5,1,0,7,3,6

  第三次比較:9和8做比較,9>8嗎 ? 是真,那麼它們兩個繼續交換值,此時,數組已經變成:2,4,8,9,5,1,0,7,3,6

  ......................

  看到這裡9的位置了嗎?它是不是一步一步往後移?第一次比較因為9本來就是大的,所以,它不應該和2交換位置,因此,9沒有被放到前面去,第二次比較,因為9比4大,所以,根據比較規則,它們應該互換位置,也就是9向後移了一位,第三次比較,依然符合比較規則,所以9和8互換位置了,9又向後移了一步,接下來的比較和上面的比較是一樣的過程,你自己比較想象一下吧,這裡就不再重覆了。

  比較到最後一次:原數組的情況應該是:2,4,8,5,1,0,7,3,6,9

  經過第一輪的比較,我們已經把最大的元素給放到最後面去了,對吧?

  接下來,第二輪:

  首先說一下,第二輪的時候,原來的數組2,9,4,8,5,1,0,7,3,6,已經變成了2,4,8,5,1,0,7,3,6,9,我們是在已經冒泡過一次的數組的基礎上進行比較的,先確認這一點,要是你還認為是最初的數組,那麼,接下來的比較你會被搞糊塗的。呵呵。

  此刻的數組:2,4,8,5,1,0,7,3,6,9

  根據比較規則:2>4 嗎?是假,不管它,繼續向前比較。

  4>8嗎?是假,不管它,繼續向前比較。

  8>5嗎?是真,兩者交換值,也就是互換位置,此刻數組:2,4,5,8,1,0,7,3,6,9

  繼續向前,8>1嗎?是真,兩者交換位置,此刻數組:2,4,5,1,8,0,7,3,6,9

  .......

  比較到最後,原數組又發生了改變,已經變成:2,4,5,1,0,7,3,6,8,9

  經過兩輪的比較,原數組是否已經變得有序一點了?呵呵,沒有錯,兩輪之後,最後面的兩位數已經是有序的了。

  既然兩輪之後,最後面的兩位已經是有序的了,那麼,十輪之後呢?你自己想象一下。

  十輪之後,這個數組肯定已經排序好了。這就是冒泡排序的工作過程,相鄰元素比較,每一輪冒泡出一個有序的值。

  那麼,我們怎麼用代碼的方式實現冒泡排序呢?

  寫到這裡,我想大家應該知道怎麼做了吧?

  我們用兩層嵌套的for迴圈來實現這個過程,也就是實現冒泡排序:

//外層控制輪數
for(var i=0;i<len;i++){
  //內層對數組元素進行冒泡選擇
  for(var j=0;j<len-1-i;j++){
    //交互元素
    if(arr[j] > arr[j+1]){
    var temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;    
    }
  }
}

   上面那兩個嵌套的for迴圈看到了嗎?外層的for迴圈,我們就是用來控制比較········輪數········的,

  內層的for迴圈,我們用來控制···················每一輪的比較次數··················的,同時,在這個for迴圈裡面,我們還要做什麼呢?上面的文字敘述,你看懂了嗎?上面的文字敘述中,我們是不是在···每一次比較···的時候,都要根據比較規則來交換數組元素的位置,是吧?那麼,程式的工作過程也是一樣的,我們也要在這裡根據比較規則對數組的元素進行交換位置,為的是冒泡出我們需要的元素。

  下麵是冒泡排序的完整代碼,我對他進行了優化,當然,如果還可以優化,你也可以繼續優化的。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
    <meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
    <title>冒泡排序</title>
    <meta name="keywords" content="關鍵字列表" />
    <meta name="description" content="網頁描述" />
    <link rel="stylesheet" type="text/css" href="" />
    <style type="text/css"></style>
    <script type="text/javascript">
    //參數數字數組
    function bubble(arr){
        //檢查參數
        if(toString.call(arr) !== '[object Array]'){
            return false;
        }
        //獲取數組長度
        var len = arr.length;
        if(len <= 1){//小於1不用排序
            return arr;
        }
        //外層控制輪數
        for(var i=0;i<len;i++){
            //標記是否有排序的元素
            var mark = true;
            //內層對數組元素進行冒泡選擇
            for(var j=0;j<len-1-i;j++){
                //交互元素
                if(arr[j] > arr[j+1]){
                    mark = false;
                    var temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;    
                }
            }
            if(mark){
            //當沒有進行冒泡選擇時,證明已經排序好了
                return arr;    
            }
        }
    }
    //測試
    var ar = [9,3,7,4,8,2,5,1,6,0];
    alert(bubble(ar));
    </script>
</head>
<body>

</body>
</html>

  這裡只是簡單的介紹冒泡排序的工作原理,假如有時間,我再詳細講解一下另外三個排序,快速排序、選擇排序、插入排序。

  其實這三個排序的工作原理都和冒泡排序很相似,網上也有很多文章介紹,大家可以自己研究一下。


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

-Advertisement-
Play Games
更多相關文章
  • 項目中ajax交互成功前總會需要給用戶提醒,比如請稍候、正在載入中等等,那個等待的動圖以前項目中用的是gif,在移動端畫質很渣,有毛邊,於是在新項目中用css3展示載入中的動畫效果。 js放在項目公用里,樣式放到公用樣式里,調用的時候tipLoading(type,top,left),在ajax交互 ...
  • 下載 "mysql 5.7.msi" 安裝 雙擊mysql.msi,按照提示安裝。 安裝之後需要註意的問題( 重點 ) 設置mysql環境環境變數(讓mysql在cmd中的任何路徑下就可以被調用) 1. 滑鼠右擊電腦,點擊屬性 2. 選擇高級系統變數設置,點擊環境變數 3. 在系統變數裡面選擇PA ...
  • 1、先引入jquery.js 2、接著引入luhmCheck.js //銀行卡號Luhm校驗 3、看下麵的案例: 下麵是js 測試卡號: 1、6222600810010710887 2、6225881414207430 ...
  • 引言 提到前端往往很多人的映像就是入門簡單,HTML、CSS加一起一個星期基本上就能大概上手,JS難一點但也能很快寫一些簡單的小效果,在網上隨便一搜索各種特效代碼隨意用,一個新手前端也能在很短的時間里寫出炫酷的頁面效果,然而入門簡單並不意味著前端這碗飯很好吃,做慣了切圖、佈局、扣特效的前端新同學在向 ...
  • 直接插入排序演算法(Straight Insertion Sort),是排序演算法中簡單的一種演算法,基本思想如下: 將一個記錄插入到已排序好的有序表中,從而得到一個新,記錄數增1的有序表。即:先將序列的第1個記錄看成是一個有序的子序列,然後從第2個記錄逐個進行插入,直至整個序列有序為止。 要點:設立哨兵 ...
  • 本案例來自React.js中文官網對應內容。 一. 運行環境 二. 組件架構 App下有兩個子組件 (評論列表)和 (評論區),其中 下又有一個子組件 (評論) Comment包括一個h2的評論人名稱,一個span的評論內容,獲取數據之後,Comment組件以數組的形式傳入CommentList。 ...
  • 1.html 2.app.js ...
  • 1.定義變數:Sass中定義變數的關鍵字是'$'(畢竟程式員缺錢),並使用冒號(:)進行賦值,例如: $width:200px;//定義了一個名為width的變數,值為200px 2.普通變數和預設變數: 普通變數便是我們在大括弧外用上面的方式聲明的變數,可全局使用。 預設變數需要在聲明的變數後加上 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...