排序算法 - 冒泡排序(Bubble Sort)

by LauCyun Aug 7,2014 20:10:00 6,504 views

核心:冒泡,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。如图1所示。

图1 Bubble Sort

所以,冒泡排序算法的运作如下:

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

 

1 算法实现

伪代码

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

C++

#include<iostream>

using namespace std;
const int N = 8;
using ElemType = int;

void BubbleSort(ElemType *array);
void Show(ElemType *array);

void BubbleSort(ElemType *array) {
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                ElemType temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        // cout << "i = " << i << " => ";
        // Show(array);
    }
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

int main() {
    ElemType array[N] = {6, 5, 3, 1, 8, 7, 2, 4};
    Show(array);
    BubbleSort(array);
    Show(array);
    return 0;
}

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def bubbleSort(alist):
    list_len = alist.__len__()
    for i in range(0, list_len):
        print('| i = %s =>' % i, alist)
        for j in range(1, list_len - i):
            if alist[j - 1] > alist[j]:
                alist[j - 1], alist[j] = alist[j], alist[j - 1]
    return alist


unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
print(bubbleSort(unsorted_list))

 

2 算法过程演示

如果显示效果不佳,请戳 这里

 

3 复杂度分析

平均情况与最坏情况均为 \(O(n^2)\),使用了 temp 作为临时交换变量,空间复杂度为\( O(1)\)

 

4 参考文档

(全文完)

Tags