及时终止的冒泡排序

及时终止的冒泡排序 

(

当然了，现在还在写冒泡排序有点让人脸红，但是冒泡排序好多面试都问，而且好久没写博文了，还是写一个吧。各位看官轻拍。

下面代码写的不错，尤其是通过标记来判断是否已经排序成功，可以及时终止，提高了性能。

当然了，如果冒泡排序的算法决定了它的整体性能不如其他优秀的排序算法。在数据量比较大的情况下，

不能选用冒泡排序。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int onepass(int a[],int n)
{
    int i ;
    int interchanges = 0;
    int temp;
    for(i = 0;i<n-1;i++)
    {
        if(a[i] > a[i+1])
    {
            temp = a[i];
     a[i] = a[i+1],
     a[i+1] = temp;
     interchanges = 1;
        }
     }
     return interchanges;
}

void bubblesort(int a[],int n)
{
    int i;
    for(i = 0;i<n-1;i++)
    {
             if(!onepass(a,n-i))
        break;
    }
}

int test_bubblesort()
{
    int i = 0;
    int array[10];

    srand(time(NULL));
    for(i = 0;i<10;i++)
    {
     array[i] = rand()%1000;
     printf("array[%d] = %d\n",i,array[i]);
    }

    bubblesort(array,10);
    printf("--------------after sort----------\n");
    for(i = 0;i<10;i++)
    {
        printf("array[%d] = %d\n",i,array[i]);
    }
    return 0;
}
int main()
{
    test_bubblesort();
    return 0;
}

运行结果如下

root@libin:~/program/C/bubblesort# ./test

array[0] = 722

array[1] = 3

array[2] = 445

array[3] = 614

array[4] = 331

array[5] = 785

array[6] = 936

array[7] = 916

array[8] = 27

array[9] = 477

--------------after sort----------

array[0] = 3

array[1] = 27

array[2] = 331

array[3] = 445

array[4] = 477

array[5] = 614

array[6] = 722

array[7] = 785

array[8] = 916

array[9] = 936

参考文献：UNIX系统编程 Kay A. Robbins ,Steven Robbins.

我的更多文章