冒泡排序时间复杂度上为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
而从时间运行角度来说:正序情况下最快,乱序排中,逆序情况下最慢