冒泡排序时间复杂度上为O(n^2)
冒泡排序三种方式，第一种也是最基本的排序：
void bubbleSort1(int *arr,int length){ int i,j,k; for(i=0;i<length;i++){ for(j=i+1;j<length;j++){ if(arr[i]>arr[j]){ k = arr[j]; arr[j] = arr[i]; arr[i] = k; } } } }
第二种是循环的时候，j指针从尾部开始，每次可以顺便排序其他的元素
void bubbleSort2(int *arr,int length){ int i,j,k; for(i=0;i<length;i++){ for(j=length-1;j>=i;j--){ if(arr[j] < arr[j-1]){ k = arr[j-1]; arr[j-1] = arr[j]; arr[j] = k; } } } }
第三种是加入一个标记为，如果一次遍历发现没有元素冒泡，那么立刻停止
void bubbleSort3(int *arr,int length){ int i,j,k; bool flag = true; for(i=0;i<length && flag; i++){ flag = false; for(j=i+1;j<length;j++){ if(arr[i] > arr[j]){ k = arr[j]; arr[j] = arr[i]; arr[i] = k; flag = true; } } } }
测试后发现，除了正序的极端情况下，第三种的冒泡排序快一些，其他情况下的冒泡排序都是原始的最简单的方法快。
乱序情况下：
正序情况下
逆序情况下：
全部代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 void copy(int *arr,int length); 5 void bubbleSort1(int *arr,int length); 6 void bubbleSort2(int *arr,int length); 7 void bubbleSort3(int *arr,int length); 8 void print(int *arr,int length); 9 //int arrtest[10] = {3,4,7,8,0,9,1,2,6,5}; 10 //int arrtest[10] = {0,1,2,3,4,5,6,7,8,9}; 11 int arrtest[10] = {9,8,7,6,5,4,3,2,1,0}; 12 int main(){ 13 int i; 14 clock_t start,end; 15 int Array[10]; 16 copy(Array,10); 17 print(Array,10); 18 printf("bubble 1:\n"); 19 start = clock(); 20 for(i=0;i<100000;i++){ 21 copy(Array,10); 22 //print(Array,10); 23 bubbleSort1(Array,10); 24 } 25 end = clock(); 26 print(Array,10); 27 printf("bubble 1 time: %d \n\n",end-start); 28 29 printf("bubble 2:\n"); 30 start = clock(); 31 for(i=0;i<100000;i++){ 32 copy(Array,10); 33 //print(Array,10); 34 bubbleSort2(Array,10); 35 } 36 end = clock(); 37 print(Array,10); 38 printf("bubble 2 time: %d \n\n",end-start); 39 40 printf("bubble 3:\n"); 41 start = clock(); 42 for(i=0;i<100000;i++){ 43 copy(Array,10); 44 //print(Array,10); 45 bubbleSort3(Array,10); 46 } 47 end = clock(); 48 print(Array,10); 49 printf("bubble 3 time: %d \n\n",end-start); 50 51 getchar(); 52 return 0; 53 } 54 void copy(int *arr,int length){ 55 int i; 56 for(i=0;i<length;i++){ 57 arr[i] = arrtest[i]; 58 } 59 } 60 void bubbleSort1(int *arr,int length){ 61 int i,j,k; 62 for(i=0;i<length;i++){ 63 for(j=i+1;j<length;j++){ 64 if(arr[i]>arr[j]){ 65 k = arr[j]; 66 arr[j] = arr[i]; 67 arr[i] = k; 68 } 69 } 70 } 71 } 72 void bubbleSort2(int *arr,int length){ 73 int i,j,k; 74 for(i=0;i<length;i++){ 75 for(j=length-1;j>=i;j--){ 76 if(arr[j] < arr[j-1]){ 77 k = arr[j-1]; 78 arr[j-1] = arr[j]; 79 arr[j] = k; 80 } 81 } 82 } 83 } 84 void bubbleSort3(int *arr,int length){ 85 int i,j,k; 86 bool flag = true; 87 for(i=0;i<length && flag; i++){ 88 flag = false; 89 for(j=i+1;j<length;j++){ 90 if(arr[i] > arr[j]){ 91 k = arr[j]; 92 arr[j] = arr[i]; 93 arr[i] = k; 94 flag = true; 95 } 96 } 97 } 98 } 99 void print(int *arr,int length){ 100 int i; 101 for(i=0;i<length;i++){ 102 printf("%d ",arr[i]); 103 } 104 printf("\n"); 105 }
最终可以看到：
冒泡排序方法1>2>3
而从时间运行角度来说：正序情况下最快，乱序排中，逆序情况下最慢
本文转自博客园xingoo的博客，原文链接：冒泡排序，如需转载请自行联系原博主。
