冒泡排序進階優化

冒泡排序的思想：我們以升序排列為例，所謂冒泡排序就是在無序數組中每執行一趟選出這一趟中最大的數放在最後面，第二趟選出次大的數放在倒數第二位上，直到完成排序。以此類推降序就是將小的數放在後面排序。代碼如下： 

方法（一）

 1   var arr = [6, 5, 3, 4, 1, 2];
 2     function sort(arr) {
 3         var maxNum= arr.length - 1;
 4         // 遍曆數組，次數就是arr.length - 1
 5         for (var i = 0; i < maxNum- 1; i++) {
 6             // 這裡根據外層for迴圈的i，逐漸減少內層 for迴圈j的次數所以要減i。
 7             for (var j = 0; j < maxNum-i; j++) {
 8                 if (arr[j] > arr[j + 1]) {
 9                     //設置第三方變數（x）來用於數據交換，且這個變數放在迴圈的外面性能要好，兩兩對比，把大的數放在後面。
10                     var x = arr[j + 1];
11                     arr[j + 1] = arr[j];
12                     arr[j] = x;
13                     // 利用加法來實現兩個數據的交換
14                     // arr[j] = arr[j] + arr[j+1];
15                     // arr[j+1] = arr[j] - arr[j+1];
16                     // arr[j] = arr[j] - arr[j+1];
17                     // 利用位運算實現兩個數據的交換
18                     //arr[j] = arr[j]^arr[j+1];
19                     //arr[j+1] = arr[j]^arr[j+1];
20                     //arr[j] = arr[j]^arr[j+1];
21                 }
22             }
23             console.log("第" + (i + 1) + "次排序後的數組是" + arr);
24         }
25     }
26     sort(arr);
27     console.log(arr);

運行圖：

方法（二）

主要還是對方法一的優化，設置一個標誌，如果這一趟下來發生了交換，則為true，否則為false。如果有一趟下來沒有發生交換，則說明排序已經完成。代碼如下：

 1  var arr = [3, 2, 1, 4,5,6];
 2     function sort(arr) {
 3         var maxNum= arr.length - 1;
 4         // 遍曆數組，次數就是arr.length - 1
 5         for (var i = 0; i < maxNum- 1; i++) {
 6             // 聲明一個變數，作為標誌位
 7             var done = true;
 8             // 這裡根據外層for迴圈的i，逐漸減少內層 for迴圈j的次數所以要減i。
 9             for (var j = 0; j < maxNum-i; j++) {
10                 if (arr[j] > arr[j + 1]) {
11                     //設置第三方變數（x）來用於數據交換，且這個變數放在迴圈的外面性能要好，兩兩對比，把大的數放在後面。
12                     var x = arr[j + 1];
13                     arr[j + 1] = arr[j];
14                     arr[j] = x;
15                     // 利用加法來實現兩個數據的交換
16                     // arr[j] = arr[j] + arr[j+1];
17                     // arr[j+1] = arr[j] - arr[j+1];
18                     // arr[j] = arr[j] - arr[j+1];
19                     // 利用位運算實現兩個數據的交換
20                     //arr[j] = arr[j]^arr[j+1];
21                     //arr[j+1] = arr[j]^arr[j+1];
22                     //arr[j] = arr[j]^arr[j+1];
23                     done = false;
24                 }
25             }
26             if (done) {
27                 break;
28             }
29             console.log("第" + (i + 1) + "次排序後的數組是" + arr);
30         }
31     }
32     sort(arr);
33     console.log(arr);

運行圖：

  方法（三）

      是對前兩種方式的進一步優化，假如數組長度是30，如果只有前15位是無序排列的，後十五位是有序且都大於前15位，所以第一趟遍歷排序的時候發生交換的位置必定小於15，且該位置之後的必定有序，我們只需要排序好該位置之前的就可以，因此我們要來標記這個位置就可以了，代碼如下：

 1  var arr = [3, 2, 1, 4, 5, 6];
 2 
 3     function sort(arr) {
 4         var n = arr.length;
 5         var j, k;
 6         var flag = n;
 7         while (flag > 0) {
 8             k = flag;
 9             flag = 0;
10             for (j = 1; j < k; j++) {
11                 if (arr[j - 1] > arr[j]) {
12                     x = arr[j - 1];
13                     arr[j - 1] = arr[j];
14                     arr[j] = x;
15                     flag = j;
16                 }
17             }
18         }
19     }
20     sort(arr);
21     console.log(arr);

 總結分析：

         1.比較相鄰的兩個元素，如果前一個比後一個大（小），則交換位置。

　　　2.第一輪的時候最後一個元素應該是最大（最小）的一個。

　　　3.按照步驟一的方法進行相鄰兩個元素的比較，這個時候由於最後一個元素已經是最大（最小）的了，所以最後一個元素不用比較。