H面试程序（15）： 冒泡排序法

#include<stdio.h>#include<assert.h>void display(int * a, int n) {for(int i = 0; i < n; i++){printf("%d,",a[i]);}printf("\n");}void swap(int * a, int * b){int temp;temp = *a;*a = *b;*b = temp;}void bubble_sort(int * a, int n){    int i = 0;  int j ;  for(i = 0; i < n-1; i++ )  {  for( j = i; j <= n-1; j++ )  {  if(a[j] >=  a[i])  {  swap(&(a[j]), &(a[i]));  }  }  }}int main(){   int a[8] ={2, 1, 3, 4, 5, 7, 6, 8};int num = sizeof(a)/sizeof(int);printf("before_sort:");display(a, num);bubble_sort(a,num);printf("after_sort:");display(a, num);return 0;}

改进后：

#include <stdio.h>#include <time.h>//交换两个数据void swap(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;}//显示交换后的数组void display_array( int a[], int n ){    int i;    for( i = 0; i < n; i++ )        printf( "%d ", a[i] );}//冒泡排序void bubble_sort( int a[], int n ){int i ,j;int flag = 1;  //判断比较中是否发生了交换 1代表进行了交换for(i = 0; i<n-1 && flag; i++ )    //flag的作用：若上次排序没有发生交换，就说明数组已经是有序{                                  //这样做可以减少不必要的后续比较flag = 0;for(j = n -1; j >=i; j-- )  //第一次比较时 j是 0 ~ 7 第二次是  1 ~ 7{if(a[j] > a[j + 1]){swap(&(a[j]), &(a[j+1]));    flag = 1;}}}}int main(){    clock_t start, finish;    start = clock();    int  n = 8;    int a[] = { 2, 1, 3, 4, 5, 7, 6, 8 };    printf( "Before sorting: " );    display_array( a, n );    bubble_sort( a, n );    printf( "After sorting: " );    display_array( a, n );    finish = clock();    printf("\n本次计算一共耗时: %f秒\n\n", (double)(finish-start)/CLOCKS_PER_SEC);    return 0;}