C语言实现插入排序、希尔排序、直接排序、堆排序、冒泡排序、快速排序的三种方法、归并排序、非比较排序以及快速排序和归并排序的非递归实现方法_插入排序和堆排序c

插入排序的实现：

//插入排序：时间复杂度最大为o（N*N）；最小为o（N）；不稳定；
void insert(int* arr, int n)
{
	for (int i = 1; i < n; ++i)
	{
		int end = i - 1;
		//保存要插入的数据
		int data = arr[i];
		//如果插入的数据小于有序列的最后一个数，则将最后一个数向后移动；并让插入数据继续向前对比；
		while (end >= 0 && arr[end] >= data)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = data;
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	insert(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

希尔排序与插入排序原理相同，步长不同。

//希尔排序:时间复杂度o（N^1.3）;不稳定
void shell(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3+1;//定义每一次排序的两个数据之间的距离
		for (int i = gap; i < n; i++)
		{
			int end = i - gap;//有序数列中的最后一个数据
			int data = arr[i];
			while (end >= 0 && arr[end] > data)//若最后一个数据大于同组的另一个数据，则将最后一个数据放在另一个数据之后，并更新end的值
			{
				arr[end + gap] = arr[end];
				end = end - gap;
			}
			arr[end + gap] = data;//若最后一个数据小于同组数据，则将该数据插入到end+gap的位置
		}
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	shell(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

直接排序：

//直接排序,时间复杂度o（N*N），空间复杂度o（1），不稳定。
void swap(int* arr, int pos1, int pos2)
{
	int tmp = arr[pos1];
	arr[pos1] = arr[pos2];
	arr[pos2] = tmp;
}
void select(int* arr, int n)
{
	int start = 0;
	int end = n - 1;
	//每次将最小值放在起始位置，下次比较时不再比较已确定的最小值。
	while (start < end)
	{
		int min = start;
		int i;
		for (i=start+1; i < n; ++i)
		{
			if(arr[i] < arr[min])
			{
				min = i;
			}
		}
		int tmp = arr[start];
		arr[start] = arr[min];
		arr[min] = tmp;
		++start;
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	select(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

优化直接排序：同时得到最大值和最小值。

//优化直接排序
void swap(int* arr, int pos1, int pos2)//交换函数
{
	int tmp = arr[pos1];
	arr[pos1] = arr[pos2];
	arr[pos2] = tmp;
}
void Select(int* arr, int n)//优化后同时将最大值和最小值得到
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int min = start;
		int max = start;
		for (int i = start + 1; i <=end; i++)
		{
			if (arr[i] > arr[max])
			{
				max = i;
			}
			if (arr[i] < arr[min])
			{
				min = i;
			}
		}
		swap(arr, start, min);//得到最小值后将最小值放在最前面
			if (max == start)//若最大值就在第一个位置，则将其与最小值交换，否则会使最大值丢失
				max = min;
			swap(arr, end, max);//把最大值放在最后面
			start++;//排除第一个和最后一个数据继续进行排序
			end--;
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Select(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

堆排序

//堆排序,时间复杂度o（N*logN），空间复杂度o（1），不稳定
void shiftdown(int* arr, int n, int root)//若向下调整为最大堆，进行排序后数组数据排序方式为从小到大，若为最小堆，则排序方式为从大到小。
{
	int child = 2 * root + 1;//左孩
	while (child<n)
	{
		if (arr[child + 1] > arr[child] && child + 1 < n)
		{
			child++;//若右孩大于左孩且右孩没有超出数组范围，则将父节点与右孩比较；
		}
		if (arr[root] < arr[child])//调整为最大堆
		{
			int tmp = arr[root];//交换后继续从右孩处进行比较
			arr[root] = arr[child];
			arr[child] = tmp;
			root = child;
			child = 2 * root + 1;
		}
		else//若父节点比右孩大则结束循环
			break;
	}
}
void heap(int* arr, int n)
{
	for (int i = (n - 2) / 2;i >= 0; --i)//从最后一个非叶子结点开始向上调整，调整到根结点；每次调整都将该非叶子结点的结构变为最大堆，结束循环后该数组即为最大堆
	{
		shiftdown(arr, n, i);
	}
	int end = n - 1;//进行排序，每次将最大值放到数组最后一个位置，并在下次排序时不将该最大值考虑在内
	while (end > 0)
	{
		int tmp = arr[end];
		arr[end] = arr[0];
		arr[0] = tmp;
		shiftdown(arr, end, 0);
		--end;
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	heap(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

冒泡排序

//冒泡排序，时间复杂度o（N^2）,空间复杂度o(1),稳定。
void Bubble(int* arr, int n)
{
	int end = n;
	while (end > 1)//进行一次循环后，需要比较的数据就少一个。
	{
	int flag = 0;//判断是否进行了数据的交换，若没有则说明排序已完成，结束循环。
		for (int i = 0; i < end-1; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				int tmp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tmp;
				flag = 1;
			}
		}
		if(!flag)
		break;
		end--;
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Bubble(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

快速排序霍尔法：

//快速排序递归实现,hoare法，不稳定
int part1(int* arr, int left, int right)
{
	int mid = getMid(arr, left, right);//获取基准值的位置
	//把基准值放到起始位置
	int tmp = arr[left];
	arr[left] = arr[mid];
	arr[mid] = tmp;
	int idx = arr[left];
	int start = left;
	while (left < right)
	{
		while (left < right&&arr[right] >= idx)//从后往前找第一个小于基准值的数据
		{
			right--;
		}
		while (left < right&&arr[left] <= idx)//从前往后找第一个大于基准值的数据
		{
			left++;
		}
		int tmp = arr[right];//交换两个数据
		arr[right] = arr[left];
		arr[left] = tmp;
	}
	int x = arr[start];//结束时将left和right相遇的位置的数据和基准值交换,此时基准值左边的值都小于基准值，右边的值都大于基准值；
	arr[start] = arr[left];
	arr[left] = x;
	return left;//返回此时基准值所在的位置
}
void part(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int div = part1(arr, left, right);
	part(arr, left, div - 1);//[left,div-1)
	part(arr, div + 1, right);//(div+1,right]
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	part(arr, 0,n-1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

优化快速排序基准值获取方法

//快速排序优化,三数取中法确定基准值，起始位置，中间位置，结束位置;数据有序时，如果没有优化，可能会导致栈溢出，因为栈调用的层数约等于数据的个数，优化之后，划分比较均衡，时间复杂度为o（n*logn），栈的调用层数约等于logn；
//稳定性：不稳定
int getMid(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (arr[left] > arr[mid])
	{
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[left] > arr[right])
		{
			return right;
		}
		else
			return left;
	}
	else
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return right;
		}
		else
			return left;
	}
}
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

快速排序挖坑法

//快速排序挖坑法
int getmid(int* arr, int left, int right)
{
	int mid = left + (right + left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
			return right;
	}
}
int part2(int* arr, int left, int right)
{
	int mid = getmid(arr, left, right);
	int tmp = arr[mid];
	arr[mid] = arr[left];
	arr[left] = tmp;
	int key = arr[left];
	//从后往前找到第一个小于基准值的位置，将其值放在基准值的位置，此时该位置空了出来；再从前往后找到第一个大于基准值的位置，将其值放在上一步运行后空出来的位置上；
	while (left < right)
	{
		while (left < right&&arr[right] >= key)
		{
			right--;
		}
		arr[left] = arr[right];
		while (left < right&&arr[left] <= key)
		{
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = key;
	return left;//返回基准值所在的位置。
}
void part(int* arr, int left, int right)
{
	if (left >= right)
		return;
		//找到分割小于基准值和大于基准值的位置；并将左边小于基准值的所有值和右边大于基准值的所有值继续进行挖坑排序。
	int div = part2(arr, left, right);
	part(arr, left, div - 1);
	part(arr, div + 1, right);
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	part(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

快速排序前后指针法：

//快速排序前后指针法
int part3(int* arr, int left, int right)
{
	int prev = left;//上一个小于基准值的位置
	int cur = left+1;//下一个小于基准值的位置
	int key = arr[left];
	while (cur <= right)
	//若cur位置的值大于基准值，则cur向后移动；
	//否则，若cur和prev连续，则将两者同时向后移动继续进行cur位置与基准值的比较；
	//若不连续，则将prev向后移动一位并与cur位置的值进行交换，再将cur向后移动
	{
		if (arr[cur] > key)
		{
			cur++;
		}
		else
		{
			if (cur == (prev + 1))
			{
				prev++;
				cur++;
			}
			else
			{
				prev++;
				int tmp = arr[prev];
				arr[prev] = arr[cur];
				arr[cur] = tmp;
				cur++;
			}
		}
	}
	//当cur的位置移动到超出数组范围时，将基准值与prev位置的值进行交换；此时左边为小于基准值的值，右边为大于基准值的值。
	int tmp = arr[left];
		arr[left] = arr[prev];
		arr[prev] = tmp;
		return prev;
}
void part(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int div = part3(arr, left, right);
	part(arr, left, div - 1);
	part(arr, div + 1, right);
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	part(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

快速排序非递归法：用顺序表实现。顺序表和队列的相关函数声明在下一篇文章中进行介绍。

//快速排序非递归法,用顺序表实现
int getmid(int* arr, int left, int right)
{
	int mid = left + (right + left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
			return right;
	}
}
int part2(int* arr, int left, int right)
{
	int mid = getmid(arr, left, right);
	int tmp = arr[mid];
	arr[mid] = arr[left];
	arr[left] = tmp;
	int key = arr[left];
	while (left < right)
	{
		while (left < right&&arr[right] >= key)
		{
			right--;
		}
		arr[left] = arr[right];
		while (left < right&&arr[left] <= key)
		{
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = key;
	return left;
}
/*排序的原理一样，但是在处理小于基准值和大于基准值的所有值的步骤中有所不同。
非递归方法利用顺序表，将数组的起始位置和结束位置放入顺序表中（注意先放结束位置再放起始位置），每次循环判断顺序表是否为空，若不为空，则将顺序表中的数据取出，取出的第一个元素为待排序数组的起始位置，第二个元素为结束位置，
取出后即删除顺序表中的这两个元素，并对这两个位置之间的数据进行排序，得到下一次待排序数组的基准值，判断上次取出的起始位置是否小于排序后小于基准值的一侧数据的结束位置，若小于，则将小于基准值一侧数据的起始位置和结束位置尾插进顺序表中，对大于基准值一侧的数据进行同样的操作，直到顺序表为空，即表示排序完成。*/
void QuickSortnonr(int* arr, int n)
{
	SeqList sq;
	SeqListinit(&sq);
	SeqListPushBack(&sq, n - 1);
	SeqListPushBack(&sq, 0);
	while (!SeqListEmpty(&sq))
	{
		int left = SeqListBack(&sq);
		SeqListPopBack(&sq);
		int right = SeqListBack(&sq);
		SeqListPopBack(&sq);
		int div = part2(arr, left, right);
		if (left < div - 1)
		{
			SeqListPushBack(&sq, div - 1);
			SeqListPushBack(&sq, left);
		}
		if (div + 1 < right)
		{
			SeqListPushBack(&sq, right);
			SeqListPushBack(&sq, div + 1);
		}
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSortnonr(arr,n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

用队列实现：用队列实现和用顺序表实现的区别就在于起始和结束位置存入数据结构的顺序，队列是先存入起始位置，再存入结束位置。因为队列是先入先出。

//快速排序非递归法，用队列实现
int getmid(int* arr, int left, int right)
{
	int mid = left + (right + left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
			return right;
	}
}
int part2(int* arr, int left, int right)
{
	int mid = getmid(arr, left, right);
	int tmp = arr[mid];
	arr[mid] = arr[left];
	arr[left] = tmp;
	int key = arr[left];
	while (left < right)
	{
		while (left < right&&arr[right] >= key)
		{
			right--;
		}
		arr[left] = arr[right];
		while (left < right&&arr[left] <= key)
		{
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = key;
	return left;
}
void QuickSortnonr(int* arr, int n)
{
	Queue q;
	queueinit(&q);
	queuePush(&q, 0);
	queuePush(&q, n-1);
	while (!queueempty(&q))
	{
		int left = queueFront(&q);
		queuePop(&q);
		int right = queueFront(&q);
		queuePop(&q);
		int div = part2(arr, left, right);
		if (left < div - 1)
		{
			queuePush(&q, left);
			queuePush(&q, div-1);
		}
		if (div + 1 < right)
		{
			queuePush(&q, div+1);
			queuePush(&q, right);
		}
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSortnonr(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

归并排序递归法：

//归并排序递归法，时间复杂度o（N*logN），稳定。
void Merge(int* arr, int begin,int mid,int end,int* tmp)
{
	int begin1 = begin;
	int end1 = mid;
	int begin2 = end1 + 1;
	int end2 = end;
	//辅助空间的起始位置
	int idx = begin;
	//合并有序序列
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[idx] = arr[begin1];
			idx++; begin1++;
		}
		else
		{
			tmp[idx++] = arr[begin2++];
		}
	}
	//判断是否有未合并的元素
	if (begin1 <= end1)
	{
		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
	}
	if (begin2 <= end2)
	{
		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
	}
	//合并之后的序列拷到原始数组中
	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = begin+(end - begin) / 2;
	MergeSort(arr, begin, mid, tmp);
	MergeSort(arr, mid + 1, end, tmp);
	Merge(arr, begin, mid, end, tmp);
}
void MS(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	MS(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

归并排序非递归法

//归并排序非递归
void Merge(int* arr, int begin, int mid, int end, int* tmp)
{
	int begin1 = begin;
	int end1 = mid;
	int begin2 = end1 + 1;
	int end2 = end;
	//辅助空间的起始位置
	int idx = begin;
	//合并有序序列
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[idx] = arr[begin1];
			idx++; begin1++;
		}
		else
		{
			tmp[idx++] = arr[begin2++];
		}
	}
	//判断是否有未合并的元素
	if (begin1 <= end1)
	{
		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
	}
	if (begin2 <= end2)
	{
		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
	}
	//合并之后的序列拷到原始数组中
	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void MergeNor(int *arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	int step = 1;
	while (step < n)
	{
		for (int idx = 0; idx < n; idx += 2 * step)
		{
			//找到两个待合并的子序列区间：[begin,mid],[mid+1,end]
			int begin = idx;
			int mid = idx + step - 1;
			//判断是否存在第二个子序列
			if (mid >= n - 1)
				//不存在，直接跳过
				continue;
			int end = idx + 2 * step - 1;
			//判断第二个子序列是否越界
			if (end >= n)
				end = n - 1;
			//合并
			Merge(arr, begin, mid, end, tmp);
		}
		//更新步长
		step *= 2;
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	MergeNor(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

非比较排序,如果range很大，会浪费很多空间

//非比较排序，时间复杂度o（Max（n，range）），空间复杂度o（range）；

void CountSort(int* arr, int n)
{
	int max, min;
	min = max = arr[0];
	for(int i = 1; i < n; ++i)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	}
	int range = max - min + 1;
	int* Countarr = (int*)calloc(range, sizeof(int));//创建数组的同时初始化为0
	//计数
	for (int i = 0; i < n; ++i)
	{
		Countarr[arr[i] - min]++;
	}
	//遍历
	int idx = 0;
	for (int i = 0; i < range; ++i)
	{
		while (Countarr[i]--)
		{
			arr[idx++] = i + min;
		}
	}
}
void main()
{
	int arr[] = { 5,6,3,1,8,7,2,4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	CountSort(arr, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
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

下面对几种排序方法的性能进行比较

#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<stdbool.h>
#include"queue.h"
//排序
//非比较排序
int getMid(int* arr, int left, int right)
{
	int mid = left + (right + left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
			return right;
	}
}
void CountSort(int* arr, int n)
{
	int max, min;
	min = max = arr[0];
	for(int i = 1; i < n; ++i)
	{
		if (arr[i] > max)
			max = arr[i];
		if (arr[i] < min)
			min = arr[i];
	}
	int range = max - min + 1;
	int* Countarr = (int*)calloc(range, sizeof(int));//创建数组的同时初始化为0
	//计数
	for (int i = 0; i < n; ++i)
	{
		Countarr[arr[i] - min]++;
	}
	//遍历
	int idx = 0;
	for (int i = 0; i < range; ++i)
	{
		while (Countarr[i]--)
		{
			arr[idx++] = i + min;
		}
	}
}
//归并排序非递归
void Merge(int* arr, int begin, int mid, int end, int* tmp)
{
	int begin1 = begin;
	int end1 = mid;
	int begin2 = end1 + 1;
	int end2 = end;
	//辅助空间的起始位置
	int idx = begin;
	//合并有序序列
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[idx] = arr[begin1];
			idx++; begin1++;
		}
		else
		{
			tmp[idx++] = arr[begin2++];
		}
	}
	//判断是否有未合并的元素
	if (begin1 <= end1)
	{
		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
	}
	if (begin2 <= end2)
	{
		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
	}
	//合并之后的序列拷到原始数组中
	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void MergeNor(int *arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	int step = 1;
	while (step < n)
	{
		for (int idx = 0; idx < n; idx += 2 * step)
		{
			//找到两个待合并的子序列区间：[begin,mid],[mid+1,end]
			int begin = idx;
			int mid = idx + step - 1;
			//判断是否存在第二个子序列
			if (mid >= n - 1)
				//不存在，直接跳过
				continue;
			int end = idx + 2 * step - 1;
			//判断第二个子序列是否越界
			if (end >= n)
				end = n - 1;
			//合并
			Merge(arr, begin, mid, end, tmp);
		}
		//更新步长
		step *= 2;
	}
}
//归并排序递归法，时间复杂度o（N*logN），稳定。
void MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = begin+(end - begin) / 2;
	MergeSort(arr, begin, mid, tmp);
	MergeSort(arr, mid + 1, end, tmp);
	Merge(arr, begin, mid, end, tmp);
}
void MS(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}
//快速排序非递归法，用队列实现
int partQ(int* arr, int left, int right)
{
	int mid = getMid(arr, left, right);
	int tmp = arr[mid];
	arr[mid] = arr[left];
	arr[left] = tmp;
	int key = arr[left];
	while (left < right)
	{
		while (left < right&&arr[right] >= key)
		{
			right--;
		}
		arr[left] = arr[right];
		while (left < right&&arr[left] <= key)
		{
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = key;
	return left;
}
void QuickSortnonrQ(int* arr, int n)
{
	Queue q;
	queueinit(&q);
	queuePush(&q, 0);
	queuePush(&q, n-1);
	while (!queueempty(&q))
	{
		int left = queueFront(&q);
		queuePop(&q);
		int right = queueFront(&q);
		queuePop(&q);
		int div = partQ(arr, left, right);
		if (left < div - 1)
		{
			queuePush(&q, left);
			queuePush(&q, div-1);
		}
		if (div + 1 < right)
		{
			queuePush(&q, div+1);
			queuePush(&q, right);
		}
	}
}
//快速排序前后指针法
int part3(int* arr, int left, int right)
{
	int prev = left;//上一个小于基准值的位置
	int cur = left+1;//下一个小于基准值的位置
	int key = arr[left];
	while (cur <= right)
	//若cur位置的值大于基准值，则cur向后移动；
	//否则，若cur和prev连续，则将两者同时向后移动继续进行cur位置与基准值的比较；
	//若不连续，则将prev向后移动一位并与cur位置的值进行交换，再将cur向后移动
	{
		if (arr[cur] > key)
		{
			cur++;
		}
		else
		{
			if (cur == (prev + 1))
			{
				prev++;
				cur++;
			}
			else
			{
				prev++;
				int tmp = arr[prev];
				arr[prev] = arr[cur];
				arr[cur] = tmp;
				cur++;
			}
		}
	}
	//当cur的位置移动到超出数组范围时，将基准值与prev位置的值进行交换；此时左边为小于基准值的值，右边为大于基准值的值。
	int tmp = arr[left];
		arr[left] = arr[prev];
		arr[prev] = tmp;
		return prev;
}
void partp(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int div = part3(arr, left, right);
	partp(arr, left, div - 1);
	partp(arr, div + 1, right);
}
//快速排序挖坑法
int part2(int* arr, int left, int right)
{
	int mid = getMid(arr, left, right);
	int tmp = arr[mid];
	arr[mid] = arr[left];
	arr[left] = tmp;
	int key = arr[left];
	while (left < right)
	{
		while (left < right&&arr[right] >= key)
		{
			right--;
		}
		arr[left] = arr[right];
		while (left < right&&arr[left] <= key)
		{
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = key;
	return left;
}
void partw(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int div = part2(arr, left, right);
	partw(arr, left, div - 1);
	partw(arr, div + 1, right);
}
//快速排序优化,三数取中法确定基准值，起始位置，中间位置，结束位置;数据有序时，如果没有优化，可能会导致栈溢出，因为栈调用的层数约等于数据的个数，优化之后，划分比较均衡，时间复杂度为o（n*logn），栈的调用层数约等于logn；
//稳定性：不稳定
//快速排序递归实现,hoare版本
int parthoare(int* arr, int left, int right)
{
	int mid = getMid(arr, left, right);//获取基准值的位置
	//把基准值放到起始位置
	int tmp = arr[left];
	arr[left] = arr[mid];
	arr[mid] = tmp;
	int idx = arr[left];
	int start = left;
	while (left < right)
	{
		while (left < right&&arr[right] >= idx)//从后往前找第一个小于基准值的数据
		{
			right--;
		}
		while (left < right&&arr[left] <= idx)//从前往后找第一个大于基准值的数据
		{
			left++;
		}
		int tmp = arr[right];//交换两个数据
		arr[right] = arr[left];
		arr[left] = tmp;
	}
	int x = arr[start];//结束时将left和right相遇的位置的数据和基准值交换,此时基准值左边的值都小于基准值，右边的值都大于基准值；
	arr[start] = arr[left];
	arr[left] = x;
	return left;//返回此时基准值所在的位置
}
void parth(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int div = parthoare(arr, left, right);
	parth(arr, left, div - 1);//[left,div-1)
	parth(arr, div + 1, right);//(div+1,right]
}
//冒泡排序，时间复杂度o（N^2）,空间复杂度o(1),稳定。
void Bubble(int* arr, int n)
{
	int end = n;
	while (end > 1)//进行一次循环后，需要比较的数据就少一个。
	{
	int flag = 0;
		for (int i = 0; i < end-1; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				int tmp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = tmp;
				flag = 1;
			}
		}
		if(!flag)
		break;
		end--;
	}
}
//堆排序,时间复杂度o（N*logN），空间复杂度o（1），不稳定
void shiftdown(int* arr, int n, int root)//若向下调整为最大堆，进行排序后数组数据排序方式为从小到大，若为最小堆，则排序方式为从大到小。
{
	int child = 2 * root + 1;//左孩
	while (child<n)
	{
		if (arr[child + 1] > arr[child] && child + 1 < n)
		{
			child++;//若右孩大于左孩且右孩没有超出数组范围，则将父节点与右孩比较；
		}
		if (arr[root] < arr[child])//调整为最大堆
		{
			int tmp = arr[root];//交换后继续从右孩处进行比较
			arr[root] = arr[child];
			arr[child] = tmp;
			root = child;
			child = 2 * root + 1;
		}
		else//若父节点比右孩大则结束循环
			break;
	}
}
void heap(int* arr, int n)
{
	for (int i = (n - 2) / 2;i >= 0; --i)//从最后一个非叶子结点开始向上调整，调整到根结点；每次调整都将该非叶子结点的结构变为最大堆，结束循环后该数组即为最大堆
	{
		shiftdown(arr, n, i);
	}
	int end = n - 1;//进行排序，每次将最大值放到数组最后一个位置，并在下次排序时不将该最大值考虑在内
	while (end > 0)
	{
		int tmp = arr[end];
		arr[end] = arr[0];
		arr[0] = tmp;
		shiftdown(arr, end, 0);
		--end;
	}
}
//优化直接排序
void swap(int* arr, int pos1, int pos2)//交换函数
{
	int tmp = arr[pos1];
	arr[pos1] = arr[pos2];
	arr[pos2] = tmp;
}
void Select(int* arr, int n)//优化后同时将最大值和最小值得到
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int min = start;
		int max = start;
		for (int i = start + 1; i <=end; i++)
		{
			if (arr[i] > arr[max])
			{
				max = i;
			}
			if (arr[i] < arr[min])
			{
				min = i;
			}
		}
		swap(arr, start, min);//得到最小值后将最小值放在最前面
			if (max == start)//若最大值就在第一个位置，则将其与最小值交换，否则会使最大值丢失
				max = min;
			swap(arr, end, max);//把最大值放在最后面
			start++;//排除第一个和最后一个数据继续进行排序
			end--;
	}
}
//直接排序,时间复杂度o（N*N），空间复杂度o（1），不稳定。
void select(int* arr, int n)
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int min = start;
		int i;
		for (i=start+1; i < n; ++i)
		{
			if(arr[i] < arr[min])
			{
				min = i;
			}
		}
		int tmp = arr[start];
		arr[start] = arr[min];
		arr[min] = tmp;
		++start;
	}
}
//希尔排序:时间复杂度o（N^1.3）;不稳定
void shell(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3+1;//定义每一次排序的两个数据之间的距离
		for (int i = gap; i < n; i++)
		{
			int end = i - gap;//有序数列中的最后一个数据
			int data = arr[i];
			while (end >= 0 && arr[end] > data)//若最后一个数据大于同组的另一个数据，则将最后一个数据放在另一个数据之后，并更新end的值
			{
				arr[end + gap] = arr[end];
				end = end - gap;
			}
			arr[end + gap] = data;//若最后一个数据小于同组数据，则将该数据插入到end+gap的位置
		}
	}
}
//插入排序：时间复杂度最大为o（N*N）；最小为o（N）；不稳定；
void insert(int* arr, int n)
{
	for (int i = 1; i < n; ++i)
	{
		int end = i - 1;
		//保存要插入的数据
		int data = arr[i];
		//如果插入的数据小于有序列的最后一个数，则将最后一个数向后移动；并让插入数据继续向前对比；
		while (end >= 0 && arr[end] >= data)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = data;
	}
}
void main()
{
	int n;
	printf("数据量:\n");
	scanf("%d", &n);
	srand(time(NULL));
	int* arr = (int*)malloc(sizeof(int)*n);
	int* copy1 = (int*)malloc(sizeof(int)*n);
	int* copy2 = (int*)malloc(sizeof(int)*n);
	int* copy3 = (int*)malloc(sizeof(int)*n);
	int* copy4 = (int*)malloc(sizeof(int)*n);
	int* copy5 = (int*)malloc(sizeof(int)*n);
	int* copy6 = (int*)malloc(sizeof(int)*n);
	int* copy7 = (int*)malloc(sizeof(int)*n);
	int* copy8 = (int*)malloc(sizeof(int)*n);
	int* copy9 = (int*)malloc(sizeof(int)*n);
	int* copy10 = (int*)malloc(sizeof(int)*n);
	int* copy11= (int*)malloc(sizeof(int)*n);
	int* copy12= (int*)malloc(sizeof(int)*n);
	int* copy13= (int*)malloc(sizeof(int)*n);
	for (int i = 0; i < n; ++i)
	{
		arr[i] = rand();
	}
	memcpy(copy1, arr, sizeof(int)*n);
	memcpy(copy2, arr, sizeof(int)*n);
	memcpy(copy3, arr, sizeof(int)*n);
	memcpy(copy4, arr, sizeof(int)*n);
	memcpy(copy5, arr, sizeof(int)*n);
	memcpy(copy6, arr, sizeof(int)*n);
	memcpy(copy7, arr, sizeof(int)*n);
	memcpy(copy8, arr, sizeof(int)*n);
	memcpy(copy9, arr, sizeof(int)*n);
	memcpy(copy10, arr, sizeof(int)*n);
	memcpy(copy11, arr, sizeof(int)*n);
	memcpy(copy12, arr, sizeof(int)*n);
	memcpy(copy13, arr, sizeof(int)*n);

	time_t begin = clock();
	insert(copy1, n);
	time_t end = clock();
	printf("插入排序：%d\n", end - begin);

	begin = clock();
	shell(copy2, n);
	end = clock();
	printf("希尔排序：%d\n", end - begin);

	begin = clock();
	select(copy3, n);
	end = clock();
	printf("直接排序：%d\n", end - begin);

	begin = clock();
	Select(copy4, n);
	end = clock();
	printf("优化直接排序：%d\n", end - begin);

	begin = clock();
	heap(copy5, n);
	end = clock();
	printf("堆排序：%d\n", end - begin);

	begin = clock();
	Bubble(copy6, n);
	end = clock();
	printf("冒泡排序：%d\n", end - begin);

	begin = clock();
	parth(copy7, 0,n-1);
	end = clock();
	printf("快速排序Hoare：%d\n", end - begin);

	begin = clock();
	partw(copy8, 0,n-1);
	end = clock();
	printf("快速排序挖坑：%d\n", end - begin);

	begin = clock();
	partw(copy9, 0, n - 1);
	end = clock();
	printf("快速排序指针：%d\n", end - begin);

	begin = clock();
	QuickSortnonrQ(copy10, n);
	end = clock();
	printf("非递归快速排序：%d\n", end - begin);

	begin = clock();
	MS(copy11, n);
	end = clock();
	printf("归并排序递归：%d\n", end - begin);

	begin = clock();
	MergeNor(copy12, n);
	end = clock();
	printf("归并排序非递归：%d\n", end - begin);

	begin = clock();
	CountSort(copy13, n);
	end = clock();
	printf("非比较：%d\n", end - begin);
}
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
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568

结果为