首页 > 代码库 > 冒泡排序(起泡排序)原理和C语言实现

冒泡排序(起泡排序)原理和C语言实现

对于刚接触排序的童鞋来说,冒泡排序应该是第一堂课:

(虽然这种排序非常耗时)

冒泡排序的原理:

  我们这里假定是从小到大排列(从大到小也是一样的)

  冒泡排序的过程很简单。首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换之,然后比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行比较为止。

  由此可知,我们需要遍历的次数为n-1次,而每一次遍历所需要比较的数字是逐渐减少的,又有什么规律呢?

  我们每一次将最大的数字“沉底”,所以从后向前是有序的,第一次排序过后最后一个数是有序的,依次类推,第i次排序只需要比较到第n-i个数即可,有如下式子:

    for(j=0;j<n-i-i;j++){if....}

贴上代码如下:

 1 void bubble_sort(int *arr, int arr_len) 2 { 3     int i,j; 4     int temp; 5     for(i=0;i<arr_len-1;i++){ 6         for(j=0;j<arr_len-i-1;j++){ 7             if(arr[j]>arr[j+1]){ 8                 temp=arr[j]; 9                 arr[j]=arr[j+1];10                 arr[j+1]=temp;11             }12         }13     }14 }

这个是常规的冒泡排序,实际上我们可以从两边进行

第一遍从左向右遍历,第二遍从右向左遍历,第三遍再从左向右遍历,依次类推:

 

  1 # include <stdio.h>  2 # include <stdlib.h>  3 # include <string.h>  4 # include <time.h>  5 /*  6 void bubble_sort(int *arr, int arr_len)  7 {  8     int i;  9     int left=-1,right=arr_len; 10     while(left<right){ 11         for(i=left+1;i<right-1;i++){ 12             if(arr[i]>arr[i+1]){ 13                 int temp=arr[i]; 14                 arr[i]=arr[i+1]; 15                 arr[i+1]=temp; 16             } 17         } 18         right--; 19         for(i=right-1;i>left+1;i--){ 20             if(arr[i]<arr[i-1]){ 21                 int temp=arr[i]; 22                 arr[i]=arr[i-1]; 23                 arr[i-1]=temp; 24             } 25         } 26         left++; 27     } 28 } 29 */ 30 void bubble_sort(int *arr, int arr_len) 31 { 32     int left=-1,right=arr_len; 33     int i; 34     int temp; 35     while(left<right){ 36         i=left+1; 37         while(left<right&&i<right-1){ 38             if(arr[i]>arr[i+1]){ 39                 temp=arr[i]; 40                 arr[i]=arr[i+1]; 41                 arr[i+1]=temp; 42             } 43             i++; 44         } 45         right--; 46         i=right-1; 47         while(left<right&&i>left+1){ 48             if(arr[i]<arr[i-1]){ 49                 temp=arr[i]; 50                 arr[i]=arr[i-1]; 51                 arr[i-1]=temp; 52             } 53             i--; 54         } 55         left++; 56     } 57 } 58  59 void bubble_sort_normal(int *arr, int arr_len) 60 { 61     int i,j; 62     int temp; 63     for(i=0;i<arr_len-1;i++){ 64         for(j=0;j<arr_len-i-1;j++){ 65             if(arr[j]>arr[j+1]){ 66                 temp=arr[j]; 67                 arr[j]=arr[j+1]; 68                 arr[j+1]=temp; 69             } 70         } 71     } 72 } 73  74 int main(void) 75 { 76     double getTime; 77     clock_t start,finish; 78     srand(time(NULL)); 79     int arr_len; 80     int *arr; 81     int *arr_normal; 82     while(printf("Give me the length of array.\n"),scanf("%d",&arr_len)==1){ 83         if((NULL==(arr=(int *)malloc(sizeof(int)*arr_len)))){ 84             printf("Malloc ERROR!!\n"); 85         } 86         if((NULL==(arr_normal=(int *)malloc(sizeof(int)*arr_len)))){ 87             printf("Malloc to arr_normal ERROR\n"); 88         } 89         int i; 90         for(i=0;i<arr_len;i++){ 91             arr_normal[i]=arr[i]=rand()%100; 92         } 93         start=clock(); 94         /* 95         printf("Show time!!!!!\n"); 96         for(i=0;i<arr_len;i++){ 97             printf("%d\t",arr[i]); 98         } 99         printf("\n");100         */101         bubble_sort(arr, arr_len);102         /*103         for(i=0;i<arr_len;i++){104             printf("%d\t",arr[i]);105         }106         printf("\n");107         */108         finish=clock();109         getTime=(double)(finish-start)/CLOCKS_PER_SEC;110         printf("The time is %fs\n",getTime);111         start=clock();112         bubble_sort_normal(arr_normal, arr_len);113         finish=clock();114         getTime=(double)(finish-start)/CLOCKS_PER_SEC;115         printf("The normal time is %fs\n",getTime);116         printf("Once again?(y/n):\n");117         char ch;118         scanf("%*c%c",&ch);119         if(ch==y&&ch!=n){120             continue;121         }122         break;123     }124     return 0;

 

两种方法的时间比较:机器(acer4752G i5-2430)系统 :debian wheezy  编译器:gcc

Give me the length of array.
100000
The time is 35.520000s
The normal time is 44.210000s
Once again?(y/n):

第二种方法虽然因为比较的次数较第一次少,但是方法是相同的 ,所以处于同一数量级上。

冒泡排序(起泡排序)原理和C语言实现