排序算法:冒泡排序

icy2003 程序 2020-05-04 18:47:57 103 0条

冒泡排序(Bubble Sort)由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”

640.gif

算法评价

  • 平均时间复杂度:O(n^2)
  • 最好情况:O(n)
  • 最坏情况:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

算法思想

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

实例分析

以数组 arr = [5, 1, 4, 2, 8] 为例说明,加粗的数字表示每次循环要比较的两个数字:

第一次外循环

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), 5 > 1 交换位置
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 交换位置
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 交换位置
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 5 < 8 位置不变

第二次外循环(除开最后一个元素8,对剩余的序列)

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 1 < 4 位置不变
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 交换位置
( 1 2 4 5 8 ) → ( 1 2 4 5 8 ), 4 < 5 位置不变

第三次外循环(除开已经排序好的最后两个元素,可以注意到上面的数组其实已经排序完成,但是程序本身并不知道,所以还要进行后续的循环,直到剩余的序列为 1)

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

第四次外循环(最后一次)

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

代码示例

Javascript

function bubbleSort(array) {
    var length = array.length,
        i,
        j,
        temp;
    for (i = length - 1; 0 < i; i--) {
        for (j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。