数据结构八大排序，你掌握了哪几大

发布于：2022-10-29 ⋅ 阅读:(412) ⋅ 点赞:(0)

文章目录

开篇一览

在这里插入图片描述

排序 时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
直接插入排序 O(N2) O(N) O(N2) O(1) 稳定
希尔排序 O(NlogN)~O(N2) O(N1.25) O(N2) O(1) 不稳定
交换排序 O(N2) O(N2) O(N2) O(1) 不稳定
堆排序 O(NlogN) O(NlogN) O(NlogN) O(1) 不稳定
冒泡排序 O(N2) O(N) O(N2) O(1) 稳定
快速排序 O(NlogN) O(NlogN) O(N2) O(logN)~O(N) 不稳定
归并排序 O(NlogN) O(NlogN) O(NlogN) O(N) 稳定
计数排序 O(max(N,范围)) O(max(N,范围)) O(max(N,范围)) O(范围) 不稳定

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。本篇文章都是按升序对8个排序进行讲解。

排序除了复杂度外，还有稳定性。
稳定性：判断待排序数组中相同的值在排序后相对位置是否发生变化，可能变化就不稳定，可以保证不发生变化就是稳定。
在这里插入图片描述

接口

//交换函数
void Swap(int* pa, int* pb);
// 直接插入排序
void InsertSort(int* a, int n);
//希尔排序
void ShellSort(int* a, int n);
//选择排序
void SelectSort(int* a, int n);
//向下调整
void AdjustDown(int* a, int parent, int n);
//堆排序
void HeapSort(int* a, int n);
//冒泡排序
void BubbleSort(int* a, int n);
//快排
void QuickSort(int* a, int left, int right);
//hoare版
int PartSort1(int* a, int left, int right);
//挖坑法
int PartSort2(int* a, int left, int right);
//前后指针版本
int PartSort3(int* a, int left, int right);
//快排非递归
void QuickSortNoR(int* a, int left, int right);
//归并排序
void MerGeSort(int* a, int n);
//归并非递归
void MerGeSortNoR(int* a, int n);
//计数排序
void CountSort(int* a, int n);

直接插入排序

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

单趟排序：
实际上我们玩扑克牌时，就用到了插入排序的思想。想象一下是如何将7插入到已经排好序的这五张牌中的。
在这里插入图片描述数组arr中除最后一个元素arr[i]外已经有序，将有序数组最后一个元素arr[i-1]开始到arr[0]依次与arr[i]比较，遇到比arr[i]大的就右移一格，遇到比arr[i]小的直接将arr[i]插入到该元素后面
在这里插入图片描述

完整过程：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，重复单趟排序直到数组最后一个元素插入后终止
在这里插入图片描述

//将数组a中的n个数据排序
void InsertSort(int* a, int n)
{	
	//有序数组最后位置从0开始，逐渐排好序逐渐增加
	//当插入到最后一个元素时，插入元素下标为n-1
	//所以有序数组最后位置下标要<n-1
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int x = a[end + 1];//插入的值
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
				break;
		}
		//循环终止有两种情况：
		//1.遇到比x小的，直接插入到该元素后面
		//2.end=-1时，直接插入到数组起始位置
		a[end + 1] = x;
	}
}

直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高O(N)，几乎每次只比较一次不用挪动数据（最好情况）
  2. 元素集合接近逆序时最坏情况，时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

希尔排序

希尔排序法又称缩小增量法。在直接插入排序的思想上进行优化，且优化效果十分明显。

基本思想是：先选定一个整数gap，gap每次排序之前都会减小，把待排序文件中所有记录分成gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当gap=1时，所有记录在统一组内排好序。

  1. 当gap>1时进行分组预排，让数组接近有序
  2. gap=1时就是直接插入排序

假设gap=3，数组分成3组（蓝色、红色、粉色三组），距离为3的为一组，按直接插入排序的思想分别对每组比较
ps：10个数时gap初始值一般是取5或4，这里gap只取成了3，进行预排
在这里插入图片描述

//希尔排序
void ShellSort(int* a, int n)
{	
	int gap = n;
	while (gap > 1)
	{	
		//gap常见的两种取值
		//gap /= 2;//gap==1时就是直接插入排序了
		gap = gap / 3 + 1;
		//多组并排
		//类比直接插入排序的思想，直接插入排序的gap=1
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int x = a[end + gap];//直接插入排序是+1，这里是+gap
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;//直接插入排序是-1，这里是-gap
				}
				else
					break;
			}
			a[end + gap] = x;
		}
	}
}

release版本下：排100万个数时，直接插入排序大概花了2分钟，而希尔排序只要0.1秒，希尔排序对直接排序优化效果十分明显
在这里插入图片描述

希尔排序的特性总结：

  1. 希尔排序是对直接插入排序的优化，且优化效果十分明显。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，接近有序时直接插入排序的时间复杂度:O(N)，O(N)级别就是排序的天花板了
  3. gap约大预排越快，但预排后越不接近有序，gap越小预排越慢，但预排后约接近有序，所以需要合理控制好gap。一般取gap=gap/2(最后gap一定会=1)，或是gap=gap/3+1（因为gap/3有可能直接除到0所以要+1）
  4. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，暂时认为是O(n1.25)
  5. 稳定性：不稳定

选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
动图演示每次取的是最小的
在这里插入图片描述还可以优化一下，每次选两个数，一个最大的一个最小的

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void SelectSort(int* a, int n)
{
	int end = n - 1;
	int begin = 0;//一前一后，不断缩小范围
	while (begin < end)
	{	
		int maxi = begin, mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[maxi] < a[i])
				maxi = i;
			if (a[mini] > a[i])
				mini = i;
		}
		//特殊情况
		if (begin == maxi)
			maxi = mini;
		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

特殊情况，begin与maxi咋同一位置，因为我们是先交换begin与mini位置的值，所以maxi位置的值就是最小的，mini位置的值是最大的，所以可以把mini的值为maxi
在这里插入图片描述

直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率很低，实际中很少使用
  2. 时间复杂度：O(N2)（怎么优化都是O(N2）
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

堆排序（重点）

堆排序是选择排序的一种，它是通过堆来进行选择数据。
基本思想：从最后一个非叶子节点开始到根节点依次向下调整

1.排升序建大堆，排降序建小堆。
参考堆删除思想，是将堆顶与堆尾的数据交换后再–size也就pop掉堆顶的元素了，所以只需要保证交换后堆尾的数最大（这样最大的数就在最后），也就是交换之前堆顶的数最大，这就是大堆的结构。所以排升序要建大堆，同理排降序建小堆

2.用向下调整建堆的时间复杂度是O(N)，而用向上调整建堆的时间复杂度是O(NlogN)，所以向下调整建堆更好，同时排序也需要用到向下调整。
单次向下调整时间复杂度O(logN)高度次

我的这篇文章已经详细讲解了堆排序和相关复杂度证明，这里就不在赘述了
堆排序

在这里插入图片描述

堆排序特性总结：

  1. 时间复杂度：O(N*logN)
  2. 空间复杂度：O(1)
  3. 稳定性：不稳定
//向下调整--升序建大堆
void AdjustDown(int* a, int parent, int n)
{	
	int child = parent * 2 + 1;//左孩子
	while (child < n)
	{	
		if (child + 1 < n && a[child + 1] > a[child])
			++child;
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
//堆排序
void HeapSort(int* a, int n)
{	
	int lastparent = (n - 1 - 1) / 2;
	//建大堆，从最后一个非叶子节点开始向下调整--时间复杂度O(N)
	for (int i = lastparent; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}
	//将大数逐渐右移，堆中元素个数逐渐减小
	int end = n - 1;
	while (end > 0)//时间复杂度O(NlogN)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		--end;
	}
}

冒泡排序

冒泡排序相必大家已经很熟悉了，冒泡排序是一种交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
在这里插入图片描述

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{	
		int flag = 1;
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				flag = 0;
			}
		}
		//没有发生交换就证明已经有序了
		if (flag == 1)
			break;
	}
}

冒泡排序的特性总结：

  1. 时间复杂度：O(N^2)
  2. 空间复杂度：O(1)
  3. 稳定性：稳定

对直接插入排序、选择排序、冒泡排序分析：
选排肯定是最差的，每次不管取一个数还是两个数，时间复杂度都是O(N2)，冒泡和直接插入综合而言，直接插入是更优的，因为直接插入排序不需要完整的走完每趟，只要发生就换就会终止，而冒泡是需要一趟走完的

快速排序（重点）

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

hoare版本

hoare版本是Hoare最开始提出的一种版本

单趟排序：

  1. 一般选数组最左边或最右边的值作key。选中间的值操作麻烦，边上的值更好操作

  2. 用left和right分别从数组左右两边向中间遍历数组

  3. 左边left找比key大的值，右边right找比key小的值（等于时不做处理），然后左右值交换

  4. 反复循环，直到left和right相遇时终止

  5. 将相遇位置的值与key交换，这样比key大的值都到右边了，比key小的值都到左边了

选左边的值作key时，右边先走-----相遇时的值比key小
选右边的值作key时，左边先走----相遇时的值比key大
单趟排序后的目标是：左边的值比key小，右边的值比key大

在这里插入图片描述

选左边的值作key时，为什么要让右边的先走？
因为左边是找比key大的值，右边是找比key小的值，相遇前进行最后一次交换后，当前left的值比key小，right的值比key大，如果让左边先走，那么相遇时的值(right所在位置的值)就比key大了，最后与key交换后，最左边的值就比key大了。同理选右边的值作key时，左边先走

int PartSort1(int* a, int left, int right)
{	
	//最左边作key
	int keyi = left;
	while (left < right)
	{
		//右边先走，找比key小的值
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//左边再走，找比key大的值
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	//最后交换key与相遇位置的值
	Swap(&a[keyi], &a[left]);

	return left;
}

整体排序：
第一趟排完后，key的左边都比它小，右边都比它大，这样如果key的左右子区间都有序了，整体也就有序了。采用分治思想，将一个大问题分治成最小子问题，我们分别对[left,key-1]和[key+1,right]排序重复单趟的操作，当区间只有一个值时这个子区间就是有序的了

//快排--前序思想
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = PartSort1(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

快排最好情况：最次从最左边或最右边取的key都是数组的中位数，单趟排序完交换后，key就到数组中间了，类似于叉树结构，单趟时间复杂度O(N)、高度logN，时间复杂度是(NlogN)
在这里插入图片描述快排最坏的情况：当数组接近有序时，最左边的值可能是最小的，选最左边作key，右边先走找比key小的值，那么结束条件就是right一直走到最左边，N*(N-1)*(N-2)…时间复杂度O(N2)。
在这里插入图片描述

解决快排面对有序情况选key的问题：

  • 随机选取key（一切随缘）
  • 三数取中（选出left，mid，right三数中次大的值作key），面对最坏的情况（数组接近有序），仍然可以选到中位数作key，变成最好的情况，这样就解决了快排时数组接近有序的问题
//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left)/ 2;
	if (a[left] > a[mid])
	{
		if (a[left] > a[right])
		{
			if (a[mid] > a[right])
				return mid;
			else
				return right;
		}
		else
			return right;
	}
	else
	{
		if (a[mid] > a[right])
		{
			if (a[left] > a[right])
				return left;
			else
				return right;
		}
		else
			return mid;
	}
}
int PartSort1(int* a, int left, int right)
{	
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	//最左边作key
	int keyi = left;
	while (left < right)
	{
		//右边先走，找比key小的值
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//左边再走，找比key大的值
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	//最后交换key与相遇位置的值
	Swap(&a[keyi], &a[left]);

	return left;
}

挖坑法

挖坑法和hoare版的思想类似

基本思想：

  1. 选一个值作key保存，一般选最左边或最右边作key，并将key所在位置作为初始坑位pit

  2. 选左边作key，右边先走，找比key小的值，并将找到的值填入坑中，然后作为新的坑位

  3. 再让左边走，找比key大的值，并将找到的值填入坑中，然后作为新的坑位

  4. 反复循环，直到left和right相遇时终止

  5. 当left和right相遇时，将最开始保存的值key填入坑位

  6. 此时key的左边都比它小，右边都比它的，在分别对key的左右子区排序，重复上面步骤

在这里插入图片描述

//挖坑法
int PartSort2(int* a, int left, int right)
{	
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int key = a[left];
	int pit = left;
	while (left < right)
	{
		//右边先走，找比key小的值
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[pit] = a[right];//填入坑位
		pit = right;//变成新的坑
		//左边再走，找比key大的值
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[pit] = a[left];//填入坑位
		pit = left;//变成新的坑
	}
	//left和right相遇后，将key填入坑中
	a[pit] = key;
	return pit;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = PartSort2(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

前后指针版本

前后指针版本相必于上面的两个版本要更好理解，快排通常是使用的这个版本实现的

基本思想：

  1. 定义两个指针prev和cur（初始时cur=prev+1）

  2. 一般选数组最左边或最右边的值作key

  3. 选左边作key时
    3.1 prev指向数组第一个数，cur指向数组第二个数
    3.2 cur先走找比key小的值，然后++prev，再交换prev和cur位置的值
    3.3 重复上面操作，直到cur遍历完数组后终止
    3.4 最后交换key与prev位置的值

  4. 选右边作key时
    4.1 cur指向数组第一个数，prev在cur左边一格
    4.2 cur先走找比key小的值，然后++prev，再交换prev和cur位置的值
    4.3 重复上面操作，知道cur遍历完数组后终止
    4.4 最后再++prev，交换key与prev位置的值

  5. 此时key的左边都比它小，右边都比它的，在分别对key的左右子区排序，重复上面步骤

cur把小的值往左边推，prev把大的值往右边推。cur找比key小的，而prev是紧跟着cur或者紧跟着比key大的序列

int PartSort3(int* a, int left, int right)
{	
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	//选最左边作key
	int key = left;
	int prev = left, cur = prev + 1;
	while (cur <= right)
	{
		//cur先走，找比key小的值(prev和cur位置一样时就不用交换了)
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		++cur;
	}
	Swap(&a[prev], &a[key]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = PartSort2(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

动图演示的大致思路和上面类似，只是有细微的差别，取最左边的值作key，初始条件是cur和prev都从第二个元素位置开始，cur找比key小的值且是先交换cur与prev位置的值，再++prev，最后是交换a[keyi]与a[–prev]位置的值
在这里插入图片描述

快排的小区间优化

采用递归实现有一个缺陷：因为每次递归都要建立栈帧，当递归的深度太深时就会栈溢出，快排的子区间划分类似于一颗二叉树结构，如果以满二叉树的高度h为例，总节点个数就是2h-1，而最后一层的节点个数是2h-1，几乎占了树的一半，那么最后一层递归调用的函数几乎占了快排递归调用的一半。
当分割到小区间时，就可以不用递归分割的思路让这段子区间有序，因为子区间是接近有序的，key的左边都比key小，右边都比key大，那么就可以用直接插入排序的非递归代替快排的递归，（对接近有序的数组，直接插入就是O(N))，这样可以有效减少递归调用的次数

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = PartSort3(a, left, right);
	//[left,keyi-1] keyi [keyi+1,right]
	if (right - left < 10)//子区间的数小于11时，用直接插入排序对接近有序的子区间排序
		InsertSort(a + left, right - left + 1);
	else
	{
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

虽然用三数取中解决了对接近有序序列排序的问题，同时小区间优化也大大减少了递归调用的次数，但当序列中都是接近重复的数时，还是无法解决栈溢出问题，且快排时间复杂度是最坏情况O(N2)，这是快排的一个缺陷。所以当序列中的数接近重复时不建议使用快排，用直接插入排序也不错
在这里插入图片描述
当然想要解决栈溢出问题，就需要用非递归实现
在这里插入图片描述

快排的非递归实现

对简单的递归可以直接用循环代替，但是快排的非递归需要借助栈模拟实现。以前后指针版本为例，每次递归调用PartSort3都要建立新的函数栈帧，形参中a的值不变，只有left和right的值在变化，所以我们可以将每次变化的left和right放入栈中，因为栈是先进后出的，也符合递归的思想：不断往下递推再回归。
ps：当然也可以用队列模拟实现，只是过程与递归的过程不同，类似层序遍历的实现思想
在这里插入图片描述由于C语言没有标准模板库，所以需要自己实现一个stack，源码放在文末。

void QuickSortNoR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);//初始化
	//首先就将left和rightpush入栈
	StackPush(&st, left);//left先入后出栈
	StackPush(&st, right);//right后入先出栈
	//只要栈不为空就可以一直循环迭代
	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, begin, end);
		//[begin,keyi-1] keyi [keyi+1,end]
		//先入右区间，后排序，当区间的值只有一个或不存在时就不需要排序了
		if (keyi + 1 < end)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, end);
		}
		//后入左区间，先排序
		if (begin < keyi - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi - 1);
		}
	}
}

快排的特性总结：

  1. 这么多排序只有它才敢叫快排，所以快速排序整体的综合性能和使用场景都是比较好的
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

归并排序（重点）

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

所以归并的前提是两个序列是有序的，实际上在刷链表题的时候就用到了归并的思想
在这里插入图片描述将数组划分为左右区间[left,mid]、[mid+1,right]，然后区间不断划分，直到子区间被划分为只有一个数时，一个数肯定是有序的，然后对有序序列一一合并（下图的6和1合并、2和5合并…）、两两合并（1、6和2、5合并…）四四合并…让整体有序。
在这里插入图片描述在这里插入图片描述

由于链表都是一个一个的节点链接起来的，空间不连续，排序时可以直接链接，而数组是一段连续的空间，对数组排序时，需要借助一个tmp数组，将排序后的子序列保存到tmp数组中，然后在拷贝到原数组。

//借助临时数组tmp对a数组[left,right]区间的数排序
//用子函数_MerGeSort完成归并
void _MerGeSort(int* a, int left, int right, int* tmp)
{	
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	//[left,mid] [mid+1,right]区间不断分解
	_MerGeSort(a, left, mid, tmp);
	_MerGeSort(a, mid + 1, right, tmp);
	//比较后合并到tmp数组
	int i = left;
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//将tmp拷贝到原数组
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}
void MerGeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MerGeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

归并的非递归实现

归并的递归可以直接用循环代替，直接跳到归并部分开始比较
在这里插入图片描述

需要注意边界条件。参考上面的递归，left>=right时就直接return了，所以begin1是不存在越界的，但end1、begin2和end2都可能存在越界
在这里插入图片描述

void MerGeSortNoR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	int grp = 1;//最开始一个数为一组
	while (grp < n)
	{
		for (int i = 0; i < n; i += grp * 2)
		{
			//左区间[i,i+grp-1]  右区间[i+grp,i+grp*2-1]
			int begin1 = i, end1 = i + grp - 1;
			int begin2 = i + grp, end2 = i + grp * 2 - 1;
			int index = begin1;
			//end1越界或者右区间不存在就不需要归并了
			if (end1 >= n || begin2 >= n)
				break;
			if (end2 >= n)//右区间存在仅end2越界，修正下标
				end2 = n - 1;
			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++];
			}
			//将子区间在tmp的数据拷回原数组
			for (int j = i; j <= end2; j++)
			{
				a[j] = tmp[j];
			}
		}
		grp *= 2;
	}

	free(tmp);
	tmp = NULL;
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。所以当数据量特别大存储在文件中，内存中一次性无法加载完时，就可以通过快排和归并配合排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

基本思想：

  1. 采用相对映射
  2. 通过一个count数组统计各元素出现的次数
  3. 根据conunt统计的结果完成排序

在这里插入图片描述

void CountSort(int* a, int n)
{
	int min = INT_MAX, max = INT_MIN;
	//确定数据范围
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);//计数数组
	if (count == NULL)
	{
		perror("malloc failed:");
		exit(-1);
	}
	memset(count, 0, sizeof(int) * range);//初始化为零
	//统计每个数出现的次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;//通过相对映射记录该数出现的次数
	}
	int aindex = 0;
	//通过下标的相对映射和出现的次数写入数组a中
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[aindex++] = i + min;
		}
	}
}

计数排序的特性总结：

  1. 计数排序在数据范围集中时，效率很高。数据很集中时，可以认为时间复杂度O(N)，空间复杂度O(1)。但是适用范围及场景有限，只适合对非负整数排序，如果排序的数都是负数也还行，但有正有负或者是浮点数就不适合了。
  2. 时间复杂度：O(MAX(N,范围))
  3. 空间复杂度：O(范围)
  4. 稳定性：稳定

栈的源码

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int DataType;

typedef struct Stack
{
	DataType* p;
	int top;
	int capacity;
}ST;

//栈初始化
void StackInit(ST* pc);
//压栈
void StackPush(ST* pc, DataType x);
//出栈
void StackPop(ST* pc);
//获取栈顶元素值
DataType StackTop(ST* pc);
//销毁栈
void StackDestroy(ST* pc);
//判断栈是否为空
bool StackEmpty(ST* pc);
//确定栈中元素个数
DataType StackSize(ST* pc);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"
#include "Stack.h"
void StackInit(ST* pc)
{	
	assert(pc);

	pc->capacity = pc->top = 0; //这里top取0，表示栈中元素个数
	pc->p = NULL;
}
void StackPush(ST* pc, DataType x)
{	
	assert(pc);
	//判断是否要扩容
	if (pc->capacity == pc->top)
	{
		int newCapacity = pc->capacity == 0 ? 4 : 2 * pc->capacity;
		DataType* tmp = (DataType*)realloc(pc->p, sizeof(ST) * newCapacity);
		if (tmp == NULL)
		{
			printf("%s\n", strerror(errno));
			exit(-1);
		}
		pc->p = tmp;
		pc->capacity = newCapacity;
	}
	pc->p[pc->top] = x;
	pc->top++;
}
bool StackEmpty(ST* pc)
{
	assert(pc);

	return pc->top == 0;//栈为空返回true非零，不为空返回false零
}
void StackPop(ST* pc)
{
	assert(pc && !StackEmpty(pc));

	pc->top--;
}
DataType StackTop(ST* pc)
{
	assert(pc && !StackEmpty(pc));

	return pc->p[pc->top - 1];
}
DataType StackSize(ST* pc)
{
	assert(pc);

	return pc->top;
}
void StackDestroy(ST* pc)
{	
	assert(pc);

	free(pc->p);
	pc->p = NULL;
	pc->top = pc->capacity = 0;
}

以上就是数据结构常见的八大排序了，希望我的文章对你有所帮助，欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏

在这里插入图片描述

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布