簡介

冒泡排序是一種較簡單排序算法。它重復地走訪過要排序的元素列，依次比較和交換兩個相鄰的元素，每一次遍歷會將一個元素“浮”到數(shù)列的頂端，所以命名為冒泡排序。

排序過程

對于數(shù)組[5, 10, 13, 15, 10, 100, 78, 46]，要求從小到大排序。

從下標為j開始，比較相鄰兩個元素，如果arr[j] > arr[j + 1]，則交換元素。

然后j++，比較下一對元素。重復上一步操作，直到這一次遍歷結(jié)束。

從數(shù)組開始，重復1、2操作。

結(jié)束的時候，數(shù)組變成有序的數(shù)組。

js代碼如下

var array = [5, 10, 13, 15, 10, 100, 78, 46];function bubbing(arr) {for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {const temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}console.log(arr); }bubbing(array);

時間復雜度

長度為n的數(shù)組，假設(shè)冒泡排序時遇到最壞的情況，數(shù)組是反序的。每一趟需要交換?n - i?次。那么總共需要交換次數(shù)C為：

C = n - 1 + n - 2 + …… + 1

根據(jù)高斯求和公式可得：

C = n * (n - 1) / 2

那么冒泡排序的時間復雜度為：O(n2)

但是經(jīng)過優(yōu)化的冒泡排序可以在最好的情況，時間復雜度為O(n)，下面第二次優(yōu)化會講。

優(yōu)化

第一次優(yōu)化

由于每次都會把一個最大或最小的元素排列到該去的位置，所以下一次遍歷的時候就可以不遍歷已有序的部分。

function bubbing_2(arr) {for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {const temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}console.log(arr); }bubbing_2(array);

第二次優(yōu)化

第一次優(yōu)化減少了要遍歷的次數(shù)，第二次優(yōu)化則是加了一個崗哨。每一次遍歷的時候判斷是否發(fā)生過元素交換操作，如果沒有沒有發(fā)生，那就說明數(shù)組已經(jīng)有序，則終止排序。

當數(shù)組本身就是有序的時候，只是遍歷了一次，沒有經(jīng)過交換就完成排序。時間負責度為O(n)。

function bubbing_2(arr) {for (let i = 0; i < arr.length; i++) {let count = 0;for (let j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {const temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;count++;}}if (count == 0) break;}console.log(arr); }bubbing_2(array);

第三次優(yōu)化

第三次優(yōu)化的思路是從數(shù)組的兩頭分別進行冒泡操作，假如要從小到大排序。那正向就是將最小的元素放到末尾，反向就是將最大的元素放到頭部。這種方案又稱為雞尾酒排序、來回排序

雞尾酒排序的方式并不會減少交換元素的次數(shù)，這點非常重要。它對性能的優(yōu)化在于某些情況下，遍歷的次數(shù)會減少。

例如：數(shù)組[2, 3, 4, 1]?，需要經(jīng)過4次外層遍歷才能有序。而用雞尾酒排序的思路，外層只需要一次即可。

function bubbing_3(arr) {const len = arr.length;const loop = Math.floor((len + 1) / 2);// 既然每次都將兩個元素排列到對的地方，// 那外層的遍歷次數(shù)就可以減少為原來的一半for (let i = 0; i < loop; i++) {let count = 0;for (let j = i + 1; j < len - 1; j++) {if (arr[j] > arr[j + 1]) {const temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;count++;}}for (let k = len - i - 1; k > 0; k--) {if (arr[k] < arr[k - 1]) {const temp = arr[k];arr[k] = arr[k - 1];arr[k - 1] = temp;count++;}}if (count == 0) break;}console.log(arr); } bubbing_3(array);

思考

冒泡排序是最基礎(chǔ)的排序方式了，和交換排序、插入排序一樣，思路簡單，容易掌握。所以我一開始把冒泡排序?qū)懗山粨Q排序，尷尬！

思考的問題有兩點：

在雞尾酒排序的方案中，仔細思考到底是哪里提升性能的時候，走了一個誤區(qū)。以為交換次數(shù)會變少，其實不是。

雞尾酒排序方案開始外層寫的是循環(huán)到n結(jié)束，后來想到是從兩頭開始排序的，一次兩個，豈不是可以減少外層次數(shù)，然后想了一下果然可以。（其實前面三段代碼中外層的n都可以寫成n - 1）

總結(jié)

以上是生活随笔為你收集整理的冒泡排序时间复杂度计算和优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。