C语言排序算法

 1 #include<stdio.h>
 2 #define N 10
 3 void swap(int *p1, int *p2);
 4 void BubbleSort(int *a);
 5 void SelectSort(int a[]);
 6 void QuickSort(int *a, int left, int right);
 7 int main(){
 8     int a[N] = {3,6,9,8,5,3,1,6,0,2};
 9     int i;
10     //SelectSort(a);
11     QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
12     for(i=0; i<N; i++){
13     printf("%d ", a[i]);
14     }
15     return 0;
16 }
17 
18 void swap(int *p1, int *p2){
19     int temp = *p1;
20     *p1 = *p2;
21     *p2 = temp;
22 }
23 void swap2(int a[], int i, int j)
24 {
25     int t = a[i];
26     a[i] = a[j];
27     a[j] = t;
28 }
29 void BubbleSort(int *a){
30 
31     int i,j;
32     for(i=0; i<N-1; i++){   /* 注意 N-1 */
33         for(j=0; j<N-1-i; j++){
34             if(a[j]>a[j+1])
35                 swap(&a[j],&a[j+1]);
36         }
37     }
38 
39 }
40 
41 void SelectSort(int a[]){
42     int i,j,min;
43 
44     for(i=0; i<N-1; i++){    /*一个n-1,下面n*/
45         min = i;
46         for(j=i+1; j<N; j++){
47             if(a[j]<a[min])
48                 min =j;
49         }
50         swap(&a[i],&a[min]);
51     }
52 }
53 
54 void QuickSort(int *a, int left, int right){
55     int key = a[left];
56     int i = left;
57     int j = right;
58 
59 
60     if(left >= right)
61         return ;
62 
63     while(i<j){
64         while(i<j && a[j]>=key){   /*a[j]>=key 如果只写> 会进入死循环*/
65             j--;
66         }
67         a[i] = a[j];
68         while(i<j && a[i]<=key){
69             i++;
70         }
71         a[j] = a[i];
72     }
73     a[i] = key;
74     QuickSort(a, left, i-1);
75     QuickSort(a, i+1, right);
76 }
77 
78 /*
79         最差时间分析 平均时间复杂度  稳定度 空间复杂度 
80 冒泡     O(n2)            O(n2)         稳定          O(1)
81 选择     O(n2)            O(n2)         稳定          O(1)
82 快速     O(n2)            O(n*log2n)    不稳定      O(log2n)~O(n)
83 */