八大排序算法详解（通俗易懂）

前言

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面，一个优秀的算法可以节省大量的资源。

一、八大排序算法：

1.直接插入排序：

直接插入排序就是把待排序的元素逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

动图演示：

那比如给我们一段序列，代码如何实现呢？
我们可以把第一个元素看成有序序列（一个元素序列必然有序）进行多次单趟插排

void InsertSort(int* arr, int size)//直接插入排序
{
   
	for (int i = 0; i < size - 1; i++)
	{
   
		//单趟插入排序
		//基本思想：[0,end]区间值为有序
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
   
			if (tmp < arr[end])
			{
   
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
   
				break;//在这里break出去再去赋值tmp是为了防止最后一次end = -1进不来赋值
			}
		}
		arr[end + 1] = 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

2.希尔排序：

希尔排序是对直接插入排序的优化，它对序列先进行多次预排序使之接近有序，因为最后接近有序使用直接插入排序非常快。

如图所示：

• 当gap越大，预排序越快，但是越不接近有序
• 当gap越小，数据处理越慢，越接近有序
• 当gap为1即直接插入排序

如下代码所示：所以我们可以对gap进行动态改变

void ShellSort(int* arr, int size)//希尔排序
{
   
	int gap = size;
	//多次预排+最后一次直接插入排序
	while (gap > 1)
	{
   
		gap = gap / 3 + 1;//控制最后一次进来gap为1进行直接插入排序
		for (int i = 0; i < size - gap; i++)
		{
   
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
   
				if (tmp < arr[end])
				{
   
					arr[end + 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20