算法导论笔记 -- Step 4 [冒泡排序]

**转载请注明**

轮到最熟悉的bubble-sort了。

原理：
    每次比较相邻两数字，把这两个数进行排序，一轮后最大的到末尾。下一轮选出次大的。。。


C++代码：

#include <iostream>

using namespace std;

void BUBBLE_SORT( int*, int, int );

int main(){
    int a[] = {5,2,4,6,1,3};

    BUBBLE_SORT(a, 0, sizeof(a)/sizeof(int));

    for (int i = 0; i < sizeof(a)/sizeof(int); i++){
        cout << a[i] << endl;
    }
    return 0;
}

void BUBBLE_SORT( int* array, int start, int len ){
    for ( int i = 1; i <= len - 1; i++ ){
        for ( int j = start; j < start + len - 1 ; j++ ){
            if ( array[j] > array[j+1] ){
                array[j] = array[j] - array[j+1];    //写了一个不需要额外内存的交换
                array[j+1] = array[j+1]+array[j];
                array[j] = array[j+1]-array[j];
            }
        }
    }
}

空间复杂度：
    O（1）

时间复杂度：
    O（n^2)