首页 > 代码库 > 冒泡排序(起泡排序)原理和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语言实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。