第五章数据结构与算法——八大排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了第五章数据结构与算法——八大排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、排序的概念及其运用

二、八大排序的原理及其实现（升序为例）

（一）、直接插入排序

（二）、希尔排序（也叫缩小增量排序）（重要）

1.原理：

2.该排序一般分为两个步骤：

3.预排序过程：

4.预排序的意义（升序为例）：

5.希尔排序的特点：

6.希尔排序代码实现：

（三）、堆排序

（四）、直接选择排序

（五）、快速排序（2023_09_21）

一、排序的概念及其运用

（一）、排序的概念

1、所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

2、 稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

举例：

例如一组数组中有三个相同的数字 3(a)、3(b)、3(c),，且 3(a) 的位置在 3(b) 前面，3(b)的位置在3(c)的前面，则排序过后，这三个3的相对位置没有改变，则称该排序算法是稳定的。

3、内部排序 ：数据元素全部放在内存中的排序。

4、外部排序 ：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二、八大排序的原理及其实现（升序为例）

（一）、直接插入排序

1.原理：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

2.特点：

①：元素的集合越接近有序，该算法的时间效率就越高；

②：时间复杂度：O(N^2)；

③：空间复杂度：O(1)；

3.代码实现：
//直接插入排序
//升序为例
void Insert(int* arr, int n)
{
	for (int i = 0; i<n-1; i++)
	{
		int end = i;
		//保存即将参与排序的第一个数（即end+1位置的数）,防止移动数据时，该数被覆盖
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			//挪动数据
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
			}
			else
			{
				break;
			}
			end--;
		}
		//插入数据
		arr[end + 1] = tmp;
	}
}

int main()
{
	int arr[7] = { 3,6,10,4,8,2,1 };
	//参数一是数组，参数二是数组元素个数
	Insert(arr, 7);
	return 0;
}

（二）、希尔排序（也叫缩小增量排序）（重要）

1.原理：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序（预排序）。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

2.该排序一般分为两个步骤：

①： 预排序

②：直接插入排序

3.预排序过程：

分组进行排序，间距为gap一组，如下：

后面我们会讨论gap的取值，但这里我们会发现：

当gap = 1时，就是直接插入排序，

并且通常 预排序会进行多次，以便更加接近有序。

4.预排序的意义（升序为例）：

①：大的数更快的跑到右边去，小的数更快跑到前面去；

②：gap越大，跳的越快（分组越少），越不接近有序；

③：gap越小，跳的越慢（分组越多），越接近的有序；

④：当gap = 1时，该排序为直接插入排序；

5.希尔排序的特点：

①：希尔排序是对直接插入排序的优化。

②：希尔排序的 时间复杂度不好计算 ，因为gap在动态变化，有人进行大量计算，最后我们取 O(n^1.3) ，但可以通过一些测试证明出他是直接插入排序的优化，比直接插入排序的效率要高；（2023_09_19）

③：稳定性：不稳定；

6.希尔排序代码实现：
//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//外层while循环就是进行多次预排序的操作
		//下面时库里面的两种规定，第一种是gap每次减少一半
		//因为任何整形连续除以2，最终都会等于1
		//所以当gap不等于1时，相当于在进行预排序，一步一步接近有序
		//当gap等于1时，进行直接插入排序
		
		//设置下面gap的两种方式是防止预排序次数不合适，若规定预排序的次数，则有时数组的数量或多或少
		//就会造成不合适，所以我们要设置来与数组的个数n有关联

		gap /= 2;
		//gap/=3+1；

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
	
	
}

int main()
{
	int arr[] = { 9,1,2,5,7,4,8,6,3 };
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	Print(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

（三）、堆排序

堆排序二叉树部分小编已经讲过了，所以在这里小编不过多叙述，感兴趣的小伙伴可以参考文章：堆排序

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

2.堆排序的特点：

①：堆排序使用堆来选数，效率就高了很多；

②：时间复杂度： O(N*logN)；

③：空间复杂度： O(1)；

④：稳定性：不稳定。

3.堆排序的代码实现（具体过程参考文章：）
//堆排序
void HeapSort(int* a, int n)
{
	//建堆(以降序建小堆为例)
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}
 
	//记录堆尾的下标
	int end = n - 1;
	//开始排序
	while (end > 0)
	{
		//交换堆顶和堆尾
		Swap(&a[0],&a[end]);
		//向下调整
		AdjustDown(a, end, 0);
		end--;
	}

（四）、直接选择排序

1.原理：每一次从待排序的数据元素中选出最小的和最大的元素，分别存放在序列的起始位置，和末位置，直到全部待排序的数据元素排完。

2.直接选择排序的特点：

①：直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用；

②：时间复杂度：O(N^2)；

③：空间复杂度：O(1)；

④：稳定性：不稳定；

3.直接选择排序的代码实现：
//直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int min = begin;
		int max = begin;
		for (int j = begin+1; j <=end; j++)
		{
			if (arr[j] > arr[max])
			{
				max = j;
			}
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}
		Swap(&arr[begin], &arr[min]);
		//如果最大值下标max与begin相等，则上述交换函数会把最大值交换到下标为min的位置，所以要记录一下
		if (max == begin)
		{
			max = min;
		}
		Swap(&arr[end], &arr[max]);
		begin++;
		end--;
	}
}

int main()
{
	//int arr[7] = { 3,6,10,4,8,2,1 };
	
	//直接选择排序
	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	Print(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}
①：首先创建两个变量begin和end来记录待排序数组的首尾位置下标，然后每选出一组最大最小数排序后，begin++，end--就更新了待排序数组的首尾位置下标，直到begin>end时代表排序结束；

②：然后创建两个变量min，和max分别记录最小值的下标和最大值的下标，因为这是一个寻找的过程，所以刚开始都初始化为begin，然后依次将待排序数组里面的数与该下标的值进行比较，若找到更小或更大的值，则更新下标，每找一次（for循环结束）就将下标为min的数与待排序数组的首位置下标begin的数进行交换，下标为max的数与待排序数组的末位置下标max的数进行交换，但要注意如果max等于begin的话，当你进行最小值min和begin交换的时候，begin位置为最大值会被交换到min的位置，所以这时要更新一下最大值的下标max，即将max更新成min.

（五）、快速排序（2023_09_21）

1.原理：

任取待排序元素序列中的某元素作为基准值（习惯称为key），按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.原理图：

3.快速排序特点：

①：快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序；

②：时间复杂度： O(N*logN)；
③：空间复杂度： O(logN)；

④：稳定性：不稳定；

4.快速排序的代码实现（有几种方法）
//三数取中（left,mid,right中找第二大那个作为key）
int GetMid(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if(arr[mid]<arr[right])//right最大
		{
			return mid;
		}
		else if(arr[left]<arr[right])//mid最大
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (arr[right] < arr[mid])//left最大
		{
			return mid;
		}
		else if(arr[left]<arr[right])//mid最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
 }

//快排的单趟排序
int PartSort(int* arr, int left, int right)
{
	int midi = GetMid(arr, left, right);
	Swap(&arr[left], &arr[midi]);
	int keyi = left;
	while (left < right)
	{
		while (arr[right] >= arr[keyi] && left < right)
		{
			right--;
		}
		while (arr[left] <= arr[keyi] && left < right)
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[keyi], &arr[left]);
	return left;

}

//快速排序
void QuickSort(int* arr, int begin,int end)
{
	if (begin >= end)
		return;
    //走单趟
	int keyi = PartSort(arr, begin, end);
	//走【begin,keyi-1】和【keyi+1,end】
	QuickSort(arr, begin, keyi - 1);
	QuickSort(arr, keyi + 1, end);
}

int main()
{
	int arr[] = { 6,1,10,7,5,3,4,9,2,8 };
	//快速排序
	QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);
	Print(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}
这里有个疑问：当left，right相遇时，我们是将key与left（相当于right）处的数相交换，从而使key找到正确的位置，但我们的规矩是key左边的数要比key对应的数要小，右边的数要比key要大，那这样交换，怎么能确认待交换这个数（也就是right和left相遇位置的数）要比key对应的位置小呐？？？

答案：这就要多亏与其中的一个小技巧，也就是当key在left处，我们就让right先走，当key在right处，我们就让left先走，当然key还有可能在中间，所以为了统一，我们写了三数取中函数GetMid（），这样就可以把合适的key放在left处，然后让right先走，这样写的好处是因为right和left相遇的情况有两种，如下：

①：当right动，left不动时，right去和left相遇：相遇位置是left处，但上一轮我们已经将right处（比key小的数）与left处（比key大的数）相交换了，所以该相遇处一定是比key处小的数。

②：当left动,right不动时，left去和right相遇：这种情况只能是right已经找到了比key小的数，然后停止，然后才让left移动，但是left向右移动过程中没有找到比key大的数，所以才会与right相遇，也就是说相遇处的数时由right找到的，所以相遇处的数一定会小于key处对应的数。
上述的单趟排序PartSort函数是经典的 “hoare”法，但是该方法细节太多，

所以下面有两种种思路明了且没有那么多细节的单趟排序算法，

①： “挖坑法”（但性能上面没有优势）
//单趟排序2（挖坑法）
int PartSort2(int* arr, int left, int right)
{
	int midi = GetMid(arr, left, right);
	Swap(&arr[left], &arr[midi]);
	int keyi = arr[left];
	//保留left,左边形成坑
	int hole = left;
	while (left < right)
	{
		//坑在左边。所以右边先走，找小
		while (left < right && arr[right] >= keyi)
		{
			right--;
		}
		//找到小，填入坑，自己变成坑
		arr[hole] = arr[right];
		hole = right;

		//然后左边走，找大。
		while (left < right && arr[left] <= keyi)
		{
			left++;
		}
		//找到大，填入坑，自己变成坑
		arr[hole] = arr[left];
		hole = left;
	}
	//right和left最终相遇在坑，将key填入坑，确定key的位置
	arr[hole] = keyi;
	return hole;
}
②："前后指针法"（但性能上面没有优势）
//前后指针
int PartSort3(int* arr, int left, int right)
{
	int prve = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && prve++ != cur)
		{
			Swap(&arr[cur], &arr[prve]);
		}
		cur++;
	}
	Swap(&arr[prve], &arr[key]);
	return prve;
}
5.算法优化：

我们由快排的算法联想到二叉树，然后我们知道二叉树最后几层节点占了总节点数的一大半，甚至最后一层的节点数大概占了总节点数的一半，所以联想到排序，我们可以看出最后几层会有大量的递归操作，但是只需要排序几个数，这样的开销不怎么划算，所以如下：

当递归到左右区间只有十个左右的数时，我们就采用直接插入排序，这样可以减少大量的递归开销：
//快速排序
void QuickSort(int* arr, int begin,int end)
{
	if (begin >= end)
		return;

	//小区间优化(剩十个数左右时)，小区间不在递归分割排序，，使用直接插入排序，降低了递归次数
	
	if (end - begin + 1 > 10)
	{
		//hoare法
		//int keyi = PartSort(arr, begin, end);

		//挖坑法
		//int keyi = PartSort2(arr, begin, end);

		//前后指针
		int keyi = PartSort3(arr, begin, end);

		//【begin,keyi-1】和【keyi+1,end】
		QuickSort(arr, begin, keyi - 1);
		QuickSort(arr, keyi + 1, end);
	}
	else
	{
		Insert(arr + begin, end - begin + 1);
	}
}
6.快速排序的非递归算法：

通过栈的后进先出特性实现：先入栈左区间再入栈右区间，每入栈一个区间就判断其左右区间是否存在且不只一个数，若是的话则继续入栈左右区间；
//快速排序（非递归）
void QuickSortNoR(int* arr, int begin, int end)
{
	ST st;
	STinit(&st);

	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		//找区间左端点
		int left = STTop(&st);
		STPop(&st);
		//找区间右端点
		int right = STTop(&st);
		STPop(&st);

		//单趟排序
		int keyi = PartSort(arr, left, right);

		//若右区间存在且不止一个数，则入栈
		if (keyi + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}

		//若左区间存在且不止一个数，则入栈
		if (keyi - 1 > left)
		{
			STPush(&st, keyi-1);
			STPush(&st, left);
		}

	}
}

（六）、归并排序

1.原理：

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

2.原理图：

3.归并排序的特点：
①：归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

②：时间复杂度： O(N*logN)

③：空间复杂度： O(N)

④：稳定性：稳定

⑤：从二叉树的角度思考出发会发现归并排序和快速排序是及其相似的，归并排序类似于二叉树的“后序遍历”，而快速排序类似于二叉树的“前序遍历”。

4.归并排序的代码实现（递归）：
//归并子函数进行递归
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
	//最小子递归返回条件，左右区间不存在(<),或者只有一个数(=)
	if (end <= begin)
		return;

	int mid = (begin + end) / 2;
	
	//递归左区间
	_MergeSort(arr, tmp, begin, mid);
	//递归右区间
	_MergeSort(arr, tmp, mid + 1,end);

	//归并区间[begin,mid]和[mid+1,end]到tmp数组，最后在拷贝回去
	int begin1 = begin, end1 = mid;
	int begin2 = mid+1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];

		}
	}

	//判断那个区间还没有归并完
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}

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

	memcpy(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));

}

//归并排序
void MergeSort(int* arr, int n)
{
    //第三方数组，导致空间复杂度是O(n)
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail");
		return;
	}

	_MergeSort(arr, tmp, 0, n - 1);

	free(tmp);
}