排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void bubble(int a[],int length ){
    for (int j = 0;j < length - 1;j++){    //外循环表示循环趟数
    	for (int i = 0;i < length - 1;i++){  //内循环：从a[0]开始比较
        	int MiddleExample;
        	if (a[i]>a[i+1]){
            	MiddleExample =a [i];
            	a[i] =a [i+1];
            	a[i+1] = MiddleExample;//利用中间变量交换下标顺序  
        	}
    	}
    }   
}

// example
int main (){
    int a []={3,9,5,6,7,45,36,88};
    int length = sizeof(a)/sizeof(a[0]);
    bubble(a,length);
    for (int i = 0;i<length;i++){
        printf("%d\n",a[i]);//遍历a[]  
    }return 0;
}

这里的时间复杂度可以很简单的得出为O(n²)，但同样对于冒泡算法还有可改进的地方，

若定义数组：

1
int a []={7,8,9,1,2,3,4,5,6}

我们按照最开始给出的算法不难发现需要循环9趟，但是发现在第一个数字7排好之后，后面根本就没有做排序了，所以我们可以给出一个判断条件是其跳出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>


void bubble(int a[],int length);
// example
int main (){
    int a []={7,8,9,1,2,3,4,5,6};
    int length = sizeof(a)/sizeof(a[0]);
    for (int i = 0;i<length;i++){
        printf("%d ",a[i]);//遍历a[]  
    }
    printf("\n");
    bubble(a,length) ;
    system("pause");
    return 0;
}
void bubble(int a[],int length ){
    for (int j = 0;j < length - 1;j++){    //外循环表示循环趟数
        int temp = 0; // 给出变量作为判断是否需要跳出循环
    	for (int i = 0;i < length - 1;i++){  //内循环：从a[0]开始比较
        	int MiddleExample;
        	if (a[i]>a[i+1]){
            	MiddleExample =a [i];
            	a[i] =a [i+1];
            	a[i+1] = MiddleExample;//利用中间变量交换下标顺序 
                temp = 1;
            }
    	}
        if (temp == 0){
            break;
        }
        for (int i = 0;i<length;i++){
        printf("%d ",a[i]);//遍历a[]  , 输出每一趟排序结果
        }
        printf("\n");
    }   
}

实现.