数据结构之九种排序算法代码实现及相应排序的特点总结_数据结构排序特点

一.插入排序

1.直接插入排序：

特点：
这种排序在序列基本有序的情况下效率最好。
在插入排序中我都是用了数组第一个位置做了所谓的哨兵，剩下的数据才是真正用来比较的部分。

2.折半插入排序

特点：仅仅是在直接插入的基础上优化了一下寻找插入位置的算法，采用了折半查找，需要知道的的是无论是什么情况下最后插入的位置都是high+1的位置。

3.希尔排序

特点：关于希尔排序的过程，另一篇文章有写：https://blog.csdn.net/weixin_44142774/article/details/105738120。
需要注意的是它的时间复杂度是未被计算出来的。而且它是不稳定的算法。

二、交换排序

1.冒泡排序

特点：
（1）也和直接插入排序一样，在序列基本有序时效率最好。而且是稳定的排序算法。
（2）每次排序后都会将一个最大或最小的值的位置确定好。

2.快速排序：

特点：
（1）每一次的快速排序都会确定一个元素的最终位置。
（2）经历一次快排，小于枢轴的元素会被移动到左边，大于枢轴的元素会被移动到右边。
（3）这种排序是不稳定的，例如序列3 2 2‘ ，选择3作为枢轴，则会得到2‘ 2 3，从而使相等的两个元素调换了位置。这种情况有出现在：①开始排序前枢轴的右端区间有两个相等的元素且值小于枢轴②开始排序前枢轴的左端区间有两个相等的元素且值大于枢轴。
（4）这种排序在序列基本有序时的效率最不好，在一般情况下效率是最好的，时间复杂度为（nlog2n）。用到了递归所以需要栈。
（5）每次排序后都会将一个值的位置确定好，但不是最值的位置而是中间值的位置。

三、选择排序

1.简单选择排序

特点：
（1）每次排序后都会将一个最大或最小的值的位置确定好。
（2）简单选择排序的效率跟序列的初始状态无关。
（3）这种排序方式是不稳定的。例如序列：2 2’ 1，开始排序后需要将2与1的位置交换，得到1 2’ 2从而破坏了稳定性。

2.堆排序

特点：
（1）堆排序调整大根堆的算法是很巧妙的，在每一次的调整中双亲的变化是确定的所以把值写入，至于要调整的值最后放在哪里在调整过程中是不确定的，有可能在孩子中也有可能在孙子中，所以在跳出循环后再将要调整的 值写入恰当的位置。
（2）堆排序的算法是不稳定的，例如序列1 2’ 2，在初始建堆的过程中会变为2’ 1 2，在最后输出交换的过程中2’又放在了最后面即2 1 2’，所以是不稳定的。
（3）堆排序也会在每一次排序后确定一个最值元素的最终位置。

四、归并排序

特点：
（1）如图是二路归并排序，我们知道在K路归并排序中归并趟数m与元素数n的关系为：m=logk（n）取上界。
（2）每一趟比较的时间复杂度为O（n）乘以趟数即为总的时间复杂度。
（3）归并排序是稳定的，因为在序列合并时当两个值相等时先并入在前面的那个值。

五、基数排序

特点：
（1）唯一一个不基于比较和移动的内部排序方式
（2）基数排序是稳定的。
（3）基数排序的时间复杂度也是不依赖于序列的初始状态的，同简单选择排序是一样的。

六、代码实现如下：

#include "stdio.h"
#include "malloc.h"
void InsertSort (int *a,int n)
{
	int i,j;
	for (i=2;i<=n;i++)
	{
		a[0]=a[i];
		for (j=i-1;a[0]<a[j];j--)
			a[j+1]=a[j];
		a[j+1]=a[0];	
	}
}
void MidSort(int *a,int n)
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		a[0]=a[i];
		int low=1;
		int high=i-1;
		int mid;
		while(low<=high)
			{
				mid=(low+high)/2;
				if(a[0]<a[mid])
				{
					high=mid-1;
				}
				else
				{	
					low=mid+1;
				}
				for(j=i-1;j>high+1;j--)
				{
					a[j+1]=a[j];
				}
				a[high+1]=a[0];
			}
	
	}

}
void ShellSort(int *a,int n)
{
	int dk;
	int i,j;
	for(dk=n/2;dk>=1;dk=dk/2)
	{
		for(i=1+dk;i<=n;i++)
		{
			a[0]=a[i];
			for(j=i-dk;j>0&&a[0]<a[j];j=j-dk)
			{
				a[j+dk]=a[j];
			}
			a[j+dk]=a[0];
		}
	}
}
void SwapSort(int *b,int n)
{
	int i,j;
	int flag;
	int swap;
	for (i=0;i<n-1;i++)
	{
		flag=0;
		for (j=n-1;j>i;j--)
		{
			if (b[j-1]>b[j])
			{
				swap=b[j-1];
				b[j-1]=b[j];
				b[j]=swap;
				flag=1;	
			}	
		}
		if(flag==0)
			return;
		
	}
}
int Divide(int *b,int low ,int high)
{
	int pivode;
	pivode=b[low];
	while(low < high)
	{
		while((low < high) && (b[high]>=pivode))
			high--;
		b[low]=b[high];
		while((low < high) && (b[low]<=pivode))
                        low++;
                b[high]=b[low];
	}
	b[low]=pivode;
	return low;
}
void QuickSort(int *b,int low,int high)
{
	if (low < high)
	{
		int divident;
		divident = Divide(b,low,high);
		QuickSort(b,low,divident-1);
		QuickSort(b,divident+1,high);
	}
}
void SelectSort(int *b,int n)
{
	int i,j,min,swap;
	for (i=0;i<n-1;i++)
	{
		min = i;
		for (j=i+1;j<n;j++)
		{
			if(b[j]<b[min])
			min=j;	
		}
		if(min!=i)
		{
			swap=b[min];
			b[min]=b[i];
			b[i]=b[min];
		}

	}
}
void HeadAdjust(int *a,int k,int len)
{
	int i,j;
	a[0]=a[k];
	for (i=2*k;i<=len;i*=2)
	{
		if((i<len)&&(a[i]<a[i+1]))
		{
			i++;
		}
		if(a[0]>=a[i])
			break;
		else
		{
			a[k]=a[i];
			k=i;
		}
	}
	a[k]=a[0];
}
void HeapCreate(int *a,int len)
{
	int i;
	for(i=len/2;i>0;i--)
	{
		HeadAdjust(a,i,len);
	}

}
void HeapSort(int *a,int len)
{
	int i;
	int swap;
	HeapCreate(a,len);
	for(i=len;i>1;i--)
	{
		swap=a[i];
		a[i]=a[1];
		a[1]=swap;
		HeadAdjust(a,1,i-1);
	}
}
void Merge(int *b,int low,int mid,int high)
{
	int *c=(int*)malloc((11)*sizeof(int));
	int i,j,k;
	for(k=low;k<=high;k++)
	{
		c[k]=b[k];
	}
	for(i=low,j=mid+1,k=i;(i<=mid) && (j<=high);k++)
	{
		if(c[i]<=c[j])
		{
			b[k]=c[i];
			i++;
		}
		else
		{
			b[k]=c[j];
			j++;
		}
	}
	if(i<=mid)
	{
		b[k++]=c[i++];
	}
	if(j<=high)
	{
		b[k++]=c[j++];
	}
	free(c);
}
void MergeSort(int *b,int low,int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		MergeSort(b,low,mid);
		MergeSort(b,mid+1,high);
		Merge(b,low,mid,high);
	}
}
int main(int argc,char *argv[])
{
	int a[11];
	int b[10];
        int i;
	for(i=1;i<=10;i++)
	{
	a[i]=argv[1][i-1]-'0';
	}	
	for(i=0;i<10;i++)
        {
        b[i]=argv[1][i]-'0';
        }
	printf("array a is:\n");
	for (i=1;i<=10;i++)
        {
        printf("%d",a[i]);
        }
	printf("\n");
        printf("array b is:\n");
        for (i=0;i<10;i++)
        {
        printf("%d",b[i]);
        }
        printf("\n");
        InsertSort(a,10);
	printf("InsertSort a is:\n");
        for (i=1;i<=10;i++)
	{
	printf("%d",a[i]);
	}
	printf("\n");
	MidSort(a,10);
	printf("MidSort a is:\n");
	for (i=1;i<=10;i++)
        {
        printf("%d",a[i]);
        }
        printf("\n");
	ShellSort(a,10);
	printf("ShellSort a is:\n");
	for (i=1;i<=10;i++)
        {
        printf("%d",a[i]);
        }
        printf("\n");
	SwapSort(b,10);
	printf("SwapSort b is:\n");
	for (i=0;i<10;i++)
        {
        printf("%d",b[i]);
        }
        printf("\n");
	QuickSort(b,0,9);
	printf("QuickSort b is:\n");
        for (i=0;i<10;i++)
        {
        printf("%d",b[i]);
        }
        printf("\n");
	SelectSort(b,10);
	printf("SelectSort b is:\n");
        for (i=0;i<10;i++)
        {
        printf("%d",b[i]);
        }
        printf("\n");
	HeapSort(a,10);
        printf("HeapSort a is:\n");
        for (i=1;i<=10;i++)
        {
        printf("%d",a[i]);
        }
        printf("\n");
	MergeSort(b,0,10);
        printf("MergeSort b is:\n");
        for (i=0;i<10;i++)
        {
        printf("%d",b[i]);
        }
        printf("\n");


}



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

七：代码运行结果：