运行结果正确
还是快速排序难一些。
完整代码
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
|
#include<stdio.h>#include <stdlib.h>#include <string.h>#include<malloc.h>void swap(int *a,int *b);void select_sort(int arr[],int n);void tra_arr(int arr[],int n);void insert_sort(int arr[],int n); void shell_sort(int arr[],int n);void perc_down(int arr[],int i,int n);void heap_sort(int arr[],int n);void merge(int arr[],int temp_arr[],int left_start,int right_start ,int right_end);void m_sort(int arr[],int temp_arr[],int left,int right);void merge_sort(int arr[],int n);int get_pri(int arr[],int left,int right);void q_sort(int arr[],int left,int right);void quick_sort(int arr[],int n);int main(){ int arr[100]={ 10,9,8,7,6,5,4,3,2,1 }; select_sort(arr,10); printf("\n简单选择排序结果\n"); tra_arr(arr,10); int arr1[100]={ 10,9,8,7,6,5,4,3,2,1 }; insert_sort(arr1,10); printf("\n插入排序结果\n"); tra_arr(arr1,10); int arr2[100]={ 10,9,8,7,6,5,4,3,2,1 }; shell_sort(arr2,10); printf("\n希尔排序结果\n"); tra_arr(arr2,10); int arr3[100]={ 10,9,8,7,6,5,4,3,2,1 }; heap_sort(arr3,10); printf("\n堆排序结果\n"); tra_arr(arr3,10); int arr4[100]={ 10,9,8,7,6,5,4,3,2,1 }; merge_sort(arr4,10); printf("\n归并排序结果\n"); tra_arr(arr4,10); int arr5[100]={ 10,9,8,7,6,5,4,3,2,1 }; quick_sort(arr5,10); printf("\n快速排序结果\n"); tra_arr(arr5,10); return 0;}void swap(int *a,int *b){ //在函数内部，如果打算接收的是指针的地址，那就不要加*, //如果想要的是值，那就加*,我也很讨厌指针，但是没办法 int t=*a; *a=*b; *b=t;}//简单选择排序 void select_sort(int arr[],int n){ int min; //这个过程一时半会讲不清楚，看书会清楚一些 for(int i=0;i<n;i++){ min=i; for(int j=i+1;j<n;j++){ if(arr[i]>arr[j]){ min=j; } } //经过上面的里层for，就找到了最小的元素的下表 swap(&arr[i],&arr[min]) ; } }//插入排序void insert_sort(int arr[],int n){ int temp,j; for(int i=1;i<n;i++){ temp=arr[i]; for(j=i;j>0&&arr[j-1]>temp;j--){ //后挪 arr[j]=arr[j-1]; } //现在就找到空出来的插入位置了 arr[j]=temp; }} //希尔排序void shell_sort(int arr[],int n){ int in,i,j,temp; //本来这个排序是很好理解的，就是这个外层的循环 //故弄玄虚，你就把他理解成一个简单的，递减的数组就行 //而且这个2的指数递减的序列的时间复杂度是很坏的 //最好使用SED或者HIB序列会好很多,这里只是演示 //两个里层的for就是插入排序,仔细看看就能看懂 for(in=n/2;in>0;in=in/2){ for(i=in;i<n;i++){ temp=arr[i]; for(j=i;j>=in;j=j-in){ if(arr[j-in]>temp){ //后挪 arr[j]=arr[j-in]; } else{ //arr[j-in]<temp，说明找到了 break; } } //上面执行完，肯定找到了插入位置 arr[j]=temp; } } } //首先是下滤操作//i是根，n是heap的规模 //这里的下滤针对最大堆 void perc_down(int arr[],int i,int n){ int child,temp; //仔细想想，其实和插入排序差不多 //首先把i取出来，把i在堆里面所在的位置空出来 //这里和原来建堆的下滤又不一样，这里没有设置哨兵 for(temp=arr[i];(2*i+1)<n;i=child){ child=2*i+1; //如果当前儿子不是最后一个，说明还有右儿子 //两者取最大 if(child!=(n-1)&&arr[child]<arr[child+1]){ child++; } if(temp<arr[child]){ arr[i]=arr[child]; } else{ //当前取出来的值终于大于两个儿子时。 break; } } //上面轮完之后，肯定找到了一个儿子比我们取出来的值还要小的 arr[i]=temp; } void heap_sort(int arr[],int n){ int i; //建堆 for(i=n/2;i>=0;i--){ perc_down(arr,i,n); } //取最大值放在最后已经舍弃的位置上，下滤剩下的堆 for(i=n-1;i>0;i--){ //取最大值放在最后已经舍弃的位置上 swap(&arr[0],&arr[i]); // 滤剩下的堆 perc_down(arr,0,i); }}//归并排序//第一步，写一个将两个已经排好序列的归并void merge(int arr[],int temp_arr[],int left_start,int right_start ,int right_end){ int i,temp_start,elem_num,left_end; temp_start=left_start; left_end=right_start-1; elem_num=right_end-left_start+1; //归并的核心 while(left_start<=left_end&&right_start<=right_end){ if(arr[left_start]<=arr[right_start]){ temp_arr[temp_start++]=arr[left_start++]; } else{ temp_arr[temp_start++]=arr[right_start++]; } } while(left_start<=left_end){ temp_arr[temp_start++]=arr[left_start++]; } while(right_start<=right_end){ temp_arr[temp_start++]=arr[right_start++]; } //重新拷回去，记住，这里归并的只是原来数组的一部分，所以不能从头开始 for(i=0;i<elem_num;i++,right_end--) { arr[right_end]=temp_arr[right_end]; }} //第二步，递归调用归并，将数组不断分割void m_sort(int arr[],int temp_arr[],int left,int right){ //tra_arr(arr,10); int center; //递归结束条件 if(left<right){ center=(right+left)/2; m_sort(arr,temp_arr,left,center); m_sort(arr,temp_arr,center+1,right); merge(arr,temp_arr,left,center+1,right); } } //第三步，初始化临时数组void merge_sort(int arr[],int n){ int *temp_arr; temp_arr=(int*)malloc(n*sizeof(int)); m_sort(arr,temp_arr,0,n-1); free(temp_arr);} //快速排序//首先，实现三数中值分割法,取一个“裁判” （中值） int get_pri(int arr[],int left,int right){ int center=(left+right)/2; if(arr[left]>arr[center]){ swap(&arr[left],&arr[center]); } if(arr[left]>arr[right]){ swap(&arr[left],&arr[right]); } if(arr[center]>arr[right]){ swap(&arr[center],&arr[right]); } //把中值扔到倒数第二个，因为上述操作已经让倒数第一大于中值了 swap(&arr[center],&arr[right-1]); return arr[right-1]; } //其次，实现分而治之void q_sort(int arr[],int left,int right){ int i,j,pri; //如果规模已经小于三了，就不要再分而治之了，没得分了 if(right-left>=3){ //取中值 pri= get_pri(arr,left,right); //取左右往中间靠拢的两个指针i,j i=left; j=right-1; //开始判断 while(1){ //如果当前i对应的值小于裁判，继续推进 while(arr[++i]<pri); // 如果当前i对应的值大于裁判，继续推进 while(arr[--j]>pri); //上面走完，肯定碰到硬杈了，在i和j没有错位的情况下 //交换 if(i<j){ swap(&arr[i],&arr[j]); } else{ break; } } swap(&arr[i],&arr[right-1]); //这个i的作用远不止此,这个i还记录了上一个裁判的位置 //开始对分下来的两个部分进行同样的操作 q_sort(arr,left,i-1); q_sort(arr,i+1,right); } //如果递归到规模已经无法再分了 //就用普通的方法排序 else{ /*这里稍微讲一下 数组和指针实际上是一样的东西 到这里了，那肯定就剩一个或者两个元素了 所以数组的开头变成left所指的位置，现在left所在位置的下标 就是0，所以后面的n也要相应变化*/ insert_sort(arr+left,right-left+1); } } //最后包装一下void quick_sort(int arr[],int n){ q_sort(arr,0,n-1);} //遍历数组void tra_arr(int arr[],int n){ for(int i=0;i<n;i++){ printf("%d ",arr[i]); } printf("\n");} |
以上就是C语言所有经典排序方法的实现代码的详细内容，更多关于C语言排序方法的的资料请关注服务器之家其它相关文章！
原文链接：https://blog.csdn.net/jiangjun_feng/article/details/117404323
