数据结构重读 – 冒泡排序

发现自己学的最水的一门就是本科的数据结构了,我现在连冒泡排序都写不出来,sign。。。从今天开始重读数据结构。

冒泡排序:

对于有N个数的数组:

(1) 第1趟从第1个开始,如果arr[j] >= arr[j+1],swap(arr[j], arr[j+1])。本趟的结果是将最“大”的放在最后的位置上。
(2)第2趟仍然从第1个开始,执行大则swap但只执行到n-1的位置上,即次大的放到n-1上。
以此类推……
注:可优化,如果某一轮没有任何swap,说明已经有序了,这个很直白不用解释了。

例子:

5  7  3  2  1
5  3  2  1  7
3  2  1  5  7
2  1  3  5  7
1  2  3  5  7

代码:

void bubble_sort(int* arr, int n) {
    int flag = 0;
    int i,j;
    for(i=0; i<n-1 ;i++) {
        flag = 0;
        for(j=0; j<n-1-i; j++) {
            if(arr[j]>=arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = 1;
            }
        }
        if(!flag) {
            break;
        }
    }
}

Leave a Reply

Your email address will not be published.