1 #include <stdio.h>
2 #include <stdlib.h>
3
4 void quickSort(int a[],int left,int right)
5 {
6 if(a==NULL||left>=right)
7 return;
8
9 ////////////////////////////////////
10 int m=(left+right)/2;
11 int t;
12 t=a[m];
13 a[m]=a[right];
14 a[right]=a[m];
15 ///////////////////////////////////////
16 int i=left,j=right-1,pivot=a[right],tmp;
17
18 while(i<=j)
19 {
20 while(a[i]<pivot) i++;
21 while(a[j]>pivot) j--;
22 if(i<=j) // <=
23 {
24 tmp=a[i];
25 a[i]=a[j];
26 a[j]=tmp;
27 i++;
28 j--;
29 }
30 }
31 tmp=a[right];
32 a[right]=a[i];
33 a[i]=tmp;
34
35 quickSort(a,left,i-1);
36 quickSort(a,i+1,right);
37 }
38
39
40 void insertSort(int a[],int n)
41 {
42 int i,j,minIndex,tmp;
43 for(i=0; i<n-1; ++i)
44 {
45 minIndex=i;
46 for(j=i+1; j<n; ++j)
47 {
48 if(a[minIndex]>a[j])
49 {
50 minIndex=j;
51 }
52 }
53 tmp=a[i];
54 a[i]=a[minIndex];
55 a[minIndex]=tmp;
56 }
57 }
58
59 void shellSort(int a[],int n)
60 {
61 int k,i,j,tmp;//k是增量(我经常说成是步长)
62 for(k=n/2; k>=1; k/=2)
63 {
64 for(i=k; i<n; ++i)
65 {
66 tmp=a[i];
67 for(j=i-k; j>=0&&a[j]>tmp; j-=k)
68 {
69 a[j+k]=a[j];
70 }
71 a[j+k]=tmp;
72 }
73 }
74 }
75
76 void bubbleSort(int a[],int n)
77 {
78 //bool flag=false; //我去，原来C语言里竟然没有bool类型,C++中有
79 int flag;
80 int i,j,tmp;
81 for(i=0; i<n-1; ++i)
82 {
83 //flag=false;
84 flag=0;
85 for(j=n-1; j>i; --j)
86 {
87 if(a[j]<a[j-1])
88 {
89 tmp=a[j];
90 a[j]=a[j-1];
91 a[j-1]=tmp;
92 //flag=true;
93 flag=1;
94 }
95 }
96 if(!flag) //本趟没有发生交换，则说明已经有序了
97 return;
98 }
99 }
100
101 //桶排序
102 void bucketSort(int a[],int n)
103 {
104 int b[11]= {0}; //初始化,假设数据范围是1-10
105 int i,j=0,value;
106 for(i=0; i<n; ++i)
107 {
108 value=a[i];
109 b[value]++;
110 }
111 for(i=0; i<11; ++i)
112 {
113 while(b[i]!=0)
114 {
115 a[j]=i;
116 j++;
117 b[i]--;
118 }
119 }
120 }
121
122 /*void swap(int *a,int *b){
123 int t;
124 t=*a;
125 *a=*b;
126 *b=t;
127 }*/
128
129 //归并排序
130 void mSort(int a[],int tmp[],int left,int right)
131 {
132 if(left<right)
133 {
134 int mid=(left+right)/2;
135 mSort(a,tmp,left,mid);
136 mSort(a,tmp,mid+1,right);
137 merge(a,tmp,left,mid+1,right);
138 }
139 }
140 void merge(int a[],int tmp[],int lstart,int rstart,int end)
141 {
142 int i,j,k;
143 i=lstart;
144 j=rstart;
145 k=lstart;
146 while(i<=rstart-1&&j<=end)
147 {
148 if(a[i]<a[j])
149 {
150 tmp[k++]=a[i++];
151 }
152 else
153 {
154 tmp[k++]=a[j++];
155 }
156 }
157 while(i<=rstart-1)
158 {
159 tmp[k++]=a[i++];
160 }
161 while(j<=end)
162 {
163 tmp[k++]=a[j++];
164 }
165
166 //把数据从临时数组中拷贝到原始数组中
167 for(i=lstart; i<=end; ++i)
168 {
169 a[i]=tmp[i];
170 }
171 }
172 void mergeSort(int a[],int n)
173 {
174 int *tmp;
175 tmp=malloc(n*sizeof(int));
176 if(tmp!=NULL)
177 {
178 mSort(a,tmp,0,n-1);
179 free(tmp);
180 }
181 }
182
183
184 int main()
185 {
186 int a[]= {6,2,7,1,1,1,5};
187 int i,n=sizeof(a)/sizeof(int);
188 //quickSort(a,0,n-1);
189 //insertSort(a,n);
190 //bubbleSort(a,n);
191 //bucketSort(a,n);
192 mergeSort(a,n);
193 for(i=0; i<n; i++)
194 {
195 printf("%d ",a[i]);
196 }
197
198 /*int b[]={0,1};
199 swap(&b[0],&b[1]);
200 printf("
%d%d",b[0],b[1]);*/
201 return 0;
202 }
