1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 /*
  5 排序算法集合
  6 排序算法一般分成非比较排序和比较排序
  7 这里的比较非比较不是指是否有数字的比较,而是是否直接对比较的数字操作
  8 */
  9 
 10 //显示数组
 11 void show(int arr[],int size);
 12 /*=====非比较排序=======*/
 13 //计数排序
 14 void counting_sort(int arr[],int size);
 15 //基数排序
 16 void radix_sort(int arr[],int size);
 17 //桶排序
 18 void bucket_sort(int arr[],int size);
 19 /*======比较排序=======*/
 20 //冒泡排序
 21 void bubble_sort(int arr[],int size);
 22 //插入排序
 23 void insertion_sort(int arr[],int size);
 24 //选择排序
 25 void selection_sort(int arr[],int size);
 26 //归并排序
 27 void merge_sort(int arr[],int size);
 28 //快速排序
 29 void quick_sort(int arr[],int size);
 30 //堆排序
 31 void heap_sort(int arr[],int size);
 32 //希尔排序
 33 void shell_sort(int arr[],int size);
 34 //void _sort(int arr[],int size);
 35 
 36 //获取数组中的最大的元素
 37 int maxof(int arr[],int size);
 38 
 39 //交换数组中的第i与第j个元素
 40 void swap(int arr[],int i,int j);
 41 
 42 /*==========主函数===========*/
 43 int main(){
 44     int a[]={1,3,5,6,4,2,8,9,7,0};
 45     int size=sizeof(a)/sizeof(int);
 46     merge_sort(a,size);
 47     show(a,size);
 48     return 0;
 49 }
 50 
 51 /*=====非比较排序======
 52 特点:少数数据有优势,占用空间,不适合给大量的数据进行排序
 53 下面三种的时间复杂度都是O(n)
 54 1.比较排序
 55     通过记录比各个元素小的元素的个数来进行排序,
 56     因为比较的作用只是用于计数,所以不属于比较排序
 57 2.基数排序
 58     读音跟计数排序差不多,但是原理是不一样的
 59     算法是通过给从各位开始的每个数位进行排序,
 60     来达到依次有序的目的
 61 3.桶排序
 62     通过将给定的数列的每个元素放到对应的位置来进行排序
 63     理论上排序效率优于任何的比较排序算法,
 64     但是由于需要开辟的储存空间过大,所以并不是很实用
 65 */
 66 //自创的排序方法,实际上是比较排序的另一种实现
 67 //自创的排序方法,非比较排序,时间复杂度为n^n
 68 void my_sort(int arr[],int size){//arr[]是源数组,size是数组的大小
 69     int temp[size],count[size];//count数组用于计数
 70     int i,j;//i,j为循环变量
 71     memset(count,0,sizeof(int)*size);//初始化count数组,其值为0
 72     for(i=0;i<size;i++){
 73         for(j=0;j<size;j++)
 74             //如果当前遍历的数比指定的数小,指定的位置权加1
 75             if(arr[j]<arr[i]) count[i]++;
 76     }
 77     for(i=0;i<size;i++)
 78         temp[count[i]]=arr[i];
 79     for(i=0;i<size;i++)
 80         arr[i]=temp[i];
 81 }
 82 
 83 //计数排序
 84 void counting_sort(int arr[],int size){
 85     int max=maxof(arr,size);
 86     int count[max+1],temp[size];
 87     memset(count,0,sizeof(int)*(max+1));
 88 //  memset(temp,0,sizeof(int)*(size));
 89     int i;
 90     for(i=0;i<size;i++)
 91         count[arr[i]]++;
 92     for(i=1;i<=max;i++)
 93         count[i]+=count[i-1];
 94     for(i=size-1;i>=0;i--)
 95         temp[--count[arr[i]]]=arr[i];
 96     for(i=0;i<size;i++)
 97         arr[i]=temp[i];
 98 }
 99 
100 //基数排序
101 void radix_sort(int arr[],int size){
102     int i,index,lsd=1,max=maxof(arr,size);
103     int count[10],temp[size];
104     while(max/lsd>0){
105         memset(count,0,sizeof(int)*10);
106         for(i=0;i<size;i++){
107             index=arr[i]/lsd%10;
108             count[index]++;
109         }
110         for(i=1;i<10;i++)
111             count[i]+=count[i-1];
112         for(i=size-1;i>=0;i--){
113             index=arr[i]/lsd%10;
114             index=--count[index];
115             temp[index]=arr[i];
116         }
117         for(i=0;i<10;i++)
118             arr[i]=temp[i];
119         lsd*=10;//进位
120     }
121 }
122 
123 //桶排序
124 void bucket_sort(int arr[],int size){
125     int max=maxof(arr,size);
126     int *bucket=(int *)malloc(sizeof(int)*(max+1));//创建一个可以存入数组中所有数字的"大桶"
127     memset(bucket,0,sizeof(int)*(max+1));//初始化大桶
128     int i,j;
129     for(i=0;i<size;i++) bucket[arr[i]]++;//将数组中的数字当成下标进行储存
130     for(i=j=0;i<=max;i++)
131         while(bucket[i]--) arr[j++]=i; //将有权重的桶的下标存入原数组
132 }
133 
134 /*======比较排序=======
135 1.冒泡排序
136     比较前后元素的大小,达到将最大的元素浮到最后的目的.稳定排序
137 2.选择排序
138     每次都将获得的当前状态的最小的元素放置到最前面,不稳定排序
139 3.插入排序
140     分组,将分组中的最小的元素放置逐元素移动到前面,直到遇到比它小的元素,稳定排序
141 4.归并排序
142     利用分治思想,稳定排序
143 5.堆排序
144     利用大根堆排序,不稳定排序
145 6.快速排序
146     每次找准一个数的位置,利用分治依次把所有的值的位置都确定,不稳定排序
147 7.希尔排序
148     可以看成插入排序的一种改进,不过速度很快,不稳定排序
149 */
150 
151 //冒泡排序
152 void bubble_sort(int arr[],int size){
153     int i,j,flag,tmp;
154     for(i=1;i<size;i++){
155         flag=1;
156         for(j=0;j<size-1;j++){
157             if(arr[j]>arr[j+1]){//交换arr[j]与arr[j+1]
158                 tmp=arr[j];
159                 arr[j]=arr[j+1];
160                 arr[j+1]=tmp;
161                 flag=0;//匹配标志位
162             }
163         }
164         if(flag) return;//判断是否已经完成排序
165     }
166 }
167 
168 //选择排序
169 void selection_sort(int arr[],int size){
170     int i,j,min,tmp;
171     for(i=0;i<size-1;i++){
172         min=i;
173         for(j=i+1;j<size;j++){
174             if(arr[j]<arr[min]) min=j;
175         }
176         if(min!=i){//交换min和i元素
177             tmp=arr[min];
178             arr[min]=arr[i];
179             arr[i]=tmp;
180         }
181     }
182 }
183 
184 //插入排序
185 void insertion_sort(int arr[],int size){
186     int i,j,temp;
187     for(i=1;i<size;i++){
188         temp=arr[i];
189         for(j=i-1;j>=0&&arr[j]>temp;j--){//将a[i]向前推进
190             arr[j+1]=arr[j];
191         }
192         arr[j+1]=temp;
193     }
194 }
195 
196 //归并排序,算法的思想值得借鉴
197 void merge_sort(int arr[],int size){
198     int step,left_min,left_max,right_min,right_max,next;
199     int *tmp=(int *)malloc(sizeof(int)*size);
200     if(tmp==NULL){
201         fputs("Something is wrong!\n",stderr);
202         abort();
203     }
204     for(step=1;step<size;step*=2){
205         for(left_min=0;left_min<size-1;left_min=right_max){
206             right_min=left_max=left_min+step;
207             right_max=left_max+step;
208             if(right_max>size) right_max=size;
209             next=0;
210             while(left_min<left_max&&right_min<right_max)//向缓存数组中存放数字
211                 tmp[next++]=arr[left_min]<arr[right_min]?arr[left_min++]:arr[right_min++];
212             while(left_min<left_max) tmp[next++]=arr[left_min++];
213             while(right_min<right_max) tmp[next++]=arr[right_min++];
214             while(next>0)    arr[--right_min]=tmp[--next];
215         }
216     }
217     free(tmp);
218 }
219 
220 //堆排序
221 void heap_sort(int arr[],int size){
222     int i;
223     for(i=(size-1)/2;i>=0;i--){
224         maxHeapify(arr,i,size);
225     }
226     for(i=size-1;i>0;i--){
227         swap(arr,0,i);
228         maxHeapify(arr,0,i);
229     }
230 
231 }
232 
233 //====堆调整
234 void maxHeapify(int arr[],int i,int size){
235     int left=i*2+1;//左子树
236     int right=i*2+2;//右子树
237     int large=i;
238     //选择左右子树中值较大的一个
239     if(left<size&&arr[left]>arr[large]) large=left;
240     if(right<size&&arr[right]>arr[large]) large=right;
241     if(i!=large){
242         swap(arr,i,large);
243         maxHeapify(arr,large,size);
244     }
245 }
246 
247 
248 //快速排序,这里我们使用非递归模式
249 void quick_sort(int arr[],int size){
250     int left=0,right=size,top=-1;
251     int *stack=(int*)malloc(sizeof(int)*size*2);//指定stack空间的大小
252     stack[++top]=left;
253     stack[++top]=right;
254     while(~top){//非空栈(即top!=-1)时循环
255         right=stack[top--];
256         left=stack[top--];
257         int i=left;
258         int j=right;
259         int key=arr[left];
260         while(i<j){
261             while(i<j&&arr[j]>=key) j--;
262             arr[i]=arr[j];
263             while(i<j&&arr[i]<=key) i++;
264             arr[j]=arr[i];
265         }
266         arr[i]=key;
267         if(left<i-1){
268             stack[++top]=left;
269             stack[++top]=i-1;
270         }
271         if(i+1<right){
272             stack[++top]=i+1;
273             stack[++top]=right;
274         }
275     }
276 }
277 
278 //希尔排序
279 void shell_sort(int arr[],int size){
280     int i,j,k,d,temp;
281     for(d=size/2;d>0;d/=2){
282         for(j=d;j<size;j++){
283             temp=arr[j];
284             for(k=j-d;k>=0&&arr[k]>temp;k-=d)//向前推进
285                 arr[k+d]=arr[k];
286             arr[k+d]=temp;
287         }
288     }
289 }
290 
291 //用于显示数组
292 void show(int a[],int size){
293     int i;
294     for(i=1;i<=size;i++){
295         printf("%d\t",a[i-1]);
296         if(i%10==0) puts("");
297     }
298     if((i-1)%10) puts("");
299 }
300 
301 //获得数组中的最大值
302 int maxof(int arr[],int size){
303     if(size<=0) return -1;
304     int max=arr[size-1];
305     while(--size) if(max<arr[size]) max=arr[size];
306     return max;
307 }
308 
309 //交换arr数组中的第i个和第j个元素
310 void swap(int arr[],int i,int j){
311     int tmp=arr[i];
312     arr[i]=arr[j];
313     arr[j]=tmp;
314 }