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

数据结构与算法--八大排序_排序算法总结表格

作者：花生_TL007 | 2024-06-17 02:56:28

赞

踩

排序算法总结表格

目录

1.基本概念：

1.排序:

2.需要掌握的点：

3.稳定性：

4.排序难点：

2.分类：

3.比较：

1.稳定性：

2.时间复杂度：

3.空间复杂度：

4.排序详解：

1.选择排序--直接插入排序

1.基本思想：

2.代码实现：

3.小结：

2.插入排序--希尔排序(Insert Sort)

1.基本思想：

2.实现方法：

3.算法实现：

4.代码实现：

5.小结：

3.选择排序-简单选择排序(Simple selection sort)

1.基本思想：

2.实现方法：

3.代码实现：

4.小结：

4.选择排序-堆排序(Heap sort)

1.基本思想：

2.实现方法：

3.算法实现：

4.代码实现：

5.小结：

5.交换排序-冒泡排序(Bubble Sort)

1.基本思想：

2.代码实现：

3.小结：

6.交换排序-快速排序(Quick-Sort)

1.基本思想：

2.代码实现：

3.小结：

7.归并排序-(Merge sort)

1.基本思想：

​2.代码实现

3.小结：

8. 基数排序(Radix Sort)

1.基本思想：

2.代码实现：

3.小结：

5.总结：

 

 

1.基本概念：

1.排序:

把无序的数据变得有序,默认升序.笔试面试排名第一的内容

2.需要掌握的点：

1.算法描述;2.能实现;3.时间复杂度,空间复杂度以及稳定性;4.优缺点

3.稳定性：

对于关键字一样的数据假如A和A',在排序前A在A'的前面,排序后如果能保证A还在A'的前面那么这个算法稳定,否则不稳定
注意:稳定性是针对算法,不针对一次具体的实现.
判断稳定性简单的方法:是否有跳跃的交换数据,如果有则不稳定,没有则稳定

4.排序难点：

算法多,容易混淆

2.分类：

排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

8cf9204f62d24f9992b5f4a9abb102a2.png

3.比较：

1.稳定性：

稳定：直接插入排序；冒泡排序；归并排序；基数排序
不稳定：希尔排序；直接选择排序；堆排序；快速排序

2.时间复杂度：

如下表:

5f4f69afe95f4b54af8ac386a053a327.png

3.空间复杂度：

 O(1):直接插入排序；冒泡排序；归并排序；希尔排序；直接选择排序；堆排序；

 

4.排序详解：

1.选择排序--直接插入排序

1.基本思想：

 在一个有序数组里面h2插入一个数据X,通过遍历比较找到位置,再把后面数据向后移动,把X插入到数组中,数组元素加一(插入单个数据)；(对数组进行排序),设立一个临时变量存储作为临时存储和判断数组边界之用,将序列第一个元素当成是有序的,然后从第2个记录逐个进行插入，直至整个序列有序为止。
b2c43f3e2f374adba4cffbb098ddc08b.gif

相当于扑克牌
从当前位置开始, 从后往前找比当前数字小的, 找到后插入到这个小的数字后面;
在找的过程中, 如果发现一个比当前数字大, 同时将这个数字往后挪;

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

2.代码实现：

  1. void InsertSort(int* arr, int len)
  2. {
  3. 	int tmp;
  4. 	int j;
  5. 	for (int i = 1; i < len; i++)
  6. 	{
  7. 		tmp = arr[i];
  8. 		for (j = i - 1; j >= 0; j--)
  9. 		{
  10. 			if (arr[j] > tmp)
  11. 				arr[j + 1] = arr[j];
  12. 			else
  13. 				break;
  14. 		}
  15. 		arr[j + 1] = tmp;
  16. 	}
  17. }
  18.  
  19. void Show(int* arr, int len)
  20. {
  21. 	for (int i = 0; i < len; i++)
  22. 	{
  23. 		printf("%d ", arr[i]);
  24. 	}
  25. 	printf("\n");
  26. }
  27.  
  28. int main()
  29. {
  30. 	int arr[] = {4,6,8,9,2,34,56,7,12,66,99,36,87};
  31. 	InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
  32. 	
  33. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  34. 	return 0;
  35. }

void InsertSort(int* arr, int len)//O(n^2),最好的情况,O(1),
int tmp;//存放当前处理的数字
int j;//比较数字
for (int i = 1; i < len; i++)//从第二个数字开始
for (j = i - 1; j >= 0; j--)//从后往前找第一个比tmp小的数字
if (arr[j] > tmp)//arr[j]需要后移
arr[j + 1] = arr[j];
else  break;//比当前最大的都大则不需要移动
arr[j + 1] = tmp;//直接放在最后
f5963a95dabc4acaaed1e835ca8c912e.png

 

3.小结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2.时间复杂度:O(n ^ 2)(情况最差时, 即逆序转有序, 最好为O(n));
3.空间复杂度:O(1);
4.稳定

2.插入排序--希尔排序(Insert Sort)

1.基本思想：

先将整个数组分成若干个子数组,通过对子数组进行排序,达到数组"基本有序",再对整个数组进行插入排序,即可达到有序.

2.实现方法：

1.先分组,间隔为Gap的数据为一组,然后对这组数据进行排序,再分组,再排,直到数组被分完.

2.然后再把Gap减小,继续分组,排序.

3.此时数组基本有序,然后将最后Gap设为1,即进行直接插入排序,得到有序数组

c95bf0f573f940dc8dc69ae950d942cd.gif

3.算法实现：

先简单处理增量序列:增量序列gap=(gap/3+1),gap为要排序的数组数据个数。即：先将要排序的一组记录按某个增量gap（gap/3,gap为要排序数的个数）分成若干组子序列，每组中记录的下标相差gap/3.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（gap/3）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

希尔排序可以认为是插入排序的优化。

1450a3d06ca9417d90ecc42d120b324b.png

 

4.代码实现：

  1. void Shell(int* arr, int len, int gap)
  2. {
  3. 	int tmp;
  4. 	int j;
  5. 	for (int i = gap; i < len; i++)
  6. 	{
  7. 		tmp = arr[i];
  8. 		for (j = i - gap; j >= 0; j -= gap)
  9. 		{
  10. 			if (arr[j] > tmp)
  11. 				arr[j + gap] = arr[j];
  12. 			else
  13. 				break;
  14. 		}
  15. 		arr[j + gap] = tmp;
  16. 	}
  17. }
  18.  
  19.  
  20. void ShellSort(int* arr, int len)//O(n^1.3~n^1.5),O(1),不稳定
  21. {
  22. 	int d[] = { 5,3,1 };
  23. 	for (int i = 0; i < sizeof(d) / sizeof(d[0]); i++)
  24. 	{
  25. 		Shell(arr, len, d[i]);
  26. 	}
  27. }
  28.  
  29. void Show(int* arr, int len)
  30. {
  31. 	for (int i = 0; i < len; i++)
  32. 	{
  33. 		printf("%d ", arr[i]);
  34. 	}
  35. 	printf("\n");
  36. }
  37.  
  38. int main()
  39. {
  40. 	int arr[] = { 4,6,8,9,2,34,56,7,12,66,99,36,87 };
  41. 	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
  42. 	
  43. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  44. 	return 0;
  45. }

void Shell(int* arr, int len, int gap)//gap:分组数
void ShellSort(int* arr, int len)//O(n^1.3~n^1.5),O(1),不稳定
int d[] = { 5,3,1 };//分组组数,注意最后一定是1.缩小增量
893b1731edfd47fc95094ad66665cbef.png

 

5.小结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N^2）
4. 稳定性：不稳定

3.选择排序-简单选择排序(Simple selection sort)

 

1.基本思想：

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

2.实现方法：

1.在数组[0,n]中选取最小的数,
2.交换数据,最小数放在左边,
3.在[1,n-1]再次选取,交换,缩减,直到集合剩一个元素

8806d0a8c03843819dd4f0c738686525.gif

 

3.代码实现：

  1. void SelectSort(int* arr, int len)
  2. {
  3. 	int minIndex;
  4. 	int  tmp;
  5. 	for (int i = 0; i < len - 1; i++)
  6. 	{
  7. 		minIndex = i;
  8. 		for (int j = i + 1; j < len; j++)
  9. 		{
  10. 			if (arr[minIndex] > arr[j])
  11. 			{
  12. 				minIndex = j;
  13. 			}
  14. 		}
  15. 		if (minIndex != i)
  16. 		{
  17. 			tmp = arr[minIndex];
  18. 			arr[minIndex] = arr[i];
  19. 			arr[i] = tmp;
  20. 		}
  21. 	}
  22. }
  23. void Show(int* arr, int len)
  24. {
  25. 	for (int i = 0; i < len; i++)
  26. 	{
  27. 		printf("%d ", arr[i]);
  28. 	}
  29. 	printf("\n");
  30. }
  31. }
  32. int main()
  33. {
  34. 	int arr[] = { 4,6,8,9,2,34,56,7,12,66,99,36,87 };
  35. 	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
  36. 	
  37. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  38. 	return 0;
  39. }

void SelectSort(int* arr, int len)//O(n^2),O(1),不稳定
int minIndex;//最小值的下标;
        for (int j = i + 1; j < len; j++)//找最小值
        //最小值和待排序的第一个值交换
        if (minIndex != i)
        {
            tmp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = tmp;
        }

96bb701c852c431591c34783b8f7baf8.png

 

4.小结：

1.容易理解,但是效率太低,实际当中不太使用
2.时间复杂度O(n^2),空间复杂度O(1);
3.不稳定

4.选择排序-堆排序(Heap sort)

 

1.基本思想：

堆排序(HeaoSort)是基于数据结构堆设计的一种排序算法,通过堆来选择数据,向上(向下)调整,得到小数(大数),然后再与堆底数据进行交换,即可排序,需要注意的是排升序建大堆,排降序建小堆

2.实现方法：

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

3.算法实现：

1. 建大堆, 把根交换到最底, 然后在减一个元素继续调整
2. 向下调整, 继续交换, 直到最后一个元素

c725224013824f92808321fcf0b89259.gif

 

4.代码实现：

  1. void  HeapAdjust(int* arr, int start, int end)//O(logn)
  2. {
  3. 	int  tmp = arr[start];
  4. 	for (int i = 2 * start + 1; i <= end; i = 2 * i + 1)
  5. 	{
  6. 		if (i < end && arr[i] < arr[i + 1])//有右孩子,并且左孩子的值小于右孩子
  7. 		{
  8. 			i++;
  9. 		}//i一定是左右孩子的最大值
  10.  
  11. 		if (arr[i] > tmp)
  12. 		{
  13. 			arr[start] = arr[i];
  14. 			start = i;
  15. 		}
  16. 		else
  17. 		{
  18. 			break;
  19. 		}
  20. 	}
  21. 	arr[start] = tmp;
  22. }
  23.  
  24. void  HeapSort(int* arr, int len)//O(nlogn),O(1),不稳定
  25. {
  26. 	//第一次建立大根堆,从后往前,多次调整
  27. 	int i;
  28. 	for (i = (len - 1 - 1) / 2; i >= 0; i--)//从最后一棵子树开始,O(nlogn)
  29. 	{
  30. 		HeapAdjust(arr, i, len - 1);
  31. 	}
  32. 	//每次将根和待排序的最后一个交换,然后再调整
  33. 	int  tmp;
  34. 	for (i = 0; i < len - 1; i++)//O(nlogn)
  35. 	{
  36. 		tmp = arr[0];
  37. 		arr[0] = arr[len - 1 - i];
  38. 		arr[len - 1 - i] = tmp;
  39.  
  40. 		HeapAdjust(arr, 0, len - 1 - i - 1);
  41. 	}
  42. }
  43. void Show(int* arr, int len)
  44. {
  45. 	for (int i = 0; i < len; i++)
  46. 	{
  47. 		printf("%d ", arr[i]);
  48. 	}
  49. 	printf("\n");
  50. }
  51. int main()
  52. {
  53. 	int arr[] = { 4,6,8,9,2,34,56,7,12,66,99,36,87 };
  54. 	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
  55. 	
  56. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  57. 	return 0;
  58. }

父--->子:i--->2*i+1,2*i+2;
子--->父:i---->(i-1)/2

if (i < end && arr[i] < arr[i + 1])//有右孩子,并且左孩子的值小于右孩子

9aa568c2e9a64d98b85fffd1517929f8.png

5.小结：

1.堆排序用来选数,效率就高了很多
2.时间复杂度O(n*logn),空间复杂度O(1);
3.不稳定

5.交换排序-冒泡排序(Bubble Sort)

 

1.基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

e7681e64d4864592847843a142c36b84.gif

2.代码实现：

  1. void   BubbleSort(int* arr, int len)
  2. {
  3. 	int tmp;
  4. 	for (int i = 0; i < len - 1; i++)
  5. 	{
  6. 		for (int j = 0; j + 1 < len - i; j++)
  7. 		{
  8. 			if (arr[j] > arr[j + 1])
  9. 			{
  10. 				tmp = arr[j];
  11. 				arr[j] = arr[j + 1];
  12. 				arr[j + 1] = tmp;
  13. 			}
  14. 		}
  15. 	}
  16. }
  17.  
  18. void Show(int* arr, int len)
  19. {
  20. 	for (int i = 0; i < len; i++)
  21. 	{
  22. 		printf("%d ", arr[i]);
  23. 	}
  24. 	printf("\n");
  25. }
  26. int main()
  27. {
  28. 	int arr[] = { 4,6,8,9,2,34,56,7,12,66,99,36,87 };
  29. 	BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
  30. 	
  31. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  32. 	return 0;
  33. }

void   BubbleSort(int* arr, int len)//O(n^2),O(1),稳定
for (int i = 0; i < len - 1; i++)//趟数

3.小结：

1.容易理解
2.时间复杂度O(n^2),空间复杂度O(1)
3.稳定

6.交换排序-快速排序(Quick-Sort)

 

1.基本思想：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止,类似于树形结构,每次排序把Key值放到应在的位置.

将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本：

Hoare版本(左右指针)

左边值设为key,然后右边先走,找小的,比key小,然后左边走找比key大,然后交换左边右边,

270c30808b7c46fba7d0c8072173fd8c.gif

2. 挖坑法：

其设定key数组第一个值为坑,右边找下,左边找大,找到一个,交换,形成新的坑,最后把key放到坑里。

bf537c7c893241969088f4727bb5a166.gif
3. 前后指针版本

 选取key值,cur小于key值,prev++,交换cur与prev值,

bdc3f15c449349ff822f354cda3cec55.gif

2.代码实现：

1. hoare版本：

  1. int  Partition(int* arr, int low, int high)//O(n),O(1)
  2. {
  3. 	int tmp = arr[low];//基准
  4. 	while (low < high)
  5. 	{
  6. 		//从后往前找比基准小的数字,往前移动
  7. 		while (low<high && arr[high] > tmp)
  8. 		{
  9. 			high--;
  10. 		}
  11. 		if (low < high)
  12. 		{
  13. 			arr[low] = arr[high];
  14. 		}
  15. 		//从前往后找比基准大的数据,往后移动
  16. 		while (low < high && arr[low] <= tmp)
  17. 		{
  18. 			low++;
  19. 		}
  20. 		if (low < high)
  21. 		{
  22. 			arr[high] = arr[low];
  23. 		}
  24. 	}
  25. 	arr[low] = tmp;
  26. 	return low;
  27. }
  28.  
  29. void  Quick(int* arr, int low, int high)//O(nlogn),O(logn),不稳定
  30. {
  31. 	int  par = Partition(arr, low, high);
  32. 	if (low < par - 1)//左边数据超过一个
  33. 	{
  34. 		Quick(arr, low, par - 1);
  35. 	}
  36. 	if (par + 1 < high)
  37. 	{
  38. 		Quick(arr, par + 1, high);
  39. 	}
  40. }
  41. void QuickSort(int* arr, int len)
  42. {
  43. 	Quick(arr, 0, len - 1);
  44. }
  45. void Show(int* arr, int len)
  46. {
  47. 	for (int i = 0; i < len; i++)
  48. 	{
  49. 		printf("%d ", arr[i]);
  50. 	}
  51. 	printf("\n");
  52. }
  53. int main()
  54. {
  55. 	int arr[] = { 4,6,8,9,2,34,56,7,12,66,99,36,87 };
  56. 	QuickSort(arr, sizeof(arr) / sizeof(arr[0]));
  57.  
  58. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  59. 	return 0;
  60. }

5bfb5760c6e940a9b2c195cc8dbd387d.png

 2.挖坑法：

  1. int PartSort2(int* a, int left, int right)
  2. {
  3. 	int key = a[left];
  4. 	while (left < right)
  5. 	{
  6. 		//找小的 
  7. 		while (left < right && a[right] >= key)
  8. 		{
  9. 			--right;
  10. 		}
  11. 		a[left] = a[right];//找到小值,放到坑里,形成新的坑 
  12. 		while (left < right && a[left] <= key)
  13. 		{
  14. 			++left;
  15. 		}
  16. 		a[right] = a[left];//找到大值,放到坑里,形成新的坑 
  17. 	}
  18. 	a[left] = key;//把key放到数组中属于它的位置,左边所有值小于它,右边所有值大于它, 
  19. 	return left; //返回left,分组处理数据 
  20.  
  21. }
  22.  
  23.  
  24. void QuickSort(int* a, int left, int right)//快排 
  25. {
  26. 	if (left >= right)
  27. 	{
  28. 		return;
  29. 	}
  30. 	int key = PartSort2(a, left, right);
  31. 	// [begin, keyi-1] keyi [keyi+1, end]
  32. 	//类似于二叉树 
  33. 	QuickSort(a, left, key - 1);//递归对左数组排序 
  34. 	QuickSort(a, key + 1, right);//递归对右数组排序 
  35. }
  36.  
  37.  
  38. void Show(int* arr, int len)
  39. {
  40. 	for (int i = 0; i < len; i++)
  41. 	{
  42. 		printf("%d ", arr[i]);
  43. 	}
  44. 	printf("\n");
  45. }
  46. int main()
  47. {
  48. 	int arr[] = { 4,6,8,9,2,34,56,7,12,66,99,36,87 };
  49. 	QuickSort(arr, 0,sizeof(arr) / sizeof(arr[0])-1);
  50.  
  51. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  52. 	return 0;
  53. }

0a74e1c457ad40cc859de1b17ba1c556.png

 

3.前后指针法

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5. int PartSort3(int* a, int left, int right)
  6. {
  7. 	int keyi = left;
  8. 	int cur = left + 1;
  9. 	int prev = left;
  10. 	while (cur <= right)
  11. 	{
  12. 		if (a[cur] < a[keyi] && ++prev != cur)//判断cur与key的值,并且防止自己与自己交换
  13. 		{
  14. 			swap(&a[cur], &a[prev]);
  15. 		}
  16. 		++cur;
  17. 	}
  18. 	swap(&a[keyi], &a[prev]);
  19. 	return prev;
  20. }
  21.  
  22.  
  23. void QuickSort(int* a, int left, int right)//快排 
  24. {
  25. 	if (left >= right)
  26. 	{
  27. 		return;
  28. 	}
  29. 	int key = PartSort3(a, left, right);
  30. 	// [begin, keyi-1] keyi [keyi+1, end]
  31. 	//类似于二叉树 
  32. 	QuickSort(a, left, key - 1);//递归对左数组排序 
  33. 	QuickSort(a, key + 1, right);//递归对右数组排序 
  34. }

3.小结：

1.快速排序整体的综合性能和使用场景都是比较好的
2.时间复杂度:O(N*logN)
3.空间复杂度:O(N*logN
4.不稳定

7.归并排序-(Merge sort)

 

1.基本思想：

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

89a191e09b1840e288abfa3becf490fb.gif
2.代码实现：

  1. static  void   Merge(int* arr, int len, int gap)//O(n)
  2. {
  3. 	int low1 = 0;//第一个归并段的起始下标;
  4. 	int high1 = low1 + gap - 1;//第一个归并段的结束下标;
  5. 	int  low2 = high1 + 1;//第二个归并段的起始下标;
  6. 	int  high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;
  7. 	int* brr = (int*)malloc(len * sizeof(int));//存放归并好的数据;
  8. 	int i = 0;//brr的下标;
  9. 	assert(brr != NULL);
  10. 	//1.有两个归并段
  11. 	while (low2 < len)
  12. 	{
  13. 		//两个归并段都还有数据,需要比
  14. 		while (low1 <= high1 && low2 <= high2)
  15. 		{
  16. 			if (arr[low1] <= arr[low2])
  17. 			{
  18. 				brr[i++] = arr[low1++];
  19. 			}
  20. 			else
  21. 			{
  22. 				brr[i++] = arr[low2++];
  23. 			}
  24. 		}
  25. 		//一个归并段的数据已经完成了,另一个还有数据
  26. 		while (low1 <= high1)
  27. 		{
  28. 			brr[i++] = arr[low1++];
  29. 		}
  30. 		while (low2 <= high2)
  31. 		{
  32. 			brr[i++] = arr[low2++];
  33. 		}
  34. 		//下两个归并段
  35. 		low1 = high2 + 1;
  36. 		high1 = low1 + gap - 1;
  37. 		low2 = high1 + 1;
  38. 		high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;
  39. 	}
  40. 	//2.只有一个归并段
  41. 	while (low1 < len)
  42. 	{
  43. 		brr[i++] = arr[low1++];
  44. 	}
  45. 	//3.将归并好的数据拷贝到arr中
  46. 	for (i = 0; i < len; i++)
  47. 	{
  48. 		arr[i] = brr[i];
  49. 	}
  50.  
  51. 	free(brr);//不要忘记
  52. }
  53.  
  54.  
  55. void  MergeSort(int* arr, int len)//O(nlogn),O(n),稳定
  56. {
  57. 	for (int i = 1; i < len; i *= 2)//O(log n )
  58. 	{
  59. 		Merge(arr, len, i);
  60. 	}
  61. }
  62.  
  63. void Show(int* arr, int len)
  64. {
  65. 	for (int i = 0; i < len; i++)
  66. 	{
  67. 		printf("%d ", arr[i]);
  68. 	}
  69. 	printf("\n");
  70. }
  71. int main()
  72. {
  73. 	int arr[] = { 8,6,2,3,1,5,7,4};
  74. 	MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
  75.  
  76. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  77. 	return 0;
  78. }

84e6b51d84114587979c05b007d88b03.png

3.小结：

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

8. 基数排序(Radix Sort)

1.基本思想：

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

79c4e714657b444fbe031822c7614423.gif

 

2.代码实现：

 

sort.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include  "listqueue.h"
  5.  
  6. void  RadixSort(int* arr, int len)//O(d*n),O(n),稳定
  7. {
  8. 	//需要10个链式队列,存放进队的数字
  9. 	LinkQueue  queArr[10];//定义了10个队头;
  10. 	for (int i = 0; i < 10; i++)
  11. 	{
  12. 		InitQueue(&queArr[i]);
  13. 	}
  14. 	//得到最大数字的位数,确定进队和出队的次数
  15. 	int count = GetFigur(arr, len);
  16. 	int index;//队列的下标
  17. 	for (int i = 0; i < count; i++)//两个含义:1.次数;2.处理每个数字从右往左的第i个数字
  18. 	{
  19. 		for (int j = 0; j < len; j++)//遍历数组并入队
  20. 		{
  21. 			index = GetNum(arr[j], i);//index保存arr[j]应该进入对的队列下标
  22. 			//获取十进制整数右数第i位的数字
  23. 			Push(&queArr[index], arr[j]);//将数字存放的对应的队列;
  24. 		}
  25.  
  26. 		//出队
  27. 		int j = 0;
  28. 		for (int k = 0; k < 10; k++)
  29. 		{
  30. 			while (!IsEmpty(&queArr[k]))
  31. 			{
  32. 				DeQueue(&queArr[k], &arr[j++]);
  33. 			}
  34. 		}
  35. 		//销毁
  36. 		for (int i = 0; i < 10; i++)
  37. 		{
  38. 			Destroy(&queArr[i]);
  39. 		}
  40. 	}
  41. }
  42.  
  43. void Show(int* arr, int len)
  44. {
  45. 	for (int i = 0; i < len; i++)
  46. 	{
  47. 		printf("%d ", arr[i]);
  48. 	}
  49. 	printf("\n");
  50. }
  51. int main()
  52. {
  53. 	int arr[] = { 8,6,2,3,1,5,7,4};
  54. 	RadixSort(arr, sizeof(arr) / sizeof(arr[0]));
  55.  
  56. 	Show(arr, sizeof(arr) / sizeof(arr[0]));
  57. 	return 0;
  58. }

listqueue.h 

  1. #pragma once
  2.  
  3. //链式队列,队头在首元节点,队尾在尾节点
  4.  
  5. typedef int ElemType;
  6. typedef struct QNode//数据节点
  7. {
  8. 	ElemType data;
  9. 	struct QNode* next;
  10. }QNode, * QueuePtr;
  11.  
  12. typedef struct
  13. {
  14. 	QNode* front;//队头指针
  15. 	QNode* rear;//队尾指针
  16. }LinkQueue;//头结点的定义
  17.  
  18. //队列初始化
  19. void InitQueue(LinkQueue* pq);
  20.  
  21. //入队
  22. bool Push(LinkQueue* pq, ElemType val);
  23.  
  24. //判空
  25. bool IsEmpty(LinkQueue* pq);
  26.  
  27. //获取队头元素,但不删除
  28. bool GetHead(LinkQueue* pq, ElemType* rtval);
  29.  
  30. //出队,获取队头元素,且删除
  31. bool DeQueue(LinkQueue* ps, ElemType* rtval);
  32.  
  33. //销毁
  34. void Destroy(LinkQueue* ps);

listqueue.cpp

  1. #pragma once
  2.  
  3. //链式队列,队头在首元节点,队尾在尾节点
  4.  
  5. typedef int ElemType;
  6. typedef struct QNode//数据节点
  7. {
  8. 	ElemType data;
  9. 	struct QNode* next;
  10. }QNode, * QueuePtr;
  11.  
  12. typedef struct
  13. {
  14. 	QNode* front;//队头指针
  15. 	QNode* rear;//队尾指针
  16. }LinkQueue;//头结点的定义
  17.  
  18. //队列初始化
  19. void InitQueue(LinkQueue* pq);
  20.  
  21. //入队
  22. bool Push(LinkQueue* pq, ElemType val);
  23.  
  24. //判空
  25. bool IsEmpty(LinkQueue* pq);
  26.  
  27. //获取队头元素,但不删除
  28. bool GetHead(LinkQueue* pq, ElemType* rtval);
  29.  
  30. //出队,获取队头元素,且删除
  31. bool DeQueue(LinkQueue* ps, ElemType* rtval);
  32.  
  33. //销毁
  34. void Destroy(LinkQueue* ps);

 

bbb07984da9f4e23878dc35e8850ecc7.png

3.小结：

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

5.总结：

55832ab1f18942b09b7017dd8eeabb05.png

 

 

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

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

  

闽ICP备14008679号