冒泡排序

2016年05月19日

概述

• 重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
• 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

步骤

• 走n-1次，两两相比，当次当前的比较元素的索引最大值为未被比较元素（未冒泡）的索引-1
• 每次从第一个元素开始进行两两比较。如果当前元素比下一个元素大，就交换他们两个，接下来有下一个元素与自己的下一个元素进行两两比较。
• 当次最后的元素是本轮比较结果中最大的数，已冒好泡，下次无需理会。
• 重复对未冒泡好的左区进行冒泡处理
• 每轮比较结束后 ，已冒泡元素新增一个

代码实现

Python 冒泡排序

def sort_mp_py(v_list):
    for i in range(len(v_list)-1):
        for j in range(len(v_list)-i-1):
            if v_list[j] > v_list[j+1]:
                v_list[j],v_list[j+1] = v_list[j+1],v_list[j]
    return v_list

C冒泡排序

void sort_mp_c (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) 
        for (j=0; j<len-1-i; j++) { 
            if (arr[j] > arr[j+1]) {  
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

性能分析

时间复杂度

平均时间复杂度为O(n^2)

算法稳定性

• 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
• 如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

算法

阅读全文