排序算法对比和代码实现

排序比较

如图:

C代码实现:

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
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <io.h>
#include <math.h>
#include <time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAX_LENGTH_INSERT_SORT 7 /* 用于快速排序时判断是否选用插入排序阙值 */
typedef int Status;
#define MAXSIZE 10000 /* 用于要排序数组个数最大值,可根据需要修改 */
typedef struct
{
int r[MAXSIZE+1]; /* 用于存储要排序数组, r[0]用作哨兵或临时变量 */
int length; /* 用于记录顺序表的长度 */
} SqList;
/* 交换 L 中数组 r 的下标为 i 和 j 的值 */
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void print(SqList L)
{
int i;
for(i=1; i<L.length; i++)
printf("%d,",L.r[i]);
printf("%d",L.r[i]);
printf("\n");
}
/* 对顺序表 L 作交换排序(冒泡排序初级版) */
void BubbleSort0(SqList *L)
{
int i,j;
for(i=1; i<L->length; i++)
{
for(j=i+1; j<=L->length; j++)
{
if(L->r[i]>L->r[j])
{
swap(L,i,j);/* 交换 L->r[i]与 L->r[j]的值 */
}
}
}
}
/* 对顺序表 L 作冒泡排序 */
void BubbleSort(SqList *L)
{
int i,j;
for(i=1; i<L->length; i++)
{
for(j=L->length-1; j>=i; j--) /* 注意 j 是从后往前循环 */
{
if(L->r[j]>L->r[j+1]) /* 若前者大于后者(注意这里与上一算法的差异) */
{
swap(L,j,j+1);/* 交换 L->r[j]与 L->r[j+1]的值 */
}
}
}
}
/* 对顺序表 L 作改进冒泡算法 */
void BubbleSort2(SqList *L)
{
int i,j;
Status flag=TRUE; /* flag 用来作为标记 */
for(i=1; i<L->length && flag; i++) /* 若 flag 为 true 说明有过数据交换,否则停止循环 */
{
flag=FALSE; /* 初始为 False */
for(j=L->length-1; j>=i; j--)
{
if(L->r[j]>L->r[j+1])
{
swap(L,j,j+1); /* 交换 L->r[j]与 L->r[j+1]的值 */
flag=TRUE; /* 如果有数据交换,则 flag 为 true */
}
}
}
}
/* 对顺序表 L 作简单选择排序 */
void SelectSort(SqList *L)
{
int i,j,min;
for(i=1; i<L->length; i++)
{
min = i; /* 将当前下标定义为最小值下标 */
for (j = i+1; j<=L->length; j++) /* 循环之后的数据 */
{
if (L->r[min]>L->r[j]) /* 如果有小于当前最小值的关键字 */
min = j; /* 将此关键字的下标赋值给 min */
}
if(i!=min) /* 若 min 不等于 i,说明找到最小值,交换 */
swap(L,i,min); /* 交换 L->r[i]与 L->r[min]的值 */
}
}
/* 对顺序表 L 作直接插入排序 */
void InsertSort(SqList *L)
{
int i,j;
for(i=2; i<=L->length; i++)
{
if (L->r[i]<L->r[i-1]) /* 需将 L->r[i]插入有序子表 */
{
L->r[0]=L->r[i]; /* 设置哨兵 */
for(j=i-1; L->r[j]>L->r[0]; j--)
L->r[j+1]=L->r[j]; /* 记录后移 */
L->r[j+1]=L->r[0]; /* 插入到正确位置 */
}
}
}


/* 对顺序表 L 作希尔排序 */
void ShellSort(SqList *L)
{
int i,j,k=0;
int increment=L->length;
do
{
increment=increment/3+1;/* 增量序列 */
for(i=increment+1; i<=L->length; i++)
{
if (L->r[i]<L->r[i-increment])/* 需将 L->r[i]插入有序增量子表 */
{
L->r[0]=L->r[i]; /* 暂存在 L->r[0] */
for(j=i-increment; j>0 && L->r[0]<L->r[j]; j-=increment)
L->r[j+increment]=L->r[j]; /* 记录后移,查找插入位置 */
L->r[j+increment]=L->r[0]; /* 插入 */
}
}
printf(" 第%d 趟排序结果: ",++k);
print(*L);
}
while(increment>1);
}


/* 堆排序********************************** */
/* 已知 L->r[s..m]中记录的关键字除 L->r[s]之外均满足堆的定义, */
/* 本函数调整 L->r[s]的关键字,使 L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L,int s,int m)
{
int temp,j;
temp=L->r[s];
for(j=2*s; j<=m; j*=2) /* 沿关键字较大的孩子结点向下筛选 */
{
if(j<m && L->r[j]<L->r[j+1])
++j; /* j 为关键字中较大的记录的下标 */
if(temp>=L->r[j])
break; /* rc 应插入在位置 s 上 */
L->r[s]=L->r[j];
s=j;
}
L->r[s]=temp; /* 插入 */
}
/* 对顺序表 L 进行堆排序 */
void HeapSort(SqList *L)
{
int i;
for(i=L->length/2; i>0; i--) /* 把 L 中的 r 构建成一个大根堆 */
HeapAdjust(L,i,L->length);
for(i=L->length; i>1; i--)
{
swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
HeapAdjust(L,1,i-1); /* 将 L->r[1..i-1]重新调整为大根堆 */
}
}

/* **************************************** */
/* 归并排序********************************** */
/* 将有序的 SR[i..m]和 SR[m+1..n]归并为有序的 TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
int j,k,l;
for(j=m+1,k=i; i<=m && j<=n; k++) /* 将 SR 中记录由小到大地并入 TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if(i<=m)
{
for(l=0; l<=m-i; l++)
TR[k+l]=SR[i+l]; /* 将剩余的 SR[i..m]复制到 TR */
}
if(j<=n)
{
for(l=0; l<=n-j; l++)
TR[k+l]=SR[j+l]; /* 将剩余的 SR[j..n]复制到 TR */
}
}

/* 递归法 */
/* 将 SR[s..t]归并排序为 TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{
int m;
int TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; /* 将 SR[s..t]平分为 SR[s..m]和 SR[m+1..t] */
MSort(SR,TR2,s,m); /* 递归地将 SR[s..m]归并为有序的 TR2[s..m] */
MSort(SR,TR2,m+1,t); /* 递归地将 SR[m+1..t]归并为有序的 TR2[m+1..t] */
Merge(TR2,TR1,s,m,t); /* 将 TR2[s..m]和 TR2[m+1..t]归并到 TR1[s..t] */
}
}
/* 对顺序表 L 作归并排序 */
void MergeSort(SqList *L)
{
MSort(L->r,L->r,1,L->length);
}
/* 非递归法 */
/* 将 SR[]中相邻长度为 s 的子序列两两归并到 TR[] */
void MergePass(int SR[],int TR[],int s,int n)
{
int i=1;
int j;
while(i <= n-2*s+1)
{
/* 两两归并 */
Merge(SR,TR,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i<n-s+1) /* 归并最后两个序列 */
Merge(SR,TR,i,i+s-1,n);
else /* 若最后只剩下单个子序列 */
for(j =i; j <= n; j++)
TR[j] = SR[j];
}
/* 对顺序表 L 作归并非递归排序 */
void MergeSort2(SqList *L)
{
int* TR=(int*)malloc(L->length * sizeof(int));/* 申请额外空间 */
int k=1;
while(k<L->length)
{
MergePass(L->r,TR,k,L->length);
k=2*k;/* 子序列长度加倍 */
MergePass(TR,L->r,k,L->length);
k=2*k;/* 子序列长度加倍 */
}
}
/* **************************************** */
/* 快速排序******************************** */
/* 交换顺序表 L 中子表的记录,使枢轴记录到位,并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
while(low<high) /* 从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
}
return low; /* 返回枢轴所在位置 */
}
/* 对顺序表 L 中的子序列 L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /* 将 L->r[low..high]一分为二,算出枢轴值 pivot */
QSort(L,low,pivot-1); /* 对低子表递归排序 */
QSort(L,pivot+1,high); /* 对高子表递归排序 */
}
}
/* 对顺序表 L 作快速排序 */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}

/* **************************************** */
/* 改进后快速排序******************************** */
/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{
int pivotkey;
int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */
if (L->r[low]>L->r[high])
swap(L,low,high); /* 交换左端与右端数据,保证左端较小 */
if (L->r[m]>L->r[high])
swap(L,high,m); /* 交换中间与右端数据,保证中间较小 */
if (L->r[m]>L->r[low])
swap(L,m,low); /* 交换中间与左端数据,保证左端较小 */
pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
L->r[0]=pivotkey; /* 将枢轴关键字备份到 L->r[0] */
while(low<high) /* 从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
L->r[low]=L->r[high];
while(low<high&&L->r[low]<=pivotkey)
low++;
L->r[high]=L->r[low];
} L
->r[low]=L->r[0];
return low; /* 返回枢轴所在位置 */
}
void QSort1(SqList *L,int low,int high)
{
int pivot;
if((high-low)>MAX_LENGTH_INSERT_SORT)
{
while(low<high)
{
pivot=Partition1(L,low,high); /* 将 L->r[low..high]一分为二,算出枢轴值 pivot */
QSort1(L,low,pivot-1); /* 对低子表递归排序 */
/* QSort(L,pivot+1,high); /* 对高子表递归排序 */
low=pivot+1; /* 尾递归 */
}
}
else
InsertSort(L);
}
/* 对顺序表 L 作快速排序 */
void QuickSort1(SqList *L)
{
QSort1(L,1,L->length);
}
/* **************************************** */
#define N 9
int main()
{

int i;
/* int d[N]={9,1,5,8,3,7,4,6,2}; */
int d[N]= {50,10,90,30,70,40,80,60,20};
/* int d[N]={9,8,7,6,5,4,3,2,1}; */
SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
for(i=0; i<N; i++)
l0.r[i+1]=d[i];
l0.length=N;
l1=l2=l3=l4=l5=l6=l7=l8=l9=l10=l0;
printf("排序前:\n");
print(l0);
printf("初级冒泡排序:\n");
BubbleSort0(&l0);
print(l0);
printf("冒泡排序:\n");
BubbleSort(&l1);
print(l1);
printf("改进冒泡排序:\n");
BubbleSort2(&l2);
print(l2);
printf("选择排序:\n");
SelectSort(&l3);
print(l3);
printf("直接插入排序:\n");
InsertSort(&l4);
print(l4);
printf("希尔排序:\n");
ShellSort(&l5);
print(l5);
printf("堆排序:\n");
HeapSort(&l6);
print(l6);
printf("归并排序(递归) :\n");
MergeSort(&l7);
print(l7);
printf("归并排序(非递归) :\n");
MergeSort2(&l8);
print(l8);
printf("快速排序:\n");
QuickSort(&l9);
print(l9);
printf("改进快速排序:\n");
QuickSort1(&l10);
print(l10);
/*大数据排序*/
/*
srand(time(0));
int Max=10000;
int d[10000];
int i;
SqList l0;
for(i=0;i<Max;i++)
d[i]=rand()%Max+1;
for(i=0;i<Max;i++)
l0.r[i+1]=d[i];
l0.length=Max;
MergeSort(l0);
print(l0);
*/
return 0;
}