超详细八大排序+基数排序（图文并茂+动图演示+C语言代码演示）_基数排序图解过程

插入排序-直接插入排序

思想引入

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。 实际中我们玩扑克牌时，就用了插入排序的思想

动图演示：

插入排序比较好理解，就是将数组中的每一个数字拿出来往前扫描，若大于则插在其后，一直反复操作，直到拿完所有的数为止

不再做过多赘述，上代码

void InsertSort(int* a, int n)
{
	for (int i = 0;i < n - 1;i++)
	{
		int end = i;//end用来做扫描时的下标
		int x = a[end + 1];//便是此趟插入拿出来的数据
		while (end >= 0)//一直扫描到数组的头
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码逻辑动图如下：

在最坏情况下，也就是数组为降序时，此时要进行升序操作，时间复杂度将达到O（N^2），而在最好的情况下，插入排序的时间复杂度仅为O（N），因此数学家希尔想了一个办法，若通过某种办法使得待排序列接近有序，此时再来进行一次直接插入排序，是不是更有效了呢？于是就有了下面的希尔排序

插入排序-希尔排序

思想引入

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个小于N的整数gap作为一个增量，把待排序序列中所有数据为gap的数放在一组，并对每一组进行直接插入排序，然后缩小增量，重复上述过程，直至gap==1，此时我们得到一个接近有序的序列，因此对整体数据进行一次插入排序时，时间复杂度将大大缩减。

增量gap呈现从大到小的变化，使得序列一步步接近有序

现在已知的有几种设定增量变化的方法：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
希尔排序的时间复杂度都不固定

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

下面给出多组并排的例子

代码：

//**希尔排序**O(N^1.3)--算是很优化的一种排序
void ShellSort(int* a, int n)
{
	//插入排序的优化版本（非常优化）
	int gap = n;
	while(gap>1)
	{
		gap = gap / 3 + 1;	 
		for (int i = 0;i < n - gap;i++)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = x;
		}
	}
}
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

选择排序-直接选择排序

动图演示

思路很简单，从待排序列中选出最小值，放在序列的起始位置，直到全部扫描完

下面代码我进行了优化，选择最小值的同时选择出了最大值放在序列的结束位置

代码如下：

// 选择排序
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin; i <= end;i++)
		{
			if (a[i] >= a[maxi])
				maxi = i;
			if (a[i] <= a[mini])
				mini = i;
		}
		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
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

选择排序-堆排序

首先，我们得明白，什么是堆？

堆，是一种完全二叉树的结构，分为大根堆和小根堆，堆排序是基于堆的二叉树结构的一种相对来说较好的排序方法。

下面用一张图简单介绍一下什么是大根堆和小根堆（以下都简称大堆和小堆）

大根堆:每个节点的值都大于或者等于他的左右孩子节点的值

小根堆:每个结点的值都小于或等于其左孩子和右孩子结点的值

现在我们可以引入思想

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

我们从思想又引入一个词——建堆

通俗点讲，就是在数组原来的物理结构的序列上，通过改变物理结构的序列，使得其逻辑结构是大堆或小堆

而建堆我们也分两种方法——自下而上建堆法和自上而下建堆法（简称向上建堆和向下建堆）

我们以向上建堆，建大堆使得物理结构是升序为例

向上建堆法使用的是向下调整算法，该算法能够保证堆一直维持着大堆或小堆的状态

向下调整算法的基本思路（以大堆为例）：从根点开始，我们找到其左右孩子中较大的一个孩子与父亲比较，若父亲小于孩子，则交换，若父亲大于孩子，证明这个子树已经是大堆态，只需将较大的孩子作为父亲如此迭代下去，直到遇到叶子结点，向下调整就结束了。

已下图为例

在最坏的情况下，我们一共需要向下调整高度次，而二叉树的高度为log（N+1），因此时间复杂度为O（logN）

这就是一次向下调整，我们做以下思考：如果以17为根结点的子树不是一个大堆，那么这个堆还能叫大堆吗？

因此向下调整算法应该自下往上去建堆，这样才能保证每一棵子树都是大堆。

因此，我们应该从最后一个非叶子结点开始，才用向下调整去改变物理结构的序列将堆建成。（叶子结点无左右子树，因此不用考虑）

而每一对父子的下标是有规律的：

child1=parent*2+1

child2=parent*2+2

parent=（child-1）/2

下面将动图演示一下建堆过程

这样建堆就完成了，由于最后一排的叶子结点不用考虑，因此时间复杂度为每个做父亲的结点个数向下调整的高度次的次数，这是一个等差 *等比的数列求和，因此要用数学的错位相减法来求

而要完成堆排序，就是在大堆的前提上，将堆顶与堆的最后一个数据交换，并进行一次向下调整再次选出堆顶（也就是次大），调整时，最后一个数据不在调整范围内，不然又会被调回堆顶。

此时，除了最后一个数是最大数以外，其他数的逻辑结构仍然是一个大堆，于是我们就将堆顶与倒数第二个数交换，如此迭代

我们进行一下简单总结：

1. 想要完成堆排序，前提是此连续存储的数据在逻辑结构上是一个大堆或者小堆
2. 如果想要完成升序，则前提是大堆，降序则前提是小堆
3. 而若逻辑结构不是堆的数据我们可以通过向下调整算法来建堆
4. 向下调整算法可以形象的认为在向上建堆（从最后一个非叶子结点开始，保证每个子树都是堆）
5. 在原本已经是排好序的结构中，尾插数据后，可以通过向上调整算法重新调整有序数据，使其保持原本的堆结构。

这样，堆排序就完成了

代码如下

// 堆排序
void AdjustDown(int* data, int size, int parent)
{
	assert(data);

	int child = parent * 2 + 1;

	while (child < size)
	{
		//小堆控制小于号
		//大堆控制大于号
		//比较左右孩子，再决定跟哪个孩子交换
		if (child + 1 < size && data[child + 1] > data[child])
		{
			child++;
		}
		//大堆，堆顶是最大的，因此孩子比父亲大的就交换
		if (data[child] > data[parent])
		{
			Swap(&data[child], &data[parent]);
			parent = child;
			child = parent * 2 + 1;

		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//先向上建个大堆
	for (int i = (n - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(a, n, i);
	}
    //将堆顶依次往后面放
	for (int i = n-1;i > 0;i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);

	}

}
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

交换排序-冒泡排序

思想引入

“冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

上代码：

void BubbleSort(int* a, int n)
{
	for (int i = 0;i < n - 1;i++)
	{
		int flag = 1;
		for (int j = 0;j < n - 1 - i;j++)
		{
			if (a[j] > a[j + 1])
			{
				flag = 0;
				Swap(&a[j], &a[j + 1]);
			}
		}
		if (flag)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

交换排序-快速排序-三种方法（重点）

快速排序分区法-hoare版本

思想引入

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

hoare版本的核心思路通俗来讲就是选取待排数组范围内的一个数作为关键字（一般是最左边或者最右边）将其放到他在有序数组中的位置上，也就是他本来应该在的位置，并且此时关键字的左边一定都是比关键字小的数，右边一定是比关键字大的数，然后再以此类推，直到所有的数都做为关键字放在了正确的位置上

现在给出图文解释比较好懂

left和right停下之后就进行交换

重复上述过程

当到达这一步时

也就是left指针与right指针相遇了，此时交换关键字key和相遇位置的值

到这一步时，大家有没有发现，6的左边已经都是小于6的数，而右边都是大于6的数

现在解释一下为什么最左边做key时最右边要先走：

我们知道，left指针是去找大于key的数，因此停下来的位置的值一定比key大，若左边先出发，右边后出发且此时相遇了，那么相遇点的值一定是大于key的值，此时再交换，则达不到key的左右两边要么大要么小的目的。因此我们要保证提前相遇的位置与key交换后是想要的效果，若最左边做key，则右边先走，最右边做key则左边先走。

这样，我们快速排序的单趟排序就完成了，接下来只需不断改变左右区间，使得每个数字都落到正确的位置上，直到key的左右序列排序就完成啦，我们要记住一个结论，那就是数据只有一个时，便是有序的。

对于实现快速排序的方法，我们有两种思路：

1. 递归

2. 非递归（栈）

   下面将逐一用代码演示

   快速排序-递归实现

   void QuickSort(int* a, int left, int right)
   {
   	//递归返回条件
   	if (left >= right)
   	{
   		return;
   	}
   	else
   	{
   		//获取第一次调用或上一次递归相遇时的下标
   		int keyi = Partion1(a, left, right);
   		//分区间分别hoare
   		QuickSort(a, left, keyi - 1);
   		QuickSort(a, keyi + 1, right);
   	}
   }
   //快速排序分区法1-hoare版本
   int Partion1(int* a, int left,int right)
   {
   	int keyi = left;
   	while (left < right)
   	{
   		//右边找小(key在最左边，考虑提前相遇的情况，右边先走)-升序，降序则相反
   		while(left < right && a[right] >= a[keyi])
   			right--;
   		//左边找大，找比keyi的值大的数
   		while(left < right && a[left] <= a[keyi])
   			left++;
   		Swap(&a[left], &a[right]);//交换
   	}
   	Swap(&a[left], &a[keyi]);
   	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
   31
   32
   33

以我的代码为例，我们对刚刚为排序完的序列做思路分析

经过上轮筛选，返回keyi=5

更新范围为[0,4]，返回keyi=2——数值6的左边（同学们用纸手动模拟一下）

更新范围为[0,1]，返回keyi=0——数值3的左边

更新范围为[0,0]，达到返回条件（默认有序）返回上层函数——数值2的左边

更新范围[1,1]，达到返回条件，返回上层函数——数值2的右边

此层函数调用完成，返回上层函数

更新范围[3,4]，返回keyi=3——数值3的右边

更新范围[3,3]——数值4的左边，更新范围[4,4]——数值4的右边，此层调用结束，一直返回到进入数值6的右边

后面就不再做解释，大家有没有发现左边已经有序了？

快速排序-非递归实现

非递归实现需要用到栈来完成，这里给出的代码不包含栈，大家自行完成

由于栈的特点便是先进后出，后进先出，非常符合快速排序，下面我用一张图简单模拟过程

大家一定要自己模拟一遍

void QuickSortNonR(int* a, int left, int right)
{
	//用栈模拟实现
	Stack st;
	InitStack(&st);
    //先进栈
	PushStack(&st, left);
	PushStack(&st, right);
    //栈不为空就拿数据
	while (!EmptyStack(&st))
	{
        //更新区间
		int end = TopStack(&st);
		PopStack(&st);
		int begin = TopStack(&st);
		PopStack(&st);
        //拿返回值
		int keyi = Partion1(a, begin, end);//分区法代码与上面一致
        //单个数据时不再进栈
		if (keyi - 1 > begin)
		{
			PushStack(&st, begin);
			PushStack(&st, keyi - 1);
		}
		if (keyi + 1 < end)
		{
			PushStack(&st, keyi + 1);
			PushStack(&st, end);
		}
	}
	DestroyStack(&st);
}
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

快速排序分区法-挖坑法

下面介绍的方法将不再一一演示过程，思路都是一样的，只是方法上有些许不同，大家自行模拟，我将给出动图演示整个过程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EywZahhB-1680439440641)(D:\小比特\数据结构初阶\picture\快速11.gif)]

上代码：

//快速排序分区法2-挖坑法
int Partion2(int* a, int left, int right)
{
	int mini = GetMiddle(a, left, right);
	Swap(&a[mini], &a[left]);
	int keyi_val = a[left];
	int hole = left;	
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= keyi_val)
		{	
			right--;
		}
		//将比keyi_val小的值扔进坑里
		a[hole] = a[right];
		hole = right;
		//找大
		while(left < right && a[left] <= keyi_val)
		{
			left++;
		}
		//将比keyi_val大的值扔进坑里
		a[hole] = a[left];
		hole = left;
	}
	//最后用keyi_val填坑
	a[hole] = keyi_val;
	return hole;

}
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

快速排序分区法3-前后指针法

话不多说，直接上动图

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/454373