devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——八大排序_熟悉线性表、红黑树、哈希表等常见数据结构,以及八种排序算法思想

作者：AllinToyou | 2024-02-29 05:21:01

赞

踩

熟悉线性表、红黑树、哈希表等常见数据结构,以及八种排序算法思想

目录

一、直接插入排序

二、希尔排序

三、选择排序

四、堆排序

五、冒泡排序

六、快速排序

递归版本

1.hoare法

2.挖坑法

3.前后指针法

快排优化版本   

1.三位数取中

2.小区间优化

非递归版本

快排总结

七、归并排序

递归版本

非递归版本

八、计数排序

九、八大排序总结

常见的八大排序算法

一、直接插入排序

1.基本思想

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

2.过程解释

  • 原本数据有序，现在需要往其中加入一个数据，使得加入后的数据依然有序。例如：【3，4，7，14】，现在要将6加入其中。

做法：只需要拿数组依次从后往前跟插入的数字比较，如果插入的数字比原有序数字最后一个的值小，那把最后一个数字往后挪，此时会出现一个空位，当挪到插入的数字放到空位刚好有序时停止，如下图示：

  • 上述情况仅支持其是有序的情况下，如果原本给出的一串数字是无序呢？如何利用插入排序？

做法：解法很简单，既然给定的一串数字是无需的，那就把第一个数字看成有序并用变量tmp将其保存起来，把第二个数字看成是插入进去的数字进行挪动排序覆盖像上文一样，排好了前两个数字，再把第三个数字看成是插入进去的数字进行挪动排序覆盖，此时前三个数字就有序了，依次类推，最终数字均是有序的。

3.代码实现

  1. //直接插入排序
  2. void InsertSort(int* a, int n)
  3. {
  4. 	for (int i = 0; i < n - 1; i++)//注意i的取值范围是[0,n-2]
  5. 	{
  6. 		//[0,end]有序，将end+1位置的值插入到[0，end]中，令[0，end]有序
  7. 		int end = i;
  8. 		int tmp = a[end + 1];//先将要插入的值用tmp存起来
  9. 		while (end >= 0)
  10. 		{
  11. 			if (a[end] > tmp)//升序排列，end>end+1,end处的值往后挪
  12. 			{
  13. 				a[end + 1] = a[end];
  14. 				--end;
  15. 			}
  16. 			else
  17. 				break;//end<tmp跳出循环
  18. 		}
  19. 		a[end + 1] = tmp;//插入数据
  20. 	}
  21. }

4.特性总结

  • 元素集合越接近有序，直接插入排序算法的时间效率越高
  • 时间复杂度：O(N^2)   

           排升序时，逆序情况下时间复杂度最坏。1+2+3+...+n-1。

           排升序时，升序情况下最好，为O(N)。

  • 空间复杂度：O(1)
  • 稳定性：稳定

二、希尔排序

1.基本思想

      希尔排序其实是建立在直接插入排序的基础上进行的优化，希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。
总的来说，可以分为两大部分：

（1）预排序；（分组进行排序，间隔为gap是一组，接近有序）

（2）直接插入排序。

从上图中可以看出：

   希尔排序需要多组预排序，gap由大变小

   gap越大，大的数可以越快到后面，小的树可以越快到前面；

   gap越大，预排序完越不接近有序；

   gap越小，越接近有序；

   gap==1，越接近有序。

2. 代码实现

仅排一次：

  1. void ShellSort(int* a, int n)
  2. {
  3. 	int gap = 3;
  4. 	for (int j = 0; j < gap; j++)
  5. 	{
  6. 		//控制gap组都进行预排序
  7. 		for (int i = j; i < n - gap; i += gap)
  8. 		{
  9. 			//确保一组中的数据都进行插入排序
  10. 			int end = i;
  11. 			//定义一个变量tmp保存end的后一个数,其下标是end+gap
  12. 			int tmp = a[end + gap];
  13. 			while (end >= 0)
  14. 			{
  15. 				if (a[end] > tmp)
  16. 				{
  17. 					a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪
  18. 					end -= gap;
  19. 				}
  20. 				else
  21. 				{
  22. 					break;
  23. 				}
  24. 			}
  25. 			//单趟循环结束或循环中直接break出来均直接赋值
  26. 			a[end + gap] = tmp;
  27. 		}
  28. 	}
  29. }

多组并列排序：

end=0相当于排第一组，i++,end=1相当于排第二组.....,如下面的动图所示（该动图来自三分苦博文）

  1. void SheellSort(int* a, int n)
  2. {
  3. 	int gap=3;//gap=1时就是直接插入排序
  4. 	//把间隔为gap的多组数据同时排
  5. 	for (int i = 0; i < n - gap; i++)
  6. 	{
  7. 		int end=i;
  8. 		int tmp = a[end + gap];
  9. 		while (end >= 0)
  10. 		{
  11. 			if (a[end] > tmp)
  12. 			{
  13. 				a[end + gap] = a[end];
  14. 				end -= gap;
  15. 			}
  16. 			else
  17. 			{
  18. 				break;
  19. 			}
  20. 		}
  21. 		a[end + gap] = tmp;
  22. 	}	
  23. }

gap取值为多少时？最合适

如果gap给小了，并且数组情况最坏是逆序且数组很长，那么大的数想要到后面就要跳很多次，如果gap越小，那么还用希尔排序干啥呢？直接用插入排序（冒泡也不是不行！）综上，我们可以再套一层循环，此循环不光接近gap的问题，还实现了多次预排直至排序结束达到最终效果。

  1. int gap = n;
  2. 	while (gap > 1)
  3. 	{
  4. 		//gap>1时都是预排序，接近有序
  5. 		// gap==1时，就是直接插入排序，有序
  6. 		//要保证gap最后一次取值为1
  7. 		//gap=gap/2;
  8. 		gap = gap / 3 + 1;
  9.  
  10.  
  11.     }

这里我们可以看到这样一个循环，实现了多组预排序直至最终效果，我们控制gap要分类，当gap > 1就继续预排序，当gap == 1就插入排序，而 gap = gap / 3 + 1满足上述要求，或者说gap=n/2，gap/=2;这行代码也可以实现。最终要满足gap==1时实现最终排好序的要求。

希尔排序的最终排序代码如下：

  1. //希尔排序
  2. void SheellSort(int* a, int n)
  3. {
  4. 	int gap = n;
  5. 	while (gap > 1)
  6. 	{
  7. 		//gap>1时都是预排序，接近有序
  8. 		// gap==1时，就是直接插入排序，有序
  9. 		//要保证gap最后一次取值为1
  10. 		//gap=gap/2;
  11. 		gap = gap / 3 + 1;
  12.  
  13. 		//把间隔为gap的多组数据同时排
  14. 		for (int i = 0; i < n - gap; i++)
  15. 		{
  16. 			int end = i;
  17. 			int tmp = a[end + gap];
  18. 			while (end >= 0)
  19. 			{
  20. 				if (a[end] > tmp)
  21. 				{
  22. 					a[end + gap] = a[end];
  23. 					end -= gap;
  24. 				}
  25. 				else
  26. 				{
  27. 					break;
  28. 				}
  29. 			}
  30. 			a[end + gap] = tmp;
  31. 		}
  32. 	}
  33. }

3.希尔排序特性总结

1、希尔排序是对直接插入排序的优化。

2、当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3、稳定性：不稳定

4、时间复杂度分析：

 希尔排序的时间复杂度不是很好算，我们先简要看下预排序的时间复杂度：

  • gap很大时，数据跳的很快，里面套的循环可以忽略不记，差不多是O(N)。
  • gap很小时，数据跳的很慢，很接近有序，差不多也是O(N)

再来看外面套上循环后的时间复杂度：

while循环中的gap = gap / 3 + 1相当于是循环了log3N次

既然外循环执行logN3次，内循环执行N次，那么时间复杂度为O(N∗log3N)。但是上述计算顶多是估算，有人在大量的实验基础上推出其时间复杂度应为：O(N1.3)

三、选择排序

1.基本思想

  • 思想

      遍数组选出最小的放在前面，剩下的数再遍历一遍，再选出小的放前面，以此类推直至遍历完毕排序结束。（选最小的与第一个交换）

  • 例如：如下一组数【3 5 2 7 8 6 1 9 4 0】

      虽说是遍历一遍，选出最小的数放在最前面，但并不是覆盖到最前面，而是进行交换。比如说我遍历了一遍，最小为1，跟第一个9交换，再从剩下的选出最小的2放到第二个位置……

  • 进行优化

    遍历一次，选出两个数，最小的和最大的，最小的放到第一个位置，最大的放到最后一个位置，随后缩小区间，在这个区间内重复上述操作。

  • 演示

2.动态演示

 3.代码实现

  1. //直接插选择排序
  2. void SelsctSort(int* a, int n)
  3. {
  4. 	int left = 0;
  5. 	int right = n - 1;
  6. 	while (left < right)
  7. 	{
  8. 		int mini = left, maxi = left;
  9. 		for (int i = left + 1; i < +right; i++)
  10. 		{
  11. 			if (a[i] < a[mini])
  12. 			{
  13. 				mini=i;//遍历数组，选出最小值的下标
  14. 			}
  15. 			if (a[i] > a[maxi])
  16. 			{
  17. 				maxi = i;//遍历一遍数组，选出最大的下标
  18. 			}
  19. 		}
  20. 		//升序，大值往右边放，小值往左边放
  21. 		Swap(&a[left], &a[mini]);
  22. 		//如果left和maxi重叠，修正maxi
  23. 		if (left == maxi)
  24. 		{
  25. 			maxi = mini;//将maxi换到mini位置
  26. 		}
  27. 		Swap(&a[right], &a[maxi]);
  28. 		//交换结束，缩小区间
  29. 		left++;
  30. 		right--;
  31. 	}
  32. }

4.特性总结

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

四、堆排序

 详细见上篇文章。

主要注意两点：

  • 对数组要向下建堆，时间复杂度小
  • 排升序要建立大堆，升序建立小堆

代码

  1. //交换
  2. void Swap(int* pa, int* pb)
  3. {
  4. 	int tmp = *pa;
  5. 	*pa = *pb;
  6. 	*pb = tmp;
  7. }
  8. //向下调整算法
  9. void AdjustDown(int* a, size_t size, size_t root)
  10. {
  11. 	int parent = (int)root;
  12. 	int child = 2 * parent + 1;
  13. 	while (child < size)
  14. 	{
  15. 		//1、确保child的下标对应的值最大，即取左右孩子较大那个
  16. 		if (child + 1 < size && a[child + 1] > a[child]) //得确保右孩子存在
  17. 		{
  18. 			child++; //此时右孩子大
  19. 		}
  20. 		//2、如果孩子大于父亲则交换，并继续往下调整
  21. 		if (a[child] > a[parent])
  22. 		{
  23. 			Swap(&a[child], &a[parent]);
  24. 			parent = child;
  25. 			child = 2 * parent + 1;
  26. 		}
  27. 		else
  28. 		{
  29. 			break;
  30. 		}
  31. 	}
  32. }
  33. //升序
  34. void HeapSort(int* a, int n)
  35. {
  36. 	//向下调整建堆
  37. 	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  38. 	{
  39. 		AdjustDown(a, n, i);
  40. 	}
  41. 	//大堆升序
  42. 	size_t end = n - 1;
  43. 	while (end > 0)
  44. 	{
  45. 		Swap(&a[0], &a[end]);
  46. 		AdjustDown(a, end, 0);
  47. 		end--;
  48. 	}
  49. }
  50. int main()
  51. {
  52. 	int a[] = { 4,2,7,8,5,1,0,6 };
  53. 	HeapSort(a, sizeof(a) / sizeof(int));
  54. 	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  55. 	{
  56. 		printf("%d ", a[i]);
  57. 	}
  58. 	return 0;
  59. }

特性总结：

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

五、冒泡排序

1. 基本思想：冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

2.步骤

  • 相邻的两个元素比较，大的上浮，小的下沉，这样一趟冒泡排序即可确保大值排列在一端。
  • 确定趟数，趟数为数组总个数-先前排过的趟数。

3.代码实现

  1. //交换
  2. void Swap(int* pa, int* pb)
  3. {
  4. 	int tmp = *pa;
  5. 	*pa = *pb;
  6. 	*pb = tmp;
  7. }
  8. //冒泡排序
  9. void BubbleSort(int* a, int n)
  10. {
  11. 	for (int j = 0; j < n; j++)
  12. 	{
  13. 		//单趟
  14. 		for (int i = 1; i < n - j; i++)
  15. 		{
  16. 			if (a[i - 1] > a[i])
  17. 			{
  18. 				Swap(&a[i], &a[i - 1]);
  19. 			}
  20. 		}
  21. 	}
  22. }

4.优化冒泡排序

根据上述代码，有个缺陷：如果我的数组本身就有序或着说是接近有序，那我还需要每一趟都进去比较相邻两个数字的大小吗？如果每次都要比，那时间复杂度就要提升，为此可以定义一个变量exchange，如果说发生了比较，那么exchange的值保存为1，如果没有比较，则exchange为0，就退出。

5.优化代码

  1. //交换
  2. void Swap(int* pa, int* pb)
  3. {
  4. 	int tmp = *pa;
  5. 	*pa = *pb;
  6. 	*pb = tmp;
  7. }
  8. //冒泡排序
  9. void BubbleSort(int* a, int n)
  10. {
  11. 	for (int j = 0; j < n; j++)
  12. 	{
  13. 		int exchange = 0;
  14. 		//单趟
  15. 		for (int i = 1; i < n - j; i++)
  16. 		{
  17. 			if (a[i - 1] > a[i])
  18. 			{
  19. 				exchange = 1;
  20. 				Swap(&a[i], &a[i - 1]);
  21. 			}
  22. 			if (exchange == 0)
  23. 				break;
  24. 		}
  25. 	}
  26. }

6.特性总结

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

最好情况：数组本身是顺序的，外层循环遍历一次就完成O(N)

最坏情况：数组本身是逆序的，内外层遍历O(N^2)

六、快速排序

递归版本

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

快速排序分为三种方法

  • hoare法
  • 挖坑法
  • 前后指针法

而其又可以使用递归和非递归来实现，接下来我将依次演示：

1.hoare法

hoare法的快排分为以下步骤：

  1. 选出一个key，一般是第一个数，或者是最后一个数
  2. 定义变量L和R，L从左走，R从右走
  3. R先向前走，找到比key小的位置停下，再让L向后走，找到比key大的值停下
  4. 交换L和R代表的数值
  5. 继续遍历，同样让R先走，L后走，同上规则
  6. 当L和R相遇的时候，把相遇位置的值与key位置的值交换，结束

排完一趟要求如下：

  1. 左边的值都比key小
  2. 右边的值都比key大

如何保证相遇位置的值比key小？

       不需要保证，此算法思想（右边先走）足矣解决。本算法思想明确了每次让R先走，R找到比key小的值之后才会停下来，这时候才轮到L走，L要么找不到比key大的值就一直走直至相遇R，此时正好满足小于key，要么L找到比key大，交换L和R的值，但随后，R又会继续向前走，一直走，最坏刚好遇到L，因为L先前和R已经换过一次，也就是说这个L的值一定是比key小的，那么同样交换key的值，综上，此算法思想足矣解决。
如若key为最右边的值呢？

  思想和上面一样，唯一要改变的是此时是L先走，R后走，其余没有变。

单趟排序代码 

  1. //快排单趟排序
  2. int PartSort(int* a, int left, int right)
  3. {
  4. 	int keyi = left; //选左边作key
  5. 	while (left < right)
  6. 	{
  7. 		//右边先走，找小
  8. 		while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left < right
  9. 		{
  10. 			right--;
  11. 		}
  12. 		//右边找到后，左边再走，找大
  13. 		while (left < right && a[left] <= a[keyi]) //同上，也要加上left < right
  14. 		{
  15. 			left++;
  16. 		}
  17. 		//右边找到小，左边找到大，就交换
  18. 		Swap(&a[left], &a[right]);
  19. 	}
  20. 	//此时left和right相遇，交换与key的值
  21. 	Swap(a[keyi], &a[left]);
  22. 	return left;
  23. }

整体排序

进行一次单趟排序后，Key就到了正确的位置，key前面的数均小于key，key后的数均大于key，此时key的位置就是最终排序好后应该在的位置。那么如果左边有序，右边有序，那么整体就有序了，只需要用到递归+分治的思想即可。

画图演示

 整体排序总代码

  1. //hoare
  2. //快排单趟排序
  3. int PartSort(int* a, int left, int right)
  4. {
  5. 	int keyi = left; //选左边作key
  6. 	while (left < right)
  7. 	{
  8. 		//右边先走，找小
  9. 		while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left < right
  10. 		{
  11. 			right--;
  12. 		}
  13. 		//右边找到后，左边再走，找大
  14. 		while (left < right && a[left] <= a[keyi]) //同上，也要加上left < right
  15. 		{
  16. 			left++;
  17. 		}
  18. 		//右边找到小，左边找到大，就交换
  19. 		Swap(&a[left], &a[right]);
  20. 	}
  21. 	//此时left和right相遇，交换与key的值
  22. 	Swap(&a[keyi], &a[left]);
  23. 	return left;
  24. }
  25.  
  26. //快速排序
  27. void QuickSort(int* a, int begin, int end)
  28. {
  29. 	//子区间相等只有一个值或者不存在那么就是递归结束的子问题
  30. 	if (begin >= end)
  31. 	{
  32. 		return;
  33. 	}
  34. 	int keyi = PartSort(a, begin, end);
  35. 	//分成左右两段区间递归
  36. 	// [begin, keyi-1] 和 [keyi+1, end]
  37. 	QuickSort(a, begin, keyi - 1);
  38. 	QuickSort(a, keyi + 1, end);
  39. }

2.挖坑法

挖坑法的步骤如下：

  1. 把最左边的位置用key保存起来，此位置形成坑位
  2. 定义变量L和R分别置于最左和最右
  3. 让R先向前走，找到比key小的位置停下
  4. 找到后，将该值放入坑位，自己形成新的坑位
  5. 再让L向后走，找比key大的位置停下
  6. 找到后，将该值放入坑位，自己形成新的坑位
  7. 再让R走……
  8. 当L和R相遇时，把key的值放到坑位，结束

挖坑法相较于上面的hoare法并没有优化，本质上也没有区别，但是其思想更好理解

  1. 不需要理解为什么最终相遇位置比key小
  2. 不需要理解为什么左边做key，右边先走

总代码如下：

  1. //挖坑法
  2. int PartSort2(int* a, int left, int right)
  3. {
  4. 	//把最左边的值用key保存起来
  5. 	int key = a[left]; 
  6. 	//把left位置设为坑位pit
  7. 	int pit = left;
  8. 	while (left < right) //当left小于right时就继续
  9. 	{
  10. 		//右边先走，找小于key的值
  11. 		while (left < right && a[right] >= key)
  12. 		{
  13. 			right--; //如若right的值>=key的值就继续
  14. 		}
  15. 		//找到小于key的值时就把此位置赋到坑位，并把自己置为新的坑位
  16. 		a[pit] = a[right];
  17. 		pit = right;
  18.  
  19. 		//左边走，找大于key的值
  20. 		while (left < right && a[left] <= key)
  21. 		{
  22. 			left++;
  23. 		}
  24. 		//找到大于key的值就把此位置赋到坑位，并把自己置为新的坑位
  25. 		a[pit] = a[left];
  26. 		pit = left;
  27. 	}
  28. 	//此时L和R相遇，将key赋到坑位
  29. 	a[pit] = key;
  30. 	return pit;
  31. }
  32.  
  33. //快速排序
  34. void QuickSort(int* a, int begin, int end)
  35. {
  36. 	//子区间相等只有一个值或者不存在那么就是递归结束的子问题
  37. 	if (begin >= end)
  38. 	{
  39. 		return;
  40. 	}
  41. 	int keyi = PartSort2(a, begin, end);
  42. 	//分成左右两段区间递归
  43. 	// [begin, keyi-1] 和 [keyi+1, end]
  44. 	QuickSort(a, begin, keyi - 1);
  45. 	QuickSort(a, keyi + 1, end);
  46. }

3.前后指针法

 演示：

 

前后指针法的步骤如下：

  1. 初始时选定prev为序列的开始，cur指针指向prev的后一个位置，同样选择最左边的第一个数字作为key；
  2. cur先走，找到小于key的值，找到就停下来；
  3. ++prev；
  4. 交换prev和cur为下标的值；
  5. 一直循环重复2 3 4步，停下来后，最后交换key和prev为下标的值。

     这样key同样到达了正确的位置。
     总的来说，cur是在找小，找到后就++prev，prev的值无论怎么走都是小于key的值的，当cur找到大与key时，cur的后面紧挨着的prev是小于key的，接下来让cur++到小于key的值，此过程间prev始终不动，唯有cur找到了小于key的值时，让prev再++，此时的prev就是大于key的值了，仔细揣摩这句话，随后交换cur和prev的值，上述操作相当于是把小于key的值甩在左边，大于key的值甩在右边。
总代码：

  1. //前后指针法
  2. int PartSort3(int* a, int left, int right)
  3. {
  4. 	int key = left;//注意不能写成 int key = a[left]
  5. 	int prev = left;
  6. 	int cur = prev + 1;
  7. 	while (cur <= right)
  8. 	{
  9. 		if (a[cur] < a[key] && a[++prev] != a[cur]) 
  10. 		{
  11. 			Swap(&a[prev], &a[cur]);//在cur的值小于key的值的前提下，并且prev后一个值不等于cur的值时交换，避免了交换两个小的（虽然也可以，但是没有意义）
  12. 		}
  13. 		cur++; //如若cur的值大于key，则cur++
  14. 	}
  15. 	Swap(&a[prev], &a[key]); //此时cur越界，直接交换key与prev位置的值
  16. 	return prev;
  17. }
  18.  
  19. //快速排序
  20. void QuickSort(int* a, int begin, int end)
  21. {
  22. 	//子区间相等只有一个值或者不存在那么就是递归结束的子问题
  23. 	if (begin >= end)
  24. 	{
  25. 		return;
  26. 	}
  27. 	int keyi = PartSort2(a, begin, end);
  28. 	//分成左右两段区间递归
  29. 	// [begin, keyi-1] 和 [keyi+1, end]
  30. 	QuickSort(a, begin, keyi - 1);
  31. 	QuickSort(a, keyi + 1, end);
  32. }

如若把key设定为最后一个数据呢？该如何控制？

总的来说有三处发生变动：

  1. cur和prev初始时的位置：先前定义的prev是第一个数据，cur是prev的后一个，而现在，cur是第一个位置，而prev是cur的前一个，相当于是初始时整体后移一位
  2. 停止的条件：原先的cur有效范围是整个数组，现在的cur有效范围是前n-1个数组，省去最后一个定为key的值
  3. 交换与key的值的条件：先前是cur越界时，直接交换prev与key的值，现在是先++prev，再交换与key的值，（因为此时的prev值依旧小于key，要++后才大于key）

除了这三处有所变动外，别的没有什么变动，交换的过程步骤都是一样的。

演示：

代码如下：

  1. //前后指针法key在右边
  2. int PartSort3(int* a, int left, int right)
  3. {
  4. 	int key = right;
  5. //变动1：	int prev = left - 1;  //先前 int prev =left;   int cur = left + 1;
  6. 	int cur = left;
  7. //变动2：	while (cur < right)  //先前 while (cur <= right) 
  8. 	{
  9. 		if (a[cur] < a[key] && a[++prev] != a[cur]) 
  10. 		{
  11. 			Swap(&a[prev], &a[cur]); 
  12. 		}
  13. 		cur++;  
  14. 	}
  15. //变动3：	Swap(&a[++prev], &a[key]); //先前Swap(&a[prev], &a[key]);
  16. 	return prev;
  17. }
  18.  
  19. //快速排序
  20. void QuickSort(int* a, int begin, int end)
  21. {
  22. 	//子区间相等只有一个值或者不存在那么就是递归结束的子问题
  23. 	if (begin >= end)
  24. 	{
  25. 		return;
  26. 	}
  27. 	int keyi = PartSort3(a, begin, end);
  28. 	//分成左右两段区间递归
  29. 	// [begin, keyi-1] 和 [keyi+1, end]
  30. 	QuickSort(a, begin, keyi - 1);
  31. 	QuickSort(a, keyi + 1, end);
  32. }

快排优化版本   

快排的时间复杂度分两种情况讨论：

  1. 最好：每次选key都是中位数，通俗讲是左边一半右边一半，具体看是key的左序列长度和右序列长度相同。时间复杂度O(N*logN)。
  2. 最坏：每次选出最小的或者最大的作为key。时间复杂度O(N^{2}) 。


   当数组是有序或者接近有序时，就是最坏的情况。因此需要对算法进行优化，一般又两种优化方法：三位数取中，小区间优化

1.三位数取中

   快速排序对于数据是敏感的，如果这个序列是非常无序，杂乱无章的，那么快速排序的效率是非常高的，可是如果数列有序，时间复杂度就会从O(N*logN)变为O(N^2)，相当于冒泡排序了。

      若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。 

       但是这是理想情况，当我们面对一组极端情况下的序列，就是有序的数组，选择左边作为key值的话，那么就会退化为O(N^2)的复杂度，所以此时我们选择首位置，尾位置，中间位置的数分别作为三数，选出中间位置的数，放到最左边，这样选key还是从左边开始，这样优化后，全部都变成了理想情况。

三数取中其实针对hoare法，挖坑法，前后指针法都适用，这里以前后指针法示例。

代码实现：

  1. //快排优化————三数取中优化
  2. int GetMidIndex(int* a, int left, int right)
  3. {
  4. 	int mid = (left + right) / 2; // int mid = left + (right - left) / 2
  5. 	// left  mid  right
  6. 	if (a[left] < a[mid])
  7. 	{
  8. 		if (a[mid] < a[right]) // left < mid < right
  9. 			return mid;
  10. 		else if (a[left] < a[right]) // left < right <mid
  11. 			return right;
  12. 		else  // right < left < mid
  13. 			return left; 
  14. 	}
  15. 	else // left > mid
  16. 	{
  17. 		if (a[right] > a[left]) // right > left > mid
  18. 			return left;
  19. 		else if (a[mid] > a[right])// left > mid > right
  20. 			return mid;
  21. 		else // left > right > mid
  22. 			return right;
  23. 	}
  24. }
  25.  
  26. //前后指针法
  27. int PartSort3(int* a, int left, int right)
  28. {
  29. 	//三数取中优化
  30. 	int midi = GetMidIndex(a, left, right);
  31. 	Swap(&a[midi], &a[left]);
  32.  
  33. 	int key = left;//注意不能写成 int key = a[left]
  34. 	int prev = left;
  35. 	int cur = prev + 1;
  36. 	while (cur <= right)
  37. 	{
  38. 		if (a[cur] < a[key] && a[++prev] != a[cur]) 
  39. 		{
  40. 			Swap(&a[prev], &a[cur]); 
  41. 		}
  42. 		cur++;  
  43. 	}
  44. 	Swap(&a[prev], &a[key]);  
  45. 	return prev;
  46. }
  47.  
  48. //快速排序
  49. void QuickSort(int* a, int begin, int end)
  50. {
  51. 	//子区间相等只有一个值或者不存在那么就是递归结束的子问题
  52. 	if (begin >= end)
  53. 	{
  54. 		return;
  55. 	}
  56. 	int keyi = PartSort3(a, begin, end);
  57. 	//分成左右两段区间递归
  58. 	// [begin, keyi-1] 和 [keyi+1, end]
  59. 	QuickSort(a, begin, keyi - 1);
  60. 	QuickSort(a, keyi + 1, end);
  61. }

2.小区间优化

思想：

快排递归调用的简化图其实就类似于一个二叉树，假设长度N为1000，那么递归调用就要走logN层也就是10层，假设其中一个递归到只有5个数了，那么还要递归3次，当然这只是左边的，右边还要递归3次，这么小的一块区间还要递归这么多次，小区间优化就是为了解决这一问题，针对最后的小区间进行其它的算法排序，就比如插入就很可以。

当递归到越小的区间时，递归次数就会越多，针对这一小区间采取插入排序更优，减少了大量的递归次数。

代码实现：

  1. //三数取中优化
  2. int GetMidIndex(int* a, int left, int right)
  3. {
  4.     //……
  5. }
  6.  
  7. //前后指针法
  8. int PartSort3(int* a, int left, int right)
  9. {
  10. 	//三数取中优化
  11. 	int midi = GetMidIndex(a, left, right);
  12. 	Swap(&a[midi], &a[left]);
  13.     //……
  14. }
  15.  
  16. //小区间优化
  17. void QuickSort2(int* a, int begin, int end)
  18. {
  19. 	//子区间相等只有一个值或者不存在那么就是递归结束的子问题
  20. 	if (begin >= end)
  21. 	{
  22. 		return;
  23. 	}
  24. 	//小区间直接插入排序控制有序
  25. 	if (end - begin + 1 <= 10)
  26. 	{
  27. 		InsertSort(a + begin, end - begin + 1);
  28. 	}
  29. 	else
  30. 	{
  31. 		int keyi = PartSort3(a, begin, end);
  32. 		// [begin, keyi-1] 和 [keyi+1, end]
  33. 		QuickSort(a, begin, keyi - 1);
  34. 		QuickSort(a, keyi + 1, end);
  35. 	}
  36. }

非递归版本

      前面快排都是用递归来实现的，但是要知道，递归也是有缺陷的。如果深度过大，可能会导致栈溢出，即使你用了快排优化可能也无法解决此问题，所以我们引出非递归的版本来解决栈溢出问题。

      递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

非递归的基本思想：

1. 申请一个栈，存放排序数组的起始位置和终点位置。

2. 将整个数组的起始位置和终点位置入栈。

3. 由于栈的特性是：后进先出，right后进栈，所以right先出栈。

定义一个end接收栈顶元素，出栈操作、定义一个begin接收栈顶元素，出栈操作。

4. 对数组进行一次单趟排序，返回key关键值的下标。

5. 这时候需要排基准值key左边的序列。

如果只将基准值key左边序列的起始位置和终点位置存入栈中，等左边排序完将找不到后边的区间。所以先将右边序列的起始位置和终点位置存入栈中，再将左边的起始位置和终点位置后存入栈中。

6.判断栈是否为空，若不为空 重复4、5步、若为空则排序完成。
代码实现：

  1. //快排非递归
  2. void QuickSort3(int* a, int begin, int end)
  3. {
  4. 	ST st;
  5. 	StackInit(&st);
  6. 	//先把第一块区间入栈
  7. 	StackPush(&st, begin);
  8. 	StackPush(&st, end);
  9. 	while (!StackEmpty(&st)) //栈不为空就继续
  10. 	{
  11. 		int right = StackTop(&st);
  12. 		StackPop(&st);
  13. 		int left = StackTop(&st);
  14. 		StackPop(&st);
  15.  
  16. 		//使用前后指针法进行排序
  17. 		int keyi = PartSort3(a, left, right); // keyi已经到了正确位置
  18.  
  19. 		// [left, kryi-1]  [keyi+1, right]
  20. 		if (left < keyi - 1)//如若左区间不只一个数就入栈
  21. 		{
  22. 			StackPush(&st, left);
  23. 			StackPush(&st, keyi - 1);
  24. 		}
  25. 		if (keyi + 1 < right)//若右区间不只一个就入栈
  26. 		{
  27. 			StackPush(&st, keyi + 1);
  28. 			StackPush(&st, right);
  29. 		}
  30. 	}
  31. 	StackDestory(&st);
  32. }

快排总结

时间复杂度O(N*logN)

空间复杂度O(logN)

稳定性：不稳定

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

七、归并排序

递归版本

动图演示：

基本思想：

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

假设我们有左右两块有序区间的数组，可以对它直接进行合并。此时我们需要借助第三方数组，一次比较两块区间的起始位置，把小的那个放到新数组，随后依次比较，小的就放新数组，一直到结束。

但是现在存在一个问题？上述条件是假设了左半区间和右半区间有序，但是原先数组是无序的啊，也就是左半区间和右半区间均无序。怎么才能达到左半区间和右半区间有序最后再归并成整体有序呢？这就体现到了分治的思想了，将数组一直分，分到1个1个的，归并成有序变成2个2个的，然后归并成有序成4个4个的，最后再4个4个的归并成有序，最终至整体有序。

画图分析：


递归分解图：

下面为递归分解图，便于理解。

代码实现：

  1. void _MergeSort(int* a, int begin, int end, int* tmp)
  2. {
  3. 	if (begin >= end)
  4. 		return; //区间不存在就返回
  5. 	int mid = (begin + end) / 2;
  6. 	//[begin, mid] [mid+1, end]
  7. 	_MergeSort(a, begin, mid, tmp); //递归左半
  8. 	_MergeSort(a, mid + 1, end, tmp); //递归右半
  9.  
  10. 	//归并[begin, mid] [mid+1, end]
  11. 	//printf("归并[%d,%d][%d,%d]\n", begin, mid, mid + 1, end);
  12. 	int begin1 = begin, end1 = mid;
  13. 	int begin2 = mid + 1, end2 = end;
  14. 	int index = begin;
  15. 	while (begin1 <= end1 && begin2 <= end2)
  16. 	{
  17. 		//将较小的值放到tmp数组里头
  18. 		if (a[begin1] < a[begin2])
  19. 		{
  20. 			tmp[index++] = a[begin1++];
  21. 		}
  22. 		else
  23. 		{
  24. 			tmp[index++] = a[begin2++];
  25. 		}
  26. 	}
  27. 	//如若begin2先走完，把begin1后面的元素拷贝到新数组
  28. 	while (begin1 <= end1)
  29. 	{
  30. 		tmp[index++] = a[begin1++];
  31. 	}
  32. 	//如若begin1先走完，把begin2后面的元素拷贝到新数组
  33. 	while (begin2 <= end2)
  34. 	{
  35. 		tmp[index++] = a[begin2++];
  36. 	}
  37. 	//归并结束后，把tmp数组拷贝到原数组
  38. 	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
  39. }
  40.  
  41. //归并排序
  42. void MergeSort(int* a, int n)
  43. {
  44. 	//malloc一块新数组
  45. 	int* tmp = (int*)malloc(sizeof(int) * n);
  46. 	assert(tmp);
  47. 	_MergeSort(a, 0, n - 1, tmp);
  48. 	free(tmp);
  49. }

非递归版本

思想：

归并的非递归不需要借助栈，直接使用循环即可。递归版中我们是对数组进行划分成最小单位，这里非递归我们直接把它看成最小单位进行归并。我们可以通过控制间距gap来完成。

画图分析：

理想情况下（2的次方数），还有特殊的边界控制，当数据个数不是偶数个时，我们所分的gap组，势必会有越界的地方。有以下三种越界情况。

  1. end1越界
  2. begin2越界
  3. end2越界

需要对三种情况特殊处理。

代码如下：

  1. //归并非递归
  2. void MergeSortNonR(int* a, int n)
  3. {
  4. 	int* tmp = (int*)malloc(sizeof(int) * n);
  5. 	assert(tmp);
  6. 	int gap = 1;
  7. 	while (gap < n)
  8. 	{
  9. 		//分组归并，间距为gap是一组，两两归并
  10. 		for (int i = 0; i < n; i += 2 * gap)
  11. 		{
  12. 			int begin1 = i, end1 = i + gap - 1;
  13. 			int begin2 = i + gap, end2 = i + 2 * gap - 1;
  14. 			//end1越界，修正即可
  15. 			if (end1 >= n)
  16. 			{
  17. 				end1 = n - 1;
  18. 			}
  19. 			//begin2越界，第二个区间不存在
  20. 			if (begin2 >= n)
  21. 			{
  22. 				begin2 = n;
  23. 				end2 = n - 1;
  24. 			}
  25. 			//begin2 ok，end2越界，修正下end2即可
  26. 			if (begin2 < n && end2 >= n)
  27. 			{
  28. 				end2 = n - 1;
  29. 			}
  30. 			printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
  31. 			int index = i;
  32. 			while (begin1 <= end1 && begin2 <= end2)
  33. 			{
  34. 				//将较小的值放到tmp数组里头
  35. 				if (a[begin1] < a[begin2])
  36. 				{
  37. 					tmp[index++] = a[begin1++];
  38. 				}
  39. 				else
  40. 				{
  41. 					tmp[index++] = a[begin2++];
  42. 				}
  43. 			}
  44. 			//如若begin2先走完，把begin1后面的元素拷贝到新数组
  45. 			while (begin1 <= end1)
  46. 			{
  47. 				tmp[index++] = a[begin1++];
  48. 			}
  49. 			//如若begin1先走完，把begin2后面的元素拷贝到新数组
  50. 			while (begin2 <= end2)
  51. 			{
  52. 				tmp[index++] = a[begin2++];
  53. 			}
  54. 		}
  55. 		memcpy(a, tmp, n * sizeof(int));
  56. 		gap *= 2;
  57. 	}
  58. 	free(tmp);
  59. }

特性总结：

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

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

3、空间复杂度：O(N)

4、稳定性：稳定 

在排序中，分为内排序和外排序，简单了解下其概念：

  • 内排序：数据量较少，在内存中进行排序
  • 外排序：数据量很大，在磁盘上进行排序

而我们前面学习的排序中，归并排序既可作为内排序，也可作为外排序，而其它几个排序只能是内排序，这也就说明了在处理数据量很大时，采用归并排序才能解决，其它排序不可。

八、计数排序

动图演示：

基本思想：又叫非比较排序，又称为鸽巢原理，是对哈希直接定址法的变形应用。

1、统计相同元素出现的个数。

2、根据统计的结果，将数据拷贝回原数组。

绝对映射：

       计数的核心步骤就是数组中数字的值是多少，就把该值映射到新开辟数组的下标上。最大数字为10，所以这里我们要开辟11个空间，才能保证数字10放到新数组下标为10的位置，遍历原数组，一个val出现几次，它映射的位置++几次。、

相对映射：

       这里我们用到了绝对映射，即a[i]中的数组元素是几，我们就在count数组下标是几的位置++，但是对于数据比较聚集，不是从较小的数字开始，例如【10000，9999，5000，9999，5000，8888】这样的数据，我们就可以用到相对映射的方法，以免开辟数组空间的浪费，count数组的空间大小我们可以用a数组中最大值减去最小值+1来确定（即：range=max-min+1）,我们可以得到count数组下标 j =a[i]-min。

  • 绝对映射：原数组是几，映射到新数组下标位置++。
  • 相对映射：此时新数组下标的范围是从0到原数组最小的值，而映射到下标的位置为原数组val的值 - 原数组最小min的值。

代码实现：

  1. //计数排序
  2. void CountSort(int* a, int n)
  3. {
  4. 	int min = a[0], max = a[0];
  5. 	//先求出原数组的最大和最小值
  6. 	for (int i = 1; i < n; i++)
  7. 	{
  8. 		if (a[i] < min)
  9. 			min = a[i];
  10. 		if (a[i] > max)
  11. 			max = a[i];
  12. 	}
  13. 	//求出新数组的范围
  14. 	int range = max - min + 1;
  15. 	//开辟新数组
  16. 	int* countA = (int*)malloc(sizeof(int) * range);
  17. 	assert(countA);
  18. 	//把新开辟数组初始化为0
  19. 	memset(countA, 0, sizeof(int) * range);
  20.  
  21. 	//计数
  22. 	for (int i = 0; i < n; i++)
  23. 	{
  24. 		countA[a[i] - min]++; //统计相同元素出现次数（相对映射）
  25. 	}
  26.  
  27. 	//排序
  28. 	int j = 0;
  29. 	for (int i = 0; i < range; i++)
  30. 	{
  31. 		while (countA[i]--)
  32. 		{
  33. 			a[j++] = i + min; //赋值时，记得加回原先的min
  34. 		}
  35. 	}
  36. 	free(countA);
  37. }

特性总结：

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

九、八大排序总结

 

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号