冒泡排序算法

CarterLi 發布于2019-08-20 15:56 / 936人閱讀

摘要：如下是一個基本的冒泡排序算法，執行的過程外部循環次內部循環每次用的值與的值進行比較由于外部循環的變量每次進入內部循環都不會改變，也就是的值進入內部循環后，都會以自身與也就是整個數組的所有元素比較一輪，結果是小于的數值都會被放到數組的開頭經過

如下是一個基本的冒泡排序算法，執行的過程

外部循環len次

內部循環每次用arr[i]的值與arr[j]的值進行比較

由于外部循環的i變量每次進入內部循環都不會改變，也就是arr[i]的值進入內部循環后，都會以自身與arr[j]（也就是整個數組的所有元素）比較一輪，結果是小于arr[i]的數值都會被放到數組的開頭

經過外層循環的一次次的進入內層循環的比對后，數組也依照從小到大的順序排列了

let arr = [1, 3, 2]
let len = arr.length

for(let i = 0; i < len; i++){
    for(let j = 0; j < len; j++){
        if(arr[i] > arr[j]){
            let temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
}

我們來分解步驟

第一輪外層循環 i = 0
    第一輪內部循環 
    j = 0
    
    arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++， arr保持現狀 [1, 3, 2]
    
    j = 1
    
    arr[i] = 1 arr[j] = 3 arr[i] > arr[j]不成立，j++, arr保持原樣 [1, 3, 2]
    
    j = 2
    
    arr[i] = 1 arr[j] = 2 arr[i] > arr[j]不成立，j++, arr保持原樣 [1, 3, 2]
    
    j = 3
    
    arr[i] = 1 arr[j] = undefined 由于len = 3 ,故 j < len不成立，第一輪層循環結束

第二輪外層循環 i = 1
    第二輪內部循環
    j = 0
    
    arr[i] = 3 arr[j] = 1 arr[i] > arr[i]成立， arr[i]和arr[j]交換數值,arr更新為[3, 1, 2]
    
    j = 1
    
    arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 1, 2]
    
    j = 2
    
    arr[i] = 1 arr[j] = 2 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 1, 2]
    
    j = 3
    
    arr[i] = 1 arr[j] = undefined 由于len = 3 ,故 j < len不成立，第二輪層循環結束

第三輪外層循環 i = 2
    第三輪內部循環
    j = 0
    
    arr[i] = 2 arr[j] = 3 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 1, 2]
    
    j = 1
    
    arr[i] = 2 arr[j] = 1 arr[i] > arr[i]成立, arr[i]和arr[j]交換數值,arr更新為[3, 2, 1]
    
    j = 2
    
    arr[i] = 1 arr[j] = 1 arr[i] > arr[i]不成立，j++, arr保持原樣 [3, 2, 1
    
    j = 3
    
    由于眾所周知的原因，第三輪內部循環結束

第四輪外層循環 i = 3

由于i < len不成立，外部循環結束，現在我們的數組最終結果為[3, 2, 1]

接下來我們來看看有沒有優化的空間

我們發現，每次內部循環都市從索引 let j = 0; 開始的，也就是說每次內部循環 arr[j]
都會把數組遍歷一遍，由于在上一次的內部循環結束后，都會把最大的數放到數組的頭部，所以再次進入內部循環時，如果還去從頭比較就是浪費時間

所以如何讓內部循環將上次列入最大值的位置忽略呢？

答案就是i變量,每次結束一次外部循環i變量都會加1，這也代表著有i個最大值被置于數組頭部，也就是我們需要忽略的位置，所以，我們只需要將內部循環的起始位置i加上i，就可以將已經確定的位置忽略比較

for(let i = 0; i < len; i++){
    for(let j = 0 + i; j < len; i++){
        // 直接簡寫成let j = i也行
    }
}

然后我們來驗證一下優化的成果

用一個大一點的數組，并且記錄下循環次數

let arr = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]
let len = arr.length
let count = 0

for(let i = 0; i < len; i++){
  for(let j = 0; j < len; j++){
    count++
    if(arr[i] > arr[j]){
      let temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }
}

console.log(arr, count)
arr = [324, 76, 65, 62, 56, 51, 45, 44, 43, 43, 34, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 0]
count = 1156次

下面看下優化過的

let arr = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7]
let len = arr.length
let count = 0

for(let i = 0; i < len; i++){
  for(let j = i; j < len; j++){
    count++
    if(arr[i] > arr[j]){
      let temp = arr[i]
      arr[i] = arr[j]
      arr[j] = temp
    }
  }
}

console.log(arr, count)
arr = [0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 34, 43, 43, 44, 45, 51, 56, 62, 65, 76, 324]
595次

結果毋庸置疑減少了近半數的無用循環，那么到此為止了嗎？
讓我們再來看看
我們現在用的比較方式是基于用數組中的一個位置與所有位置進行比較，然后在下一輪比較時忽略已經確定的位置，
如下：
[1, 3, 2]

1 比 1

1 比 3

1 比 2

大家是不是發現了一個無效操作？就是1和1比較，這就是一個無效操作，由于外部循環的i和內部循環的j初始化會相等，所以arr[i]和arr[j]會取到同一個位置的值比較一次，那么怎么優化這個操作呢？

答案就是讓內部j從第二位開始，避免和arr[i]取同一個值的情況

for(let i = 0; i < len; i++){
    for(let j = i; j < len - 1; j++){
       if(arr[i] > arr[j+1]){
           temp = arr[i];
           arr[i] = arr[j+1];
           arr[j+1] = temp;
       } 
    }
}

注意我給內部循環的len減去了1，是由于給j+1的會導致最后一次arr[j+1]會溢出數組，所以將其減1，正好彌補了j+1，也不會出現少遍歷數組元素的情況

然后我們來看看成果

[0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 34, 43, 43, 44, 45, 51, 56, 62, 65, 76, 324]
561次

GPU云服務器云服務器冒泡排序前端冒泡排序冒泡排序代碼 js冒泡排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/82602.html

JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
數據結構與算法——冒泡排序

摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實現細節，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩定性一個穩定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩定。 1. 導言因為這是排序算法系列的第一篇文章，所以多啰嗦幾句。排序是很常見的算法之一，現在很多編程語言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...

Yang_River 2019-08-16 15:51 評論0 收藏0
排序算法分析總結（附js實現）

摘要：本文對一些排序算法進行了簡單分析，并給出了的代碼實現。平均時間復雜度不好分析，它是冒泡排序是穩定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復雜度是的排序算法。歸并排序，會將數組從中間分成左右兩部分。本文對一些排序算法進行了簡單分析，并給出了 javascript 的代碼實現。因為本文包含了大量的排序算法，所以分析不會非常詳細，適合有對排序算法有一定了解的同學。本文內容其實不...

liaoyg8023 2019-08-23 17:11 評論0 收藏0
數據結構與算法（二）：帶你讀懂冒泡排序（Bubble Sorting）

摘要：經過一次冒泡排序，最終在無序表中找到一個最大值，第一次冒泡結束。也是我們后面要說的冒泡排序的優化。冒泡排序只執行第一層循環，而不會執行第二層循環。因此冒泡排序的時間復雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

chuyao 2019-08-19 11:46 評論0 收藏0
算法之旅 | 冒泡排序法

摘要：學堂碼匠本期繼續走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優化假如序列的數據為使用上面的冒泡排序法進行排序，得到的結果肯定沒有問題，但是，待排序的序列是有序的，理論上是無需遍歷排序。 HTML5學堂-碼匠：本期繼續走入算法 —— 冒泡排序法。冒泡排序算法相對簡單，容易上手，穩定性也比較高,算是一種較好理解的算法，也是面試官高頻提問的算法之一。 Tips：關于算法及排序的基礎知識...

qujian 2019-08-20 19:05 評論0 收藏0