八大排序(C语言)_c加加序列长度怎么算

冒泡排序：

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个；
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
3）针对所有的元素重复以上的步骤，除了最后一个；
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

选择排序：

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
3）重复第二步，直到所有元素均排序完毕。

直接插入排序：

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤：
1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置(相同则插入相等元素后边)。

希尔排序(递减增量排序算法)：

核心思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
1）选择一个增量序列d[1]，t[2]，…，d[k]，其中d[i]>d[j]，d[k]=1；
2）按增量序列个数k，对序列进行k 趟排序；
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

堆排序：

利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

1）创建一个堆H[0…n-1]

2）把堆首（最大值）和堆尾互换

3）把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4） 重复步骤2，直到堆的尺寸为1

快速排序：

分而治之。通过排序将序列分割为两部分，左边都是比基线条件小的数，右边都是比它大的数；然后再按照这个方法对分割后的两个序列排序。

归并排序：

1）将需要排序的序列两两划分进行第一次组内排序；

2）将第一步排好的组再次两两组合进行组内排序；

3）重复以上步骤，直至最后一次排序完成；

基数排序：

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

1.算法排序的时间复杂度:

时间复杂度o(n^2)
冒泡排序，选择排序，插入排序
时间复杂度o(n*logn)
归并排序，快速排序，堆排序，希尔排序
时间复杂度o(n)
基数排序

2.算法排序的空间复杂度

o(1)
冒泡排序，选择排序，插入排序，堆排序，希尔排序
o(nlogn)
快速排序
o(N)
归并排序
o(M)
基数排序

3.稳定性：相同值的元素排序前和排序后值保持不变

稳定的排序算法：冒泡排序，插入排序，归并排序，基数排序；
不稳定的排序算法：选择排序，快速排序，堆排序，希尔排序；

4.不稳定原因

选择排序原因：在选择最小值和位置为0的数交换的时候产生；
快速排序原因：在随机选择相同值中间的数的，两边的相同值的不不是被划分到选择值得左边就是选择值的右边；
堆排序原因：在每次建立大根堆后，堆顶元素会换到最后的位置上去；
希尔排序：步长为2时，第二个1跳两部，造成了不稳定；

5.源码

详情见代码注释

/***********************************************************

Create date:2019.10.8
Designer by:MaL
Compiling environment:Microsoft Visual Studio2012

************************************************************/

#include "sort.h"
#include <assert.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#include <math.h>

void Swap(int *a, int *b)
{
	int c = *a;
	*a = *b;
	*b = c;
}

void Show(int *arr, int len)
{
	for (int i = 0; i < len; ++i)
	{
		printf("%d  ", arr[i]);
	}

	printf("\n");
}

// 冒泡
// O(n^2)   O(1)    稳定 
void BubbleSort(int *arr, int len)
{
	for (int i = 0; i < len - 1; ++i)
	{
		int flag = 0;
		for (int j = 0; j < len - 1 - i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

// 选择
// O(n^2)   O(1)    不稳定
void SelectSort(int *arr, int len)
{
	for (int i = 0; i < len - 1; ++i)
	{
		int min = i;
		for (int j = i + 1; j < len; ++j)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}

		Swap(&arr[i], &arr[min]);
	}
}

//直接插入排序   数据越趋于有序，其效率越高
// O(n^2)     O(1)    稳定
//  最坏 O(n^2)   最好 O(n)
void InsertSort(int *arr, int len)
{
	for (int i = 1; i < len; ++i)
	{
		int tmp = arr[i];
		int j = 0;
		for (j = i - 1; j >= 0; --j)
		{
			if (arr[j] > tmp)
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
		}

		arr[j + 1] = tmp;
	}
}

static void Shell2(int *arr, int len, int d)
{
	for (int k = 0; k < d; ++k)
	{
		for (int i = d + k; i < len; i += d)
		{
			int tmp = arr[i];
			int j = i - d;
			for (; j >= 0; j -= d)
			{
				if (arr[j] > tmp)
				{
					arr[j + d] = arr[j];
				}
				else
				{
					break;
				}
			}

			arr[j + d] = tmp;
		}
	}
}
static void Shell(int *arr, int len, int d)
{
	for (int i = d; i < len; ++i)
	{
		int tmp = arr[i];
		int j = i - d;
		for (; j >= 0; j -= d)
		{
			if (arr[j] > tmp)
			{
				arr[j + d] = arr[j];
			}
			else
			{
				break;
			}
		}

		arr[j + d] = tmp;
	}
}

//希尔排序
//  O(n ^1.3~1.5)   O(1)    不稳定  
void ShellSort(int *arr, int len)
{
	// 目前并没有一个合适的固定分组
	//  分组的值需要两两互质，并且最后一个分组必须为1
	int d[] = { 5, 3, 1 };
	for (int i = 0; i < sizeof(d) / sizeof(d[0]); ++i)
	{
		Shell(arr, len, d[i]);
	}
}

//  O(logn)
static void OneAdjust(int *arr, int len, int root)
{
	int i = root;
	int tmp = arr[i];
	int j = 2 * i + 1; //   left
	while (j < len)
	{
		if (j + 1 < len && arr[j] < arr[j + 1])
		{
			j = j + 1; 
		}
		//  j 就是左右孩子中较大的哪一个
		if (arr[j] > tmp)
		{
			arr[i] = arr[j];
			i = j;  //  下一个子树的根
			j = 2 * i + 1; //  下一个子树的左孩子
		}
		else
		{
			break;
		}
	}

	arr[i] = tmp;
}

//  O(nlogn) 
static void CreateHeap(int *arr, int len)
{
	int root = len / 2 - 1;
	for (; root >= 0; --root)
	{
		OneAdjust(arr, len, root);  // O(logn)
	}
}

//堆排序
//  O(nlogn)     O(1)      不稳定
void HeapSort(int *arr, int len)
{
	CreateHeap(arr, len);  //  O(nlogn)

	for (int i = 0; i < len - 1; ++i)  // O(n)
	{
		Swap(&arr[0], &arr[len - 1 - i]);

		OneAdjust(arr, len - i - 1, 0);  //  O(logn)
	}
}

// O(n)
static  int  OneQuick(int *arr, int i,  int j)
{
	int tmp = arr[i];

	while (i < j)   //   保证找的整个过程  i  < j
	{
		while (i < j)   //  从后向前找比tmp小的元素  保证  i < j
		{
			if (arr[j] < tmp) break;
			j--;
		}

		arr[i] = arr[j];   //   当找到比tmp小的元素后，将j位置的值存储到i位置

		while (i < j)  //  从前向后找比tmp大的元素  保证  i < j
		{
			if (arr[i] > tmp) break;
			i++;
		}

		arr[j] = arr[i];  //   当找到比tmp大的元素后，将i位置的值存储到j位置
	}

	arr[i] = tmp;   //   i之前的数据都比tmp小， 之后的数据都比tmp大

	return i;
}

// O(nlogn)     O(logn)      不稳定
static void Quick(int *arr, int left, int right)
{
	// O(n)
	int mod = OneQuick(arr, left, right);

	if (mod - left > 1)   //  i左边剩余的数据是否超过1个
	{
		Quick(arr, left, mod - 1);
	}
	if (right - mod > 1)  // i右边剩余的数据是否超过1个
	{
		Quick(arr, mod + 1, right);
	}
}

//  
static void  ForQuick(int *arr, int left, int right)
{
	Stack st;
	int size = (int)(log10((double)(right - left + 1)) / log10((double)2));
	size = (size + 1) * sizeof(int) * 2;
	st.data = (int *)malloc(size);
	assert(st.data != NULL);
	st.top = 0;

	st.data[st.top++] = left;
	st.data[st.top++] = right;

	while (st.top != 0)
	{
		right = st.data[--st.top];
		left = st.data[--st.top];

		int mod = OneQuick(arr, left, right);

		if (mod - left > 1)
		{
			st.data[st.top++] = left;
			st.data[st.top++] = mod - 1;
		}
		if (right - mod > 1)
		{
			st.data[st.top++] = mod + 1;
			st.data[st.top++] = right;
		}
	}

	free(st.data);
}

//快速排序
void QuickSort(int *arr, int len)
{
	ForQuick(arr, 0, len - 1);
}

// O(n)
static void Meger(int *arr, int len,  int width, int *brr)
{
	int L1 = 0;
	int H1 = L1 + width - 1;
	int L2 = H1 + 1;
	int H2 = L2 + width - 1 < len - 1 ? L2 + width - 1 : len - 1;
	int num = 0;

	while (L1 < len && L2 < len)
	{
		while (L1 <= H1 && L2 <= H2)
		{
			if (arr[L1] < arr[L2])
			{
				brr[num++] = arr[L1++];
			}
			else
			{
				brr[num++] = arr[L2++];
			}
		}

		while (L1 <= H1)
		{
			brr[num++] = arr[L1++];
		}

		while (L2 <= H2)
		{
			brr[num++] = arr[L2++];
		}

		L1 = H2 + 1;
		H1 = L1 + width - 1 < len - 1 ? L1 + width - 1 : len - 1;
		L2 = H1 + 1;
		H2 = L2 + width - 1 < len - 1 ? L2 + width - 1 : len - 1;
	}

	while (L1 <= H1)
	{
		brr[num++] = arr[L1++];
	}

	for (int i = 0; i < len; ++i)
	{
		arr[i] = brr[i];
	}
}

//归并排序
// O(nlogn)    O(n)     稳定
void MegerSort(int *arr, int len)
{
	int *brr = (int *)malloc(sizeof(int)* len);

	for (int i = 1; i < len; i *= 2)
	{
		Meger(arr, len, i, brr);   // O(n)
	}

	free(brr);
}

//  求数组中最大数字的宽度
static int  GetMaxWidth(int *arr, int len)
{
	int max = arr[0];
	for (int i = 0; i < len; ++i)
	{
		if (arr[i] > max)  max = arr[i];
	}

	int width = 0;
	while (max)  //  12
	{
		width++;
		max /= 10;
	}

	return width;
}

//  求data的倒数第i+1位上的值
static int GetNumOfWidth(int data, int i)
{
	while (i)
	{
		data /= 10;
		i--;
	}

	return data % 10;
}

// O(d * n)      O(k + n)     稳定
// 基数排序      不需要比较的排序
void RadixSort(int *arr, int len)
{
	/* 
	    1、创建队列
		2、先求最大数字的位数
		3、求出相应位数的值， 并根据位数值将其存储相应的队列中
		4、按顺序输出所有队列中的值，  循环处理3,4步，循环次数由第一步算出
	*/

	Que que[10];
	for (int i = 0; i < 10; ++i)
	{
		que[i].data = (int*)malloc(sizeof(int)* len);
		assert(que[i].data != NULL);
		que[i].head = que[i].tail = 0;
	}

	int width = GetMaxWidth(arr, len); // O(n)

	for (int i = 0; i < width; ++i)  // O(d * n)
	{
		//  将数组中所有的数字取其相应位数的值，并将其存储到相应的队列中
		for (int j = 0; j < len; ++j)
		{
			int  num = GetNumOfWidth(arr[j], i);
			que[num].data[que[num].tail++] = arr[j];
		}

		int k = 0;
		for (int m = 0; m < 10; ++m)
		{
			while (que[m].head != que[m].tail)
			{
				arr[k++] = que[m].data[que[m].head++];
			}
		}

		for (int n = 0; n < 10; ++n)
		{
			que[n].head = que[n].tail = 0;
		}
	}

	for (int i = 0; i < 10; ++i)
	{
		free(que[i].data);
	}
}
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
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441