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

数据结构—八大排序_数据结构排序

作者：我家小花儿 | 2024-02-29 05:10:22

赞

踩

数据结构排序

 本文所有排序以升序为例子

目录

一、直接插入排序

二、希尔排序

三、选择排序 ​

四、堆排序

五、冒泡排序

六、快速排序

递归版本

1、hoare版本

2、挖坑法

3、前后指针法（推荐这种写法）

快速排序的优化

1、三数取中法

2、递归到小子区间 

非递归版本

七、归并排序

递归实现：

非递归实现：

八、计数排序 

八大排序的稳定性总结：

一、直接插入排序

基本思想：我们平时玩扑克牌时，摸牌阶段的排序就用到了插入排序的思想

1、当插入第n个元素时，前面的n-1个数已经有序

2、用这第n个数与前面的n-1个数比较，找到要插入的位置，将其插入（原来位置上的数不会被覆盖，因为提前保存了）

3、原来位置上的数据，依次后移

 具体实现：

①单趟的实现（将x插入到 [0,end] 的有序区间）

即一般情况下的插入，我们随机列举了一些数字，待插入的数字分为两种情况

（1）待插入的数字是在前面有序数字的中间数，直接比较将x赋值给end+1位置

（2）x是最小的一个数，end就会到达-1的位置，最后直接将x赋值给end+1位置

 ②整个数组排序的实现 

我们一开始并不知道数组是不是有序的，所以我们控制下标，end从0开始，将end+1位置的值始终保存到x中，循环进行单趟排序即可，最后结束时end=n-2，n-1位置的数字保存到x中

 总体代码：

  1. void InsertSort(int* a, int n)
  2. {
  3. 	assert(a);
  4.  
  5. 	for (int i = 0; i < n - 1; ++i)
  6. 	{
  7. 		int end = i;
  8. 		int x=a[end+1];//将end后面的值保存到x里面了
  9. 		//将x插入到[0，end]的有序区间
  10. 		while (end >= 0)
  11. 		{
  12. 			if (a[end] > x)
  13. 			{
  14. 				a[end + 1] = a[end];  //往后挪动一位
  15. 				--end;
  16. 			}
  17. 			else
  18. 			{
  19. 				break;
  20. 			}
  21. 		}
  22. 		a[end + 1] = x;      //x放的位置都是end的后一个位置
  23. 	}
  24. 	
  25. }

直接插入排序总结：

①元素越接近有序，直接插入排序的效率越高 

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

最坏的情况下，每次插入一个数字，前面的数字都要挪动一下，一共需要挪动1+2+3+……+n=n(n+1)/2 

③空间复杂度：O(1)

没有借助额外的空间，只用到常数个变量

二、希尔排序

 

基本思想：

1、先选定个小于n的数字作为gap，所有距离为gap的数分为一组进行预排序（直接插入排序）

2、再选一个小于gap的数，重复①的操作

3、当gap=1时，相当于整个数组就是一组，再进行一次插入排序即可整体有序

例如： 

具体实现：

①单组排序

和前面的直接插入相同，就是把原来的间隔为1，现在变为gap了，每组分别进行预排序

②多组进行排序

③整个数组进行排序（控制gap）

多次预排序（gap>1）+ 一次插入排序（gap==1）

（1）gap越大，预排越快，越不接近于有序

（2）gap越小，预排越慢，越接近有序

结果就是： 

总体代码：

  1. void ShellSort(int* a, int n)
  2. {
  3.  
  4. 	int gap = n;
  5. 	while (gap > 1)
  6. 	{
  7. 		gap /= 2;
  8.  
  9. 		for (int i = 0; i < n - gap; i++)
  10. 		{
  11. 			int end = i;
  12. 			int x = a[end + gap];
  13. 			while (end >= 0)
  14. 			{
  15. 				if (a[end] > x)
  16. 				{
  17. 					a[end + gap] = a[end];
  18. 					end -= gap;
  19. 				}
  20. 				else
  21. 				{
  22. 					break;
  23. 				}
  24. 			}
  25. 			a[end + gap] = x;
  26. 		}
  27. 	}
  28. }

希尔排序总结：

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

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

③空间复杂度：O(1) 

三、选择排序 

基本思想：

每次从数组中选出最大的或者最小的，存放在数组的最右边或者最左边，直到全部有序 

具体实现：

我们这里进行了优化，一次排序中，直接同时选出最大的数（a[maxi]）和最小的数（a[mini]）放在最右边和最左边，这样排序效率是原来的2倍

①单趟排序

找到最小的数字（a[mini]）和最大的数字（a[maxi]），将他们放在最左边和最右边

ps：其中的begin，end保存记录左右的下标，mini，maxi记录保存最小值和最大值得下标

 ②整个数组排序

begin++和end--这样下次就可以排剩下的n-2个数字，再次进行单趟，如此可构成循环，直到begin小于end

整体代码：

  1. void SelectSort(int* a, int n)
  2. {
  3. 	int begin = 0,end = n - 1;
  4.  
  5. 	while (begin<end)
  6. 	{
  7. 		int mini = begin, maxi = begin;
  8.  
  9. 		for (int i = begin; i <= end; 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. 		Swap(&a[mini], &a[begin]);
  21. 		//当begin==maxi时，最大值会被换走，修正一下
  22. 		if (begin==maxi)
  23. 		{
  24. 			maxi=mini;
  25. 		}
  26. 		Swap(&a[maxi], &a[end]);
  27. 		begin++;
  28. 		end--;
  29. 	}
  30. }

直接选择排序总结：

①直接选择排序很好理解，但实际效率不高，很少使用

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

③空间复杂度：O(1)

四、堆排序

基本思想：

1、将待排序的序列构造成一个大堆，根据大堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；

2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大堆；

3、重复步骤2，如此反复，从第一次构建大堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大堆的尾部。最后，就得到一个有序的序列了。

小结论：

排升序，建大堆

排降序，建小堆

具体实现：、

①向下调整算法

我们将给定的数组序列，建成一个大堆，建堆从根节点开始就需要多次的向下调整算法

堆的向下调整算法（使用前提）：
（1）若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
（2）若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

向下调整算法的基本思想：

1、从根节点开始，选出左右孩子值较大的一个 

2、如果选出的孩子的值大于父亲的值，那么就交换两者的值

3、将大的孩子看做新的父亲，继续向下调整，直到调整到叶子节点为止

  1. //向下调整算法
  2. //以建大堆为例
  3. void AdJustDown(int* a, int n, int parent)
  4. {
  5. 	int child = parent * 2 + 1;
  6. 	//默认左孩子较大
  7. 	while (child < n)
  8. 	{
  9. 		if (child + 1 < n && a[child+1] > a[child ])//如果这里右孩子存在，
  10.                                        //且更大，那么默认较大的孩子就改为右孩子
  11. 		{
  12. 			child++;
  13. 		}
  14. 		if(a[child]>a[parent])
  15. 		{
  16. 			Swap(&a[child], &a[parent]);
  17. 			parent = child;
  18. 			child = parent * 2 + 1;
  19. 		}
  20. 		else
  21. 		{
  22. 			break;
  23. 		}
  24. 	}
  25. }

②建堆（将给定的任意数组建成大堆）

建堆思想：

从倒数第一个非叶子节点开始，从后往前，依次将其作为父亲，依次向下调整，一直调整到根的位置

 建堆图示：

  1. //最后一个叶子结点的父亲为i，从后往前，依次向下调整，直到调到根的位置
  2. for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  3. {
  4. 	AdJustDown(a, n, i);
  5. }

 ③堆排序（利用堆删的思想进行）

堆排序的思想：

1、建好堆之后，将堆顶的数字与最后一个数字交换
2、将最后一个数字不看，剩下的n-1个数字再向下调整成堆再进行第1步

3、直到最后只剩一个数停止，这样就排成有序的了

  1. for (int end = n - 1; end > 0; --end)
  2. {
  3. 	Swap(&a[end], &a[0]);
  4. 	AdJustDown(a, end, 0);
  5. }

整体代码如下：

  1. void AdJustDown(int* a, int n, int parent)
  2. {
  3. 	int child = parent * 2 + 1;
  4. 	
  5. 	while (child < n)
  6. 	{
  7. 		if (child + 1 < n && a[child+1] > a[child ])
  8.                                        
  9. 		{
  10. 			child++;
  11. 		}
  12. 		if(a[child]>a[parent])
  13. 		{
  14. 			Swap(&a[child], &a[parent]);
  15. 			parent = child;
  16. 			child = parent * 2 + 1;
  17. 		}
  18. 		else
  19. 		{
  20. 			break;
  21. 		}
  22. 	}
  23. }
  24.  
  25. //堆排序
  26. void HeapSort(int*a,int n)
  27. {
  28. 	
  29. 	for (int i = (n - 1 - 1) / 2;i>=0;--i)
  30. 	{
  31. 		AdJustDown(a,n,i);
  32. 	}
  33. 	
  34. 	for (int end = n - 1; end > 0; --end)
  35. 	{
  36. 		Swap(&a[end],&a[0]);
  37. 		AdJustDown(a,end,0);
  38. 	}
  39. }

五、冒泡排序

冒泡排序的基本思想：

一趟过程中，前后两个数依次比较，将较大的数字往后推，下一次只需要比较剩下的n-1个数，如此往复 

  1. //优化版本的冒泡排序
  2. void BubbleSort(int* a, int n)
  3. {
  4. 	int end = n-1;
  5. 	while (end>0)
  6. 	{
  7. 		int exchange = 0;
  8. 		for (int i = 0; i < end; i++)
  9. 		{
  10. 			if (a[i] > a[i + 1])
  11. 			{
  12. 				Swap(&a[i], &a[i + 1]);
  13. 				exchange = 1;
  14. 			}
  15. 		}
  16. 		if (exchange == 0)//单趟过程中，若没有交换过，证明已经有序，没有必要再排序
  17. 		{
  18. 			break;
  19. 		}
  20. 		end--;
  21. 	}
  22. }

 冒泡排序总结：

①非常容易理解的排序

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

③空间复杂度:O(1)

六、快速排序

递归版本

1、hoare版本

hoare的单趟思想：

1、左边作key，右边先走找到比key小的值

2、左边后走找到大于key的值

3、然后交换left和right的值

4、一直循环重复上述1 2 3步

5、两者相遇时的位置，与最左边选定的key值交换

这样就让key到达了正确的位置上

动图演示：  

  1. //hoare版本
  2. //单趟排序  让key到正确的位置上   keyi表示key的下标，并不是该位置的值
  3. int partion1(int* a, int left, int right)
  4. {
  5. 	int keyi = left;//左边作keyi
  6. 	while (left < right)
  7. 	{   //右边先走，找小于keyi的值
  8. 		while (left < right && a[right] >= a[keyi])
  9. 		{
  10. 			right--;
  11. 		}
  12. 		//左边后走，找大于keyi的值
  13. 		while (left < right && a[left] <= a[keyi])
  14. 		{
  15. 			left++;
  16. 		}
  17. 		Swap(&a[left], &a[right]);
  18. 	}
  19. 	Swap(&a[left], &a[keyi]);
  20. 	return left;
  21. }
  22.  
  23. void QuickSort(int* a, int left, int right)
  24. {
  25. 	if (left >= right)
  26. 		return;
  27.  
  28. 	int keyi = partion1(a, left, right);
  29. 	//[left,keyi-1] keyi [keyi+1,right]
  30. 	QuickSort(a, left, keyi - 1);
  31. 	QuickSort(a, keyi + 1, right);
  32. }

2、挖坑法

其实本质上是hoare的变形

挖坑法单趟思想：

1、先将最左边第一个数据存放在临时变量key中，形成一个坑位

2、右边先出发找到小于key的值，然后将该值丢到坑中去，此时形成一个新坑位

3、左边后出发找到大于key的值，将该值丢入坑中去，此时又形成一个新的坑位

4、一直循环重复1 2 3步

5、直到两边相遇时，形成一个新的坑，最后将key值丢进去

这样key就到达了正确的位置上了

动图演示： 

  1. //挖坑法
  2. int partion2(int* a, int left, int right)
  3. {
  4. 	int key = a[left];
  5. 	int pit = left;
  6. 	while (left < right)
  7. 	{
  8. 		while (left < right && a[right] >= key)
  9. 		{
  10. 			right--;
  11. 		}
  12. 		a[pit] = a[right];//填坑
  13. 		pit=right;
  14.  
  15.  
  16. 		while (left < right && a[left] <= key)
  17. 		{
  18. 			left++;
  19. 		}
  20. 		a[pit] = a[left];//填坑
  21. 		pit=left;
  22. 	}
  23. 	a[pit] = key;
  24. 	return pit;
  25. }
  26.  
  27. void QuickSort(int* a, int left, int right)
  28. {
  29. 	if (left >= right)
  30. 		return;
  31.  
  32. 	int keyi = partion2(a, left, right);
  33. 	//[left,keyi-1] keyi [keyi+1,right]
  34. 	QuickSort(a, left, keyi - 1);
  35. 	QuickSort(a, keyi + 1, right);
  36. }

3、前后指针法（推荐这种写法）

前后指针的思想：

1、初始时选定prev为序列的开始，cur指针指向prev的后一个位置，同样选择最左边的第一个数字作为key

2、cur先走，找到小于key的值，找到就停下来

3、++prev

4、交换prev和cur为下标的值

5、一直循环重复2 3 4步，停下来后，最后交换key和prev为下标的值

这样key同样到达了正确的位置

动图演示： 

  1. int partion3(int* a, int left, int right)
  2. {
  3. 	int prev = left;
  4. 	int cur = left + 1;
  5. 	int keyi = left;
  6. 	while (cur <= right)
  7. 	{
  8. 		if (a[cur] < a[keyi] && ++prev != cur)//prev != cur  防止cur和prev相等时，相当于自己和自己交换，可以省略
  9. 		{                                   //前置 ++ 的优先级大于 != 不等于的优先级
  10. 			Swap(&a[prev], &a[cur]);
  11. 		}
  12. 		++cur;
  13. 	}
  14. 	Swap(&a[keyi], &a[prev]);
  15. 	return prev;
  16. }
  17.  
  18. void QuickSort(int* a, int left, int right)
  19. {
  20. 	if (left >= right)
  21. 		return;
  22.  
  23. 	int keyi = partion3(a, left, right);
  24. 	//[left,keyi-1] keyi [keyi+1,right]
  25. 	QuickSort(a, left, keyi - 1);
  26. 	QuickSort(a, keyi + 1, right);
  27. }

递归展开图

快速排序的优化

1、三数取中法

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

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

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

  1. //快排的优化
  2. //三数取中法
  3. int GetMidIndex(int* a, int left, int right)
  4. {
  5. 	int mid = (left + right) / 2;
  6. 	
  7. 	if (a[left] < a[right])
  8. 	{
  9. 		if (a[mid] < a[right])
  10. 		{
  11. 			return mid;
  12. 		}
  13. 		else if (a[mid] > a[right])
  14. 		{
  15. 			return right;
  16. 		}
  17. 		else
  18. 		{
  19. 			return left;
  20. 		}
  21. 	}
  22.  
  23. 	else
  24. 	{
  25. 		
  26. 		if (a[mid] > a[left])
  27. 		{
  28. 			return left;
  29. 		}
  30. 		else if (a[mid] < a[right])
  31. 		{
  32. 			return right;
  33. 		}
  34. 		else
  35. 		{
  36. 			return mid;
  37. 		}
  38. 	}
  39.  
  40. }
  41. int partion5(int* a, int left, int right)
  42. {
  43. 	//三数取中,面对有序时是最坏的情况O(N^2)，现在每次选的key都是中间值，变成最好的情况了
  44. 	int midi = GetMidIndex(a, left, right);
  45. 	Swap(&a[midi], &a[left]);//这样还是最左边作为key
  46.  
  47. 	int prev = left;
  48. 	int cur = left + 1;
  49. 	int keyi = left;
  50. 	while (cur <= right)
  51. 	{
  52. 		if (a[cur] < a[keyi] && ++prev != cur)//prev != cur  防止cur和prev相等时，相当于自己和自己交换，可以省略
  53. 		{                                   //前置 ++ 的优先级大于 != 不等于的优先级
  54. 			//++prev;
  55. 			Swap(&a[prev], &a[cur]);
  56. 		}
  57. 		++cur;
  58. 	}
  59. 	Swap(&a[keyi], &a[prev]);
  60. 	return prev;
  61. }

2、递归到小子区间 

随着递归深度的增加，递归次数以每层2倍的速度增加，这对效率有着很大的影响，当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排

我们可以当划分区间长度小于10的时候，用插入排序对剩下的数进行排序

  1. //小区间优化法，可以采用直接插入排序
  2. void QuickSort(int* a, int left, int right)
  3. {
  4. 	if (left >= right)
  5. 		return;
  6.  
  7. 	if (right - left + 1 < 10)
  8. 	{
  9. 		InsertSort(a + left, right - left + 1);
  10. 	}
  11. 	else
  12. 	{
  13. 		int keyi = partion5(a, left, right);
  14. 		//[left,keyi-1] keyi [keyi+1,right]
  15. 		QuickSort(a, left, keyi - 1);
  16. 		QuickSort(a, keyi + 1, right);
  17. 	}
  18. }

非递归版本

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

非递归的基本思想：

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

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

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

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

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

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

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

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

  1. void QuickSortNonR(int* a, int left, int right)
  2. {
  3. 	Stack st;
  4. 	StackInit(&st);
  5. 	StackPush(&st,left);
  6. 	StackPush(&st, right);
  7.  
  8. 	while (!StackEmpty(&st))
  9. 	{
  10. 		int end = StackTop(&st);
  11. 		StackPop(&st);
  12.  
  13. 		int begin = StackTop(&st);
  14. 		StackPop(&st);
  15.  
  16. 		int keyi = partion5(a,begin,end);
  17. 		//区间被成两部分了 [begin,keyi-1] keyi [keyi+1,end]
  18. 		if (keyi + 1 < end)
  19. 		{
  20. 			StackPush(&st,keyi+1);
  21. 			StackPush(&st,end);
  22. 		}
  23. 		if (keyi-1>begin)
  24. 		{
  25. 			StackPush(&st, begin);
  26. 			StackPush(&st, keyi -1);
  27. 		}
  28. 	}
  29. 	StackDestroy(&st);
  30. }

快速排序的总结：

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

②快排唯一死穴，就是排一些有序或者接近有序的序列，例如 2,3,2,3,2,3,2,3这样的序列时，会变成O(N^2)的时间复杂度

③时间复杂度O(N*logN)

④空间复杂度O(logN)

七、归并排序

 归并排序的基本思想（分治思想）：

1、（拆分）将一段数组分为左序列和右序列，让他们两个分别有序，再将左序列细分为左序列和右序列，如此重复该步骤，直到细分到区间不存在或者只有一个数字为止

2、（合并）将第一步得到的数字合并成有序区间

 具体实现：

①拆分

 ②合并

递归实现：

从思想上来说和二叉树很相似，所以我们可以用递归的方法来实现归并排序

代码如下：

  1. void _MergeSort(int* a, int left, int right, int* tmp)
  2. {
  3. 	if (left >= right)
  4. 	{
  5. 		return;
  6. 	}
  7. 	int mid = (left + right) / 2;
  8. 	_MergeSort(a, left, mid, tmp);
  9. 	_MergeSort(a, mid+1, right, tmp);
  10. 	
  11. 	int begin1 = left, end1 = mid;
  12. 	int begin2 = mid + 1, end2 = right;
  13. 	int i = left;
  14. 	while (begin1 <= end1 && begin2 <= end2)
  15. 	{
  16. 		if (a[begin1] < a[begin2])
  17. 		{
  18. 			tmp[i++] = a[begin1++];
  19. 		}
  20. 		else
  21. 		{
  22. 			tmp[i++] = a[begin2++];
  23. 		}
  24. 	}
  25. 	while (begin1 <= end1)
  26. 	{
  27. 		tmp[i++] = a[begin1++];
  28. 	}
  29. 	while (begin2 <= end2)
  30. 	{
  31. 		tmp[i++] = a[begin2++];
  32. 	}
  33. 	for (int j = left; j <= right; j++)
  34. 	{
  35. 		a[j] = tmp[j];
  36. 	}
  37. }
  38. //归并排序
  39. void MergeSort(int* a, int n)
  40. {
  41. 	int* tmp = (int*)malloc(sizeof(int)*n);
  42. 	if (tmp == NULL)
  43. 	{
  44. 		printf("malloc fail\n");
  45. 		exit(-1);
  46. 	}
  47. 	_MergeSort(a,0,n-1,tmp);
  48.  
  49. 	free(tmp);
  50. 	tmp = NULL;
  51. }

非递归实现：

我们知道，递归实现的缺点就是会一直调用栈，而栈内存往往是很小的。所以，我们尝试着用循环的办法去实现

由于我们操纵的是数组的下标，所以我们需要借助数组，来帮我们存储上面递归得到的数组下标，和递归的区别就是，递归要将区间一直细分，要将左区间一直递归划分完了，再递归划分右区间，而借助数组的非递归是一次性就将数据处理完毕，并且每次都将下标拷贝回原数组

归并排序的基本思路是将待排序序列a[0…n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

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

第一种情况：

第二种情况：

代码如下：

  1. void MergeSortNonR(int* a, int n)
  2. {
  3. 	int* tmp = (int*)malloc(sizeof(int)*n);
  4. 	if (tmp == NULL)
  5. 	{
  6. 		printf("malloc fail\n");
  7. 		exit(-1);
  8. 	}
  9.  
  10. 	int gap = 1;
  11. 	while (gap < n)
  12. 	{
  13. 		for (int i = 0; i < n; i += 2 * gap)
  14. 		{
  15. 			// [i,i+gap-1] [i+gap,i+2*gap-1]
  16. 			int begin1 = i, end1 = i + gap - 1;
  17. 			int begin2 = i + gap, end2 = i + 2 * gap - 1;
  18.  
  19. 			// 核心思想：end1、begin2、end2都有可能越界
  20. 			// end1越界 或者 begin2 越界都不需要归并
  21. 			if (end1 >= n || begin2 >= n)
  22. 			{
  23. 				break;
  24. 			}
  25. 			
  26. 			// end2 越界，需要归并，修正end2
  27. 			if (end2 >= n)
  28. 			{
  29. 				end2 = n- 1;
  30. 			}
  31.  
  32. 			int index = i;
  33. 			while (begin1 <= end1 && begin2 <= end2)
  34. 			{
  35. 				if (a[begin1] < a[begin2])
  36. 				{
  37. 					tmp[index++] = a[begin1++];
  38. 				}
  39. 				else
  40. 				{
  41. 					tmp[index++] = a[begin2++];
  42. 				}
  43. 			}
  44.  
  45. 			while (begin1 <= end1)
  46. 			{
  47. 				tmp[index++] = a[begin1++];
  48. 			}
  49.  
  50. 			while (begin2 <= end2)
  51. 			{
  52. 				tmp[index++] = a[begin2++];
  53. 			}
  54.  
  55. 			// 把归并小区间拷贝回原数组
  56. 			for (int j = i; j <= end2; ++j)
  57. 			{
  58. 				a[j] = tmp[j];
  59. 			}
  60. 		}
  61.  
  62. 		gap *= 2;
  63. 	}
  64.  
  65. 	free(tmp);
  66. 	tmp = NULL;
  67. }

归并排序的总结：

①缺点是需要O(N)的空间复杂度，归并排序更多的是解决磁盘外排序的问题

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

③空间复杂度:O(N)

八、计数排序 

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

基本思想：

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

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

具体实现：

①统计相同元素出现的个数

对于给定的任意数组a，我们需要开辟一个计数数组count，a[i]是几，就对count数组下标是几++

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

 ②根据count数组的结果，将数据拷贝回a数组

count[j]中数据是几，说明该数出现了几次，是0就不用拷贝

 代码如下：

  1. void CountSort(int* a, int n)
  2. {
  3. 	int min = a[0], max = a[0];//如果不赋值，min和max就是默认随机值，最好给赋值一个a[0]
  4.  
  5. 	for (int i=1;i<n;i++)//修正 找出A数组中的最大值和最小值
  6. 	{
  7. 		if (a[i] < min)
  8. 		{
  9. 			min=a[i];
  10. 		}
  11. 		if (a[i]>max)
  12. 		{
  13. 			 max=a[i];
  14. 		}
  15. 	}
  16. 	int range = max - min + 1;//控制新开数组的大小，以免空间浪费
  17. 	int* count = (int*)malloc(sizeof(int) * range);
  18. 	memset(count,0, sizeof(int) * range);//初始化为全0
  19. 	if (count==NULL)
  20. 	{
  21. 		printf("malloc fail\n");
  22. 		exit(-1);
  23. 	}
  24.  
  25. 	//1、统计数据个数
  26. 	for (int i=0;i<n;i++)
  27. 	{
  28. 		count[a[i]-min]++;
  29. 	}
  30. 	//2、拷贝回A数组
  31. 	int j = 0;
  32. 	for (int i=0;i<range;i++)
  33. 	{
  34. 		while (count[i]--)
  35. 		{
  36. 			a[j++] = i + min;
  37. 		}
  38. 	}
  39. 	free(count);
  40. 	count = NULL;
  41. }

 计数排序总结：

①在数据范围比较集中时，效率很高，但是使用场景很有限，可以排负数，但对于浮点数无能为力

②时间复杂度：O(MAX(N,range))

③空间复杂度：O(range)

八大排序的稳定性总结：

稳定的排序有：直接插入排序、冒泡排序、归并排序

不稳定的排序有：希尔排序、选择排序、堆排序、快速排序、计数排序

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

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

  

闽ICP备14008679号