冒泡排序，插入排序，快速排序，堆排序，希尔排序，归并排序，计数排序，选择排序

🎉前言

本人是西安邮电大学一名普通的大二学生，希望这篇关于插入排序的博客对你有用

点个赞嘛

请添加图片描述

以下动图均来自https://www.r2coding.com/#/

🚕交换数据函数（SwapData）

这个函数会经常用到

1
2
3
4
5
6
7
void SwapData(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

🦽 寻找中间值做key的函数（GetMidi）

这个再快排那里会用到

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
int GetMidi(int* a,int left, int right)//寻找中间值做key
{
	int midi = left + ((right - left) >> 2);
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}
		else if (a[left]>a[right])
		{
			return left;
		}
		else 
		{
			return right;
		}
	}
	else
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

🚒 堆排序

点击这里看->堆的定义以及堆排序

🎈冒泡排序

冒泡排序动图解释：

在这里插入图片描述
冒泡就是每次把最大或者最小的挪到最边
这个代码不难理解，相信大家初学C语言就了解到了冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 冒泡排序
void BubbleSort(int* a, int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n; i++)
	{
		int exchange = 0;//加一个判断条件，比如：如果第x趟是有序的直接结束掉循环，return掉
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				SwapData(&a[j], &a[j + 1]);
				exchange = 1;//有交换的话置为1
			}
		}
		if (!exchange)//没有交换就返回
		{
			return;
		}
	}
}

🏍️插入排序

什么是插入排序

个人理解插入排序类似于打牌

幸运女神在微笑，胜利女神在微笑

在这里插入图片描述

在这里插入图片描述

🎉插入排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertSort(int* a, int n)//想象自己在打扑克
{
	int i = 0;
	for (i = 0; i < n - 1; i++)//先是第一个和第二个开始比较
	{
		int end = i;//end是下标
		int tmp = a[end + 1];
		while (end >= 0 && tmp < a[end])
		{
			a[end + 1] = a[end];
			end--;
		}
		a[end + 1] = tmp;//用3 1 2 作为测试用例就可以理解为什么是a[end+1]=tmp
	}
}

🚙希尔排序

希尔排序和插入排序差不了多少，只是每次比较的间距从1变成了一个变量，这个变量 gap根据数据的数量而定，不过最后gap还是要等于1

动图演示：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;//n=2的时候代入一下
	while (gap > 1)//gap=1的时候已经执行一次代码了，然后再判断的。
	{
		gap = gap / 3 + 1;
		int i = 0;
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0 && a[end] > tmp)
			{
				a[end + gap] = a[end];
				end-=gap;//记得这里是end-=gap  不是 end--！！！这是希尔排序！！！
			}
			a[end + gap] = tmp;
		}
	}
}

✈️快速排序

🏎️1.快速排序hoare版本（带哨兵位）

这个有个小细节就是哪边做key对边先走，比如左边做key 那就右边先走，然后右边找到比key小的数字就挺住，然后左边再走，左边找到比key大的就停住，然后交换两边的数字，然后右边再走，当两边碰到的时候，交换key（这里是左边）和 相遇位置的数字，当然这个是循环版本。

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
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)//哨兵
{
	int midi = GetMidi(a, left, right);
	SwapData(&a[left], &a[midi]);

	int keyi = left;
	while (left<right)
	{
		while (left<right&&a[right]>=a[keyi])
		{
			right--;
		}
		while(left < right && a[left]<=a[keyi])
		{
			left++;
		}
		SwapData(&a[left], &a[right]);
	}

	SwapData(&a[left], &a[keyi]);

	return left;
}


void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	if (right - left + 1 < 5)
	{
		InsertSort(a+left, right - left + 1);
	}
	else
	{
		int midi = PartSort1(a, left, right);
		QuickSort(a, left, midi - 1);
		QuickSort(a, midi + 1, right);
	}
}


🍕2快速排序挖坑法

在这里选择最左边做坑(key)然后从右边开始找比key小的然后a[left] = a[right]，然后从左边开始找找比key大的a[right] = a[left]，最后相遇的时候a[left] = key;//坑的值归位

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
int PartSort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	SwapData(&a[left], &a[midi]);

	int key = a[left];//坑
	while (left<right)
	{
		while (left < right && a[right] >= key)//左边做坑
		{
			right--;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key)//右边做坑
		{
			left++;
		}
		a[right] = a[left] ;
	}
	a[left] = key;//坑的值归位

	return left;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	if (right - left + 1 < 5)
	{
		InsertSort(a+left, right - left + 1);
	}
	else
	{
		int midi = PartSort2(a, left, right);
		QuickSort(a, left, midi - 1);
		QuickSort(a, midi + 1, right);
	}
}

🚒3.快速排序前后指针法

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
int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	SwapData(&a[left], &a[midi]);

	int keyi = left;
	int cur = left;
	int pro = left + 1;//pro 先走
	while (pro<=right)
	{
		if (a[pro] < a[keyi] && a[++cur] != a[pro])
		{
			SwapData(&a[pro], &a[cur]);
		}
		pro++;
	}
	SwapData(&a[keyi],& a[cur]);

	return cur;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	if (right - left + 1 < 5)
	{
		InsertSort(a+left, right - left + 1);
	}
	else
	{
		int midi = PartSort3(a, left, right);
		QuickSort(a, left, midi - 1);
		QuickSort(a, midi + 1, right);
	}
}

🍺4.快速排序非递归法

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
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	if (left < right)//先进后出
	{
		StackPush(&st, left);
		StackPush(&st, right);
	}
	while (!StackEmpty(&st))
	{
		right = StackTop(&st);
		StackPop(&st);
		left = StackTop(&st);
		StackPop(&st);
		int midi=PartSort3(a, left, right);

		if (left < midi )
		{
			StackPush(&st, left);
			StackPush(&st,midi - 1);
		}
		if (midi + 1 < right)
		{
			StackPush(&st, midi+1);
			StackPush(&st, right);
		}
	}
}

🚙归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法思想：1.把长度为n的输入序列分成两个长度为n/2的子序列；2. 对这两个子序列分别采用归并排序；3. 将两个排序好的子序列合并成一个最终的排序序列。

在这里插入图片描述

这个是递归版本：

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
void _MergeSort(int* a, int begin, int end,int* tmp)//先分成最小规模子问题然后再解决
{
	if (begin >= end)
	{
		return;
	}
	int midi = begin + ((end-begin)>>1);
	_MergeSort(a, begin, midi, tmp);
	_MergeSort(a, midi+1, end, tmp);

	int begin1 = begin;
	int end1 = midi;
	int begin2 = midi + 1;
	int end2 = end;
	int index = begin;//合并两个有序数组

	while(begin1<=end1&&begin2<=end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1<=end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2<=end2)
	{
		tmp[index++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序
void MergeSort(int* a, int n)
{  
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	_MergeSort(a, 0, n-1,tmp);//传闭区间好控制一点点
	free(tmp);
}

还有这个非递归版的归并排序：

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
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;
	while (gap<n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2*gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			if (begin2<n && end2 >= n)
			{
				end2 = n - 1;
			}
			int index = i;
			while (begin1<=end1 && begin2<=end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1<=end1)
			{
				tmp[index++]=a[begin1++];
			}
			while (begin2<=end2)
			{
				tmp[index++] = a[begin2++];
			}
		}
		assert(tmp);
		memcpy(a, tmp, n * sizeof(int));
		gap *= 2;
	}
	free(tmp);
}

🎄计数排序

计数排序统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
计数排序不是比较排序，排序的速度快于任何比较排序算法。
算法思想：

找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；

在这里插入图片描述

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
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	int i = 0;
	for (i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = (max - min + 1);
	int* tmp = (int*)malloc(sizeof(int)*range);
	assert(tmp);
	memset(tmp, 0, sizeof(int) * range);//把tmp数组初始化为0 
	int j = 0;
	int count = 0;//最后把tmp中的值赋给a,控制a的下标
	for (i = 0; i < n; i++)
	{
		tmp[a[i] - min]++;
	}
	for (i = 0; i < range; i++)
	{
		for (j = 0; j < tmp[i]; j++)
		{
			//a[count++] = (tmp[j] + min);这是错误写法
			//a[count++] = (tmp[i] + min); 这是错误写法
			a[count++] = i + min;//下标+min才是原来的数字
		}
	}
}

💖 选择排序

在这里插入图片描述

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
void SelectSort(int* a, int n)
{
	int left = 0;//控制最左边和最右边的边界
	int right = n - 1;//控制最左边和最右边的边界
	
	while (left < right)
	{
		int mini = left;
		int maxi = left;
		for (int i = left; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		SwapData(&a[left], &a[mini]);
		if (maxi == left)//如果第一个数是最大的话就没交换到mini的位置上去了
		{
			maxi = mini;
		}
		SwapData(&a[right], &a[maxi]);
		left++;
		right--;
	}
}

结语

点赞评论呗
请添加图片描述

C语言
#算法 #数据结构 #笔记 #排序算法
冒泡排序，插入排序，快速排序，堆排序，希尔排序，归并排序，计数排序，选择排序
https://6jackjiang.github.io/2022/05/05/categories/C语言/冒泡排序，插入排序，快速排序，堆排序，希尔排序，归并排序，计数排序，选择排序/
作者
米兰的小铁匠
发布于
2022年5月5日
许可协议