1. Toy模板网首页
  2. > Toy博客

【八大排序】一篇文章搞定所有排序

8月前 作者：戴墨镜的恐龙 分类：Toy博客 阅读(84) 违法举报

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


【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

1.排序的概念

1.1排序的概念

  • 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
  • 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
  • 内部排序：数据元素全部放在内存中的排序。
  • 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2.常见排序算法的实现

2.1 插入排序

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

2.1.1直接插入排序

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];//待排序数据
		while (end >= 0)
		{
			if (tmp < a[end])//将待排序数据前的数据依次与其比较
			{
				a[end + 1] = a[end];//数据后移
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;//将待排序数据放在合适位置
	}
}

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

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

2.1.2希尔排序

  • 希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数作为gap，把待排序数据分成gap组，所有距离为gap的数据分在同一组内，并对每一组内的记录进行排序。然后重新取gap，重复上述分组和排序的工作。当到达gap==1时，所有记录在统一组已内排好序。

  • 希尔排序是对直接插入排序的优化。
    当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，在使用直接插入排序，这样就会很快。这样整体而言，可以达到优化的效果。

  • 在初始时，gap通常选择 n/2 或 n/3+1(n为数据的个数)

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 3 + 1;
		gap = gap / 2;
		//gap趟
		for (int j = 0; j < gap; j++)
		{
			//一趟的
			for (int i = j; i < n - gap; i+=gap)//每次跳跃gap
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}
}

上面的代码可以进行优化，不需要单独排每一趟，直接可将gap趟一次排。

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 3 + 1;
		gap = gap / 2;
		//gap趟一起排
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}

	}
}

希尔排序的特性总结：

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

2.2选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2.1直接选择排序:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void SelectSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int m = i;//记录当前数的下标
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[m])//将当前数与其后的数对比
			{
				m = j;//记录较小值的下标
			}
		}
		//较小值不是当前数，交换
		if (m != i)
		{
			Swap(&a[i], &a[m]);
		}
	}
}

优化：一趟遍历找出最大与最小值。

void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while(left < right)
	{
		int max = left;
		int min = left;
		for (int i = left; i <= right; i++)
		{
			//找最大值
			if (a[i] > a[max])
				max = i;
			//找最小值
			if (a[i] < a[min])
				min = i;
		}
		Swap(&a[min], &a[left]);
		//若最大值在最左侧，其会被换到最小值位置
		if (max == left)
		{
			max = min;
		}
		Swap(&a[max], &a[right]);
		left++;
		right--;
	}
}

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

2.2.2堆排序

堆排序在前面已经写过，点击链接跳转至堆排序

排序的特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

2.3交换排序

  • 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
  • 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

冒泡排序相信大家都非常熟悉了，直接上代码吧。
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

void BubbleSort(int* a, int n)
{
	//进行多少趟比较
	for (int i = 0; i < n - 1; i++)
	{
		//每趟比较的次数
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
		Print(a, n);

	}
}

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

2.3.2快速排序

Hoare法

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
如图所示：
right从右往左找小于key的；left从左往右找大于key的，然后二者交换。继续找，直到二者相遇；相遇以后，需要和key位置数交换，此时key位置的数就处在了排序完成后应该在的位置。
然后再对key位置左边与右边进行上述相同的操作即可完成排序。

为什么二者相遇的位置一定比key小呢？
此处就是该算法的精髓，因为是right先走，right停下来的位置一定比key小，或者right到了key位置。、

void QuickSort(int* a, int left,int right)
{
	//若区间只有一个数，则已经有序
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	int key = left;//基准值
	
	while (left < right)
	{
		//从右往左，找比key位置小的，不小就左移
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		//从左往右，找比key位置大的，不大就右移
		while (left < right && a[left] <= a[key])
		{
			left++;
		}

		//left位置比key大，right位置比key小。交换
		Swap(&a[left], &a[right]);
	}
	//left与right相遇，那就与key交换
	Swap(&a[key], &a[right]);
	key = left;

	//递归左右区间
	//[begin,key-1] key [key+1,end]
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

我们都知道快排很快，它的时间复杂度为O(N*logN)，但真的是这样吗？

思考：若数据有序或已经接近有序，该算法还快吗？
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

如果是这种情况，那么这个基准值每次都会选到最小的值，此时它的时间复杂度就是N^2。那有什么解决办法吗？
使用随机取key法或三数取中法。

  • 随机数选key就是每次选的key都不一定，但有时可以避免最坏情况
	int begin = left;
	int end = right;

	//使随机数的范围再[left,rihgt]中
	int randk = rand() % (right - left);
	randk += left;
	//为了我们后面代码的逻辑不改变，将randk位置与left位置交换
	Swap(&a[left], &a[randk]);

	int key = left;//基准值
  • 三数取中法
    这里的取中并不是取中间的数，而是三个数中，位于中间大小的数。
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] < a[right])
	{
		if (a[mid] > a[left])
		{
			//left < mid < right
			return mid;
		}
		else if (a[left] < a[right])
		{
			//mid < left < right
			return left;
		}
		else
		{	//left < right < mid
			return right;
		}
	}
	else//a[mid] > a[right]
	{
		if (a[mid] < a[left])
		{
			//right < mid < left
			return mid;
		}
		else if (a[left] > a[right])
		{
			//right < left < mid
			return left;
		}
		else
		{
			//left < right < mid
			return right;
		}
	}
}

void QuickSort(int* a, int left,int right)
{
	//若区间只有一个数，则已经有序
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	使随机数的范围再[left,rihgt]中
	//int randk = rand() % (right - left);
	//randk += left;
	为了我们后面代码的逻辑不改变，将randk位置与left位置交换
	//Swap(&a[left], &a[randk]);
	int midk = GetMid(a, left, right);

	Swap(&a[left], &a[midk]);
	int key = left;//基准值
	
	while (left < right)
	{
		//从右往左，找比key位置小的，不小就左移
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		//从左往右，找比key位置大的，不大就右移
		while (left < right && a[left] <= a[key])
		{
			left++;
		}

		//left位置比key大，right位置比key小。交换
		Swap(&a[left], &a[right]);
	}
	//left与right相遇，那就与key交换
	Swap(&a[key], &a[right]);
	key = left;

	//递归左右区间
	//[begin,key-1] key [key+1,end]
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}
  • 小区间优化
    当快排进行到数据元素比较少的时候，使用快速排序走递归的消耗是比较大的，最后一层的递归占整个递归的80%-%90。是不值当的，如下图这种情况：

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
对于这种情况，我们给出小区间优化的方式。即当递归进入待排序数字只剩下10个左右时，直接使用插入排序。

	//小区间优化
	if (right - left + 1 < 10)
	{
		//进行插入排序
		InsertSort(a + left, right - left - 1);
	}
	else
	{
		//继续进行递归
	}

前后指针法

先看一下动图演示
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
此方法与第一种方法不同之处在于，它不是一左一右了。使用前后指针，cur指针为前指针，它找比key小的，找到以后，先让prev++，然后二者在交换，最后自己在++；当cur超出范围时，prev位置小于key，将prev与key交换，本轮排序结束。
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

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

	int prev = left;
	int cur = prev + 1;
	int key = left;

	//当前值比key小，先++prev,然后交换
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	//使key位于正确位置
	Swap(&a[key], &a[prev]);
	key = prev;
	//递归左右区间
	QuickSort2(a, left, key - 1);
	QuickSort2(a, key + 1, right);
}

为了避免自己与自己进行无意义的交换，代码也可以写成这样：

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

	int prev = left;
	int cur = prev + 1;
	int key = left;

	//当前值比key小，先++prev,然后交换
	/*while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}*/
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}

	//使key位于正确位置
	Swap(&a[key], &a[prev]);
	key = prev;
	//递归左右区间
	QuickSort2(a, left, key - 1);
	QuickSort2(a, key + 1, right);
}

挖坑法

挖坑法与Hoare法类似
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
将步骤拆解下来就是下面这样
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int key = a[left];
	int pos = left;//选定坑位
	while (left < right)
	{
		while (left <  right && a[right]>= key)
		{
			right--;
		}

		//从右边找，找到了比key小的，数据变化，坑位变化
		a[pos] = a[right];
		pos = right;//换坑

		while (left < right && a[left] <= key)
		{
			left++;
		}

		//从左边找，找到了比key大的，数据变化，坑位变化
		a[pos] = a[left];
		pos = left;
	}
	//此时left与right相遇
	a[pos] = key;

	//[begin,pos-1] pos [pos+1,end]
	QuickSort3(a, begin, pos - 1);
	QuickSort3(a, pos + 1, end);
}

非递归版本

如果待排序的数据量非常大时，会递归很多次，可能会导致栈溢出，所以非递归版本也是我们必须掌握的。
其实非递归版本也是利用栈后进先出的特性，模拟出的递归的效果。
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);

	//左右区间先入栈
	StackPush(&st, right);
	StackPush(&st, left); 

	//栈不为空，就取栈顶元素排序
	while (!StackEmpty(&st))
	{
		int begin = StackTopElement(&st);
		StackPop(&st);
		int end = StackTopElement(&st);
		StackPop(&st);

		//前后指针法，进行单趟排
		int prev = begin;
		int cur = prev + 1;
		int key = begin;
		while (cur <= end)
		{
			if (a[cur] < a[key] && ++prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
			cur++;
		}
		//使key位于正确位置
		Swap(&a[key], &a[prev]);
		key = prev;

		//[begin,key-1] key [key+1,end]
		//继续入栈,先入右，再入左
		if (key + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, key + 1);
		}
		if (key - 1 > begin)
		{
			StackPush(&st, key - 1);
			StackPush(&st, begin);
		}
	}
	StackDestroy(&st);
}

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

  1. 空间复杂度：O(logN)
  2. 稳定性：不稳定

2.4归并排序

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

归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

  1. 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
  2. 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表

分的过程就是将数据拆到只有一个数据时，此时该数据自身有序。
什么时候就拆好了呢？
当数据的左右边界相等时，就只剩下一个数据，此时可以合并了，如下图：
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
那它的合并又是怎么合的呢？难道在原数组上合并吗？
肯定不是这样的，如果在原数组上合并的话，那数据就乱套了。
因此，我们需要借助一个临时数组来保存数据，待数据合并后，在将临时数组中的数据拷回到原数组中。

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
动图演示：

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

递归版本

#include<string.h>

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	//仅剩下一个数据，自身有序，不在进行递归
	if (begin == end)
		return;

	int mid = (begin + end) / 2;
	//分的过程：递归左右区间，使左右区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	//两区间已经有序，进行合并
	int left1 = begin, right1 = mid;
	int left2 = mid + 1, right2 = end;
	int tmpi = begin;//往tmp数组存放位置的下标

	//两区间均未遍历完
	while (left1 <= right1 && left2 <= right2)
	{
		//按序存放进tmp数组
		if (a[left1] < a[left2])
		{
			tmp[tmpi++] = a[left1++];
		}
		else
		{
			tmp[tmpi++] = a[left2++];
		}
	}
	//有一个遍历完了
	while (left1 <= right1)
	{
		tmp[tmpi++] = a[left1++];
	}
	while (left2 <= right2)
	{
		tmp[tmpi++] = a[left2++];
	}

	//tmp数组中的数据已经有序，拷贝回原数组
	//注意数据拷贝元素的位置
	memcpy(a + begin, tmp + begin, sizeof(int) * (tmpi - begin));
}


void MergeSort(int* a, int n)
{
	//开辟临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

非递归版本

该方法的思想和递归相似。

【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构

void MergeSortNonR(int* a, int n)
{
	//开辟临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1; //最开始为 1个一组,每组均有序

	while (gap < n)
	{
		//gap个分为一组,每次分两组，然后取小进行尾插
		for (int i = 0; i < n; i += 2*gap)
		{
			int left1 = i, right1 = left1 + gap - 1;
			int left2 = left1 + gap, right2 = left2 + gap - 1;

			int tmpi = i;

			while (left1 <= right1 && left2 <= right2)
			{
				//按序存放进tmp数组
				if (a[left1] < a[left2])
				{
					tmp[tmpi++] = a[left1++];
				}
				else
				{
					tmp[tmpi++] = a[left2++];
				}
			}
			//有一个遍历完了
			while (left1 <= right1)
			{
				tmp[tmpi++] = a[left1++];
			}
			while (left2 <= right2)
			{
				tmp[tmpi++] = a[left2++];
			}
			//将临时数组拷回原数组
			memcpy(a + i, tmp + i, sizeof(int) * tmpi - i);
		}
		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}

运行上述代码，我们会发现会出现越界问题
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
我们分析一下：

  • 首先，我们的left1=i，i<n，所以left1不可能越界
  • right1可能越界，如果right1越界那说明数组已经有序了，不需要进行排序
  • left2可能越界，如果right2越界那说明数组也已经有序了，不需要进行排序
  • right2也可能越界，当right2越界时，[left2,未越界] right2，那么我们需要对未越界的部分进行排序。
	if (right1 >= n || left1 >= n)
	{
		break;
	}
	if (right2 >= n)
	{
		right2 = n - 1;
	}

到此，我们的归并排序就算完美了。

void MergeSortNonR(int* a, int n)
{
	//开辟临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1; //最开始为1个一组,每组均有序

	while (gap < n)
	{
		//gap个分为一组,每次分两组
		for (int i = 0; i < n; i += 2*gap)
		{
			int left1 = i, right1 = left1 + gap - 1;
			int left2 = left1 + gap, right2 = left2 + gap - 1;
			//printf("[%d,%d][%d,%d] ", left1, right1, left2, right2);

			//无需再排
			if (right1 >= n || left1 >= n)
			{
				break;
			}
			//部分要排
			if (right2 >= n)
			{
				right2 = n - 1;
			}

			int tmpi = i;

			while (left1 <= right1 && left2 <= right2)
			{
				//按序存放进tmp数组
				if (a[left1] < a[left2])
				{
					tmp[tmpi++] = a[left1++];
				}
				else
				{
					tmp[tmpi++] = a[left2++];
				}
			}
			//有一个遍历完了
			while (left1 <= right1)
			{
				tmp[tmpi++] = a[left1++];
			}
			while (left2 <= right2)
			{
				tmp[tmpi++] = a[left2++];
			}
			//将临时数组拷回原数组
			memcpy(a + i, tmp + i, sizeof(int) * (tmpi - i));
		}
		gap *= 2;
		//printf("\n");
	}

	free(tmp);
	tmp = NULL;
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

2.5计数排序

计数排序属于非比较排序，那什么较非比较排序呢？–排序的关键逻辑不是比较出来的。
那具体是如何实现的呢？

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

动图演示：
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
从图中我们可以看出，它是将数据的个数收集到一个临时数组中，最后根据临时数组的内容有序放回到原数组中。
但我们这个临时数组开多大呢？和原数组一样大吗？那未免有点太浪费了。
我们只需要找出数据中的最大与最小值，数组大小开最大-最小+1就够了。

例如：假设数组元素大小为100-200之间的数据，那就只需要开100+1个空间。 由于数组下标是从0开始的，而我最小的数据是100，那101就越界了，所以我们需要将待排序数据减去所有数组中的最小值再放进临时数组中。

void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	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* tmp = (int*)calloc(range, sizeof(int));
	if (tmp == NULL)
	{
		perror("calloc fail");
		return;
	}

	//统计各数据的个数
	for (int i = 0; i < n; i++)
	{
		tmp[a[i]-min]++;
	}
	
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		//当前数组元素不为0，还有为排序元素
		while (tmp[i]--)
		{
			a[j++] = i + min;
		}
	}
}

计数排序的特性总结：

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(MAX(N,范围))
  3. 空间复杂度：O(范围)
  4. 稳定性：稳定

3.排序的比较

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n2) O(n)（有序） O(n2) O(1) 稳定
简单选择排序 O(n2) O(2) O(n2) O(1) 不稳定
直接插入排序 O(n2) O(n)（有序） O(n2) O(1) 稳定
希尔排序 O(nlogn)~O(n2) O(n1.3) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(nlogn) O(logn)~O(n)（递归） 不稳定
计数排序 O(Max(n,范围)) O(Min(n,范围)) O(Max(n,范围)) O(范围) 不稳定

稳定性：

若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定的都好理解，不稳定的如下：
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构
【八大排序】一篇文章搞定所有排序,数据结构,排序算法,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-845525.html

到了这里，关于【八大排序】一篇文章搞定所有排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 一篇文章搞定克拉美罗界（CRB）

    一篇文章搞定克拉美罗界（CRB）

    二郎最近在研究LBL（长基线）定位，大部分论文都提到了文中算法获得的方差接近CRB，所以自己的算法性能较好。于是二郎就想知道克拉美罗界是什么意思，以及能应用的场景。 1）查文档： 克拉美罗界：为无偏估计量的方差确定一个下界，衡量无偏估计的性能。 无偏估计：

    2024年02月15日
    浏览(53)
  • 一篇文章搞定《APP的启动流程》

    一篇文章搞定《APP的启动流程》

    前面已经铺垫了Binder、Handler、View的绘制流程 那么该来看看APP的启动流程了，是如何启动了我们这些重要的组件 本文会按照步骤和启动需要的成员并附带一点点源码进行讲解。 以了解熟悉启动的流程为主。不会大篇幅的利用源码深入。 本文结构： 1、冷启动、温启动、热启

    2024年02月16日
    浏览(49)
  • 一篇文章搞定《Android权限问题(全版本)》

    一篇文章搞定《Android权限问题(全版本)》

    文章内容如下： 如果你只是想快速的完成你Android权限申请的工作，那么直接上工具PermissionX 如果是想真正的了解Android的权限问题，那么建议你用15分钟通读一下本文。(可以不去实验，收藏以备后用) 首先了解Android版本和SDK的关系，帮助我们分辨后面的权限版本。 其次把最常

    2024年02月03日
    浏览(54)
  • 一篇文章搞定Android权限问题(全版本)

    一篇文章搞定Android权限问题(全版本)

    文章内容如下： 如果你只是想快速的完成你Android权限申请的工作，那么直接上工具PermissionX 如果是想真正的了解Android的权限问题，那么建议你用15分钟通读一下本文。(可以不去实验，收藏以备后用) 首先了解Android版本和SDK的关系，帮助我们分辨后面的权限版本。 其次把最常

    2023年04月20日
    浏览(57)
  • 【Unity】一篇文章搞定AStar（A*）算法

    【Unity】一篇文章搞定AStar（A*）算法

    AStar（A*）算法，是一种在静态网格中求解最短路径直接有效的搜索方法。在游戏开发中，A*算法常应用于部分RPG游戏和策略战棋类游戏。对于Unity开发者来说，掌握A*算法也是十分有必要的。不过在了解A*算法之前，有必要先回顾一下深度优先算法（DFS）、广度优先算法（BFS）

    2024年02月02日
    浏览(58)
  • Spring之AOP（带你一篇文章搞定AOP）

    Spring之AOP（带你一篇文章搞定AOP）

    Spring的核心之一：AOP 用的依赖（包括上篇文章讲诉的IOC依赖）： AOP：面向切面编程。利用 AOP 可以对业务逻辑的各个部分进行隔离，从而使得业务逻辑各部分之间的耦合度降低，提高程序的可重用性，同时提高了开发的效率。通俗来说就是在不修改代码的情况下添加新的功能

    2024年02月16日
    浏览(56)

  • 一篇文章搞定什么是nodeJs它和NPM关系与应用

    现在前端的入门门槛越来越高了，不再是单纯 html+css+js ，各种前端框架 层出不穷，各种ui组件库层出不穷。 模块化，打包化，各种工具库层出不穷，前端变成 大前端 ，甚至前端可以搞定整个项目，通过 node 作为服务端api， 这里我们主角就是 nodeJs javaScript是一门脚本语言，

    2024年02月03日
    浏览(48)
  • 一篇文章搞定《实战中的设计模式之Android版》

    一篇文章搞定《实战中的设计模式之Android版》

    其实大多数可能和我一样，在开发项目的累积经验下，和对设计模式隐约的记忆下。 在开发项目的过程中其实已经使用到了设计模式，但是不能自知。 比如：之前开发的基于AI的一个对话IM，里面涉及到了很多的设计模式。但是都是下意识的去使用，甚至连他是那种设计模式

    2024年02月10日
    浏览(51)
  • OSPF技术连载16：DR和BDR选举机制，一篇文章搞定！

    OSPF技术连载16：DR和BDR选举机制，一篇文章搞定！

    你好，这里是网络技术联盟站。 在计算机网络中，开放最短路径优先（Open Shortest Path First，OSPF）是一种广泛使用的内部网关协议（Interior Gateway Protocol，IGP），用于在大型网络中实现路由选择。在OSPF网络中，当一个OSPF区域内有多个路由器时，为了减少链路状态数据库（Link

    2024年02月07日
    浏览(46)
  • 七大 排序算法(一篇文章梳理)

    七大 排序算法(一篇文章梳理)

    排序算法是计算机科学中不可或缺的一部分，它们在数据处理、数据库管理、搜索引擎、数据分析等多个领域都有广泛的应用。排序算法的主要任务是将一组数据元素按照某种特定的顺序（如升序或降序）进行排列。本文将对一些常见的排序算法进行详细的介绍和分析，包括

    2024年03月08日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包