• 排序算法集合

    1. 冒泡排序

    排序的过程分为多趟，在每一趟中，从前向后遍历数组的无序部分，通过交换相邻两数位置的方式，将无序元素中最大的元素移动到无序部分的末尾（第一趟中，将最大的元素移动到数组倒数第一的位置；第二趟中，将第二大的元素移动到数组倒数第二的位置，以此类推）。

    每排一趟，数组末尾的有序序列就向前增长一个元素，数组前端的无序部分就减少一个元素。

    优化：某趟中，一次交换也没有发生，说明数组已有序，直接结束排序。

    整个排序的过程中，剩余无序元素中最大的元素就像气泡一样不断“上浮”到数组末尾，所以该算法被称作冒泡排序。

    冒泡排序的思想很简单，类似于递归：

    要实现整个数组（n个元素）的有序，可以将数组分为前（n-1）个元素和最后一个元素。

    首先确保最后一个元素有序（最大），然后再用相同的方式解决前（n-1）个元素组成的数组的有序性问题。

    当然，你也可以当我上面这段话是放屁，因为冒泡排序的算法太过简单，按上面的方式来理解确实小题大做。 

    但伴随着简单算法的往往是极高的开销，这也使得冒泡排序没有任何的实际意义，仅作教学作用。

    可以说冒泡排序是最拉的排序算法，接下来讲到的所有排序算法，效率都至少为其的十倍以上（实测结果非理论分析，理论分析出的时间复杂度几乎相同）

    时间复杂度：最坏情况（元素逆序）O(n^{2})，最好情况（已有序）O(n)

    空间复杂度：O(1)

    1. //冒泡排序
    2. void BubbleSort(int* arr, int len)
    3. {
    4. 	for (int i = 0; i < len; i++)
    5. 	{
    6. 		int flag = 1;
    7. 		for (int j = 0; j < len - 1 - i; j++)
    8. 		{
    9. 			if (arr[j] > arr[j + 1])
    10. 			{
    11. 				flag = 0;
    12. 				swap(&arr[j], &arr[j + 1]);
    13. 			}
    14. 		}
    15. 		if (flag)
    16. 			return;
    17. 	}
    18. }

    2. 选择排序

    顾名思义，就是在每趟排序中，直接选出最大的元素（的下标），然后将其与无序部分末尾的元素进行交换，同时无序部分的末尾向前缩短一个元素。

    相对于冒泡排序，二者的做法很像，但选择排序省去了交换相邻元素的过程（效率提高的关键），手段更加直接。

    优化：在选出最大元素的同时，将最小元素也选出来，两端同时排序。

    1. void SelectSort(int* arr, int len)
    2. {
    3. 	int begin = 0, end = len - 1;
    4. 	while (begin < end)
    5. 	{
    6. 		int max = begin;
    7. 		int min = begin;
    8. 		for (int i = begin + 1; i <= end; i++)
    9. 		{
    10. 			if (arr[i] < arr[min])
    11. 				min = i;
    12. 			if (arr[i] > arr[max])
    13. 				max = i;
    14. 		}
    15. 		swap(&arr[begin], &arr[min]);
    16. 		swap(&arr[end], &arr[max]);
    17.  
    18. 		begin++;
    19. 		end--;
    20. 	}
    21. }

    但是，直接进行优化之后的算法会存在一个小bug：

    假设在每趟排序中，将最大元素和最小元素选出来之后，先让最小元素交换到无序部分的前端，再让最大元素交换到无序部分末尾。

    那么，当最大元素刚好在无序部分前端时，就会发生如下的过程：

    1. 首元素（最大元素）与最小元素交换

    2. 最大元素（首元素，此时该位置为最小元素）与末尾元素交换

     可以按照下面的方式解决。

    1. //选择排序
    2. void SelectSort(int* arr, int len)
    3. {
    4. 	int begin = 0, end = len - 1;
    5. 	while (begin < end)
    6. 	{
    7. 		int max = begin;
    8. 		int min = begin;
    9. 		for (int i = begin + 1; i <= end; i++)
    10. 		{
    11. 			if (arr[i] < arr[min])
    12. 				min = i;
    13. 			if (arr[i] > arr[max])
    14. 				max = i;
    15. 		}
    16. 		swap(&arr[begin], &arr[min]);
    17. 		if (begin == max)
    18. 			swap(&arr[end], &arr[min]);
    19. 		else
    20. 			swap(&arr[end], &arr[max]);
    21.  
    22. 		begin++;
    23. 		end--;
    24. 	}
    25. }

    时间复杂度： O(n^{2})

    空间复杂度：O(1)

    由于选择排序无法提前结束，所以其时间复杂度为稳定的O(n^{2})。

    但是，相比于冒泡排序，选择排序在整体上减少了频繁交换的消耗，在一般情况下，效率要远好于冒泡排序。

    3. 插入排序

    上面的两种算法是在为某个位置选择合适的元素填入，而插入排序则是在为某个元素选择合适的位置去存放，也正是这一差别，使其成为了这三位难兄难弟的老大哥。

    为某个元素选择合适的位置，必然只有在其他元素都有序的情况下才能做到（或者局部有序）。

    尽管数组在整体上无序，我们却可以将开头的一个元素看作是无序，接着将第二个元素插入其中。

    于是，前两个元素就变得有序了，我们又可以将第三个元素插入其中……以此类推，数组便逐渐有序了。

    插入排序，就是将数组分为两个部分：数组前端的有序部分（开始只有一个元素），和数组后半段的无序部分。然后将无序部分的元素逐个插入到有序部分。

    而对于插入，我们采用的办法是：

    从后向前遍历有序部分，如果当前位置的元素比要插入的元素大，则将当前位置的元素向后移动一个元素（为要插入的元素腾位置）；如果当前位置的元素要比插入的元素小，则将要插入的元素插入到当前位置的后面（自己原本的位置，或者是第一种情况腾出来的位置）。

    优化： 可优化为希尔排序，详见下文。

    1. //插入排序
    2. void InsertSort(int* arr, int len)
    3. {
    4. 	for (int i = 1; i < len; i++)
    5. 	{
    6. 		int temp = arr[i];
    7. 		int j = i;
    8. 		while(j > 0 && arr[j - 1] > temp)
    9. 		{
    10. 			arr[j] = arr[j - 1];
    11. 			j--;
    12. 		}
    13. 		arr[j] = temp;
    14. 	}
    15. }

    时间复杂度：最坏情况（元素逆序）O(n^{2})，最好情况（已有序）O(n)

    空间复杂度：O(1)

    虽然看上去与冒泡排序一模一样，但是其实际的消耗要小得多，相比于选择排序也要更优。

    4. 希尔排序

     在插入排序算法中，越小的元素越早插入越好，越大的元素越晚插入越好。

    当元素恰好逆置时，算法的消耗较大，几乎等价于冒泡排序。

    而希尔排序就是希尔为解决插入排序痛点而设计的算法，解决这一痛点的方法就是，先对整个数组进行跨度较大的粗调，再进行更加细致的调整（只有数据量较大时希尔排序的优化才有意义，否则直接使用插入排序即可）。

    我们发现，如果较大的元素插入得较早，之后就会进行大量的操作将该元素后移，并且每次只移动一个元素。

    如果我们能够快速地（一次跳过多个元素）将这些较大的元素调整到靠后的位置，使得数组基本有序，插入排序的时间复杂度就会无限接近于最好情况。

    那么如何进行粗调呢？

    1. 将数组的元素分为若干组（记组数为gap），每一组元素的下标模上gap所得的值相同（即每一组元素的下标为模gap的同余关系，类似于分层抽样）。

    2. 对每一组的元素进行插入排序（这样一来，较大的元素每次向后移动的元素个数为gap，粗调的效率就远高于直接插入排序）。

    3. 缩小gap的值，重复上述过程（一般做法为gap=gap/3+1，+1的目的是使得最后一趟排序时gap为1，也就是对整个数组进行一次插入排序）。

    1. //希尔排序(插入排序优化)
    2. void ShellSort(int* arr, int len)
    3. {
    4. 	int gap = len;
    5. 	while (gap > 1)
    6. 	{
    7. 		gap = gap / 3 + 1;
    8. 		for (int group = 0; group < gap; group++)
    9. 		{
    10. 			for (int i = group + gap; i < len; i += gap)
    11. 			{
    12. 				int temp = arr[i];
    13. 				int j = i;
    14. 				while (j > group && arr[j - gap] > temp)
    15. 				{
    16. 					arr[j] = arr[j - gap];
    17. 					j -= gap;
    18. 				}
    19. 				arr[j] = temp;
    20. 			}
    21. 		}
    22. 	}
    23. }

    可以看到，最内层的两层循环其实就是将插入排序中的“1”替换为了“gap”，将起点从“0+1”改成了“group + gap”。

    控制group的循环就是在切换插入排序的组别。

    优化：如果觉得四层循环看起来很唬人的话，我们也可以优化掉一层循环（但效率不变）

    1. //希尔排序X(各组同时排，优化掉三重循环，但效率相同)
    2. void ShellSort_X(int* arr, int len)
    3. {
    4. 	int gap = len;
    5. 	while (gap > 1)
    6. 	{
    7. 		gap = gap / 3 + 1;
    8. 		for (int i = gap; i < len; i++)
    9. 		{
    10. 			int temp = arr[i];
    11. 			int j = i;
    12. 			while (j > 0 && arr[j - gap] > temp)
    13. 			{
    14. 				arr[j] = arr[j - gap];
    15. 				j -= gap;
    16. 			}
    17. 			arr[j] = temp;
    18. 		}
    19. 	}
    20. }

    时间复杂度：平均情况O(n^{1.3})，最好情况O(n(logn)^{2})

    空间复杂度：O(1)

    初见希尔排序的代码，可能会误以为其效率极低，但实际上希尔排序的效率极高，甚至在数据量较大时，效率高出上文介绍的算法不止一个量级（百倍以上）！

    接下来的几种算法，于希尔排序同属一个量级，但效率有略微差别。

    其排序的过程极其复杂，具有许多不可控因素，不能简单地通过循环的层数来计算时间复杂度。

    希尔排序的代码很难理解，但是其解决问题的思想却很值得我们学习借鉴。

    5. 堆排序

    详见这篇文章：全面详解堆-CSDN博客

    6. 快速排序

    详见这篇文章：C语言实现快速排序算法-CSDN博客 

    值得一提的是，快速排序正如其名，快且综合实力强。

    C语言中，qsort函数的底层算法便是采用的快速排序算法。

    7. 归并排序 

    归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

    将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

    若将两个有序表合并成一个有序表，称为二路归并。

    以二路归并为例，假如一个数组从中间位置被分为了前后两个部分，而这两个部分都是有序的，那么我们就可以采用与合并两个有序链表相同的思路：比较两个序列中的最小值，将较小的那个插入到新的序列中，不断重复这样的操作，直到原序列中的值全部插入到新序列中。

    但前提是，前后两个子序列都要有序。

    所以我们的首要任务是使得前后两个子序列有序，而使其有序的方式依然如上。

    于是我们找到的递归的思路：

    1. void _MergeSort(int* arr, int* copy, int begin, int end)
    2. {
    3. 	if (begin >= end)
    4. 		return;
    5.  
    6. 	//区间不能分为[begin,mid-1]和[mid,end]
    7. 	int mid = (begin + end) / 2;
    8. 	_MergeSort(arr, copy, begin, mid);
    9. 	_MergeSort(arr, copy, mid + 1, end);
    10.  
    11. 	//归并
    12. 	int begin1 = begin, end1 = mid;
    13. 	int begin2 = mid + 1, end2 = end;
    14. 	int cur = begin;
    15. 	while (begin1 <= end1 && begin2 <= end2)
    16. 	{
    17. 		if (arr[begin1] < arr[begin2])
    18. 		{
    19. 			copy[cur++] = arr[begin1++];
    20. 		}
    21. 		else
    22. 		{
    23. 			copy[cur++] = arr[begin2++];
    24. 		}
    25. 	}
    26.  
    27. 	while (begin1 <= end1) { copy[cur++] = arr[begin1++]; }
    28. 	while (begin2 <= end2) { copy[cur++] = arr[begin2++]; }
    29. 	memcpy(arr + begin, copy + begin, (end - begin + 1) * sizeof(int));
    30. }
    31.  
    32. //归并排序
    33. //时间复杂度O(n*logn)，空间复杂度O(n)
    34. void MergeSort(int* arr, int len)
    35. {
    36. 	int* copy = (int*)malloc(sizeof(int) * len);
    37. 	if (copy == NULL)
    38. 	{
    39. 		perror("malloc fail");
    40. 		return;
    41. 	}
    42.  
    43. 	_MergeSort(arr, copy, 0, len - 1);
    44. 	
    45. 	free(copy);
    46. }

    和快速排序类似，既然这个算法是用递归的方式实现的，我们就会考虑其非递归的实现方式。

    但与快速排序不同，快速排序的递归方式类似于二叉树的前序遍历，但是归并排序类似于后序遍历。

    参考栈与递归的实现-CSDN博客会发现，二叉树前序遍历的非递归实现很简单，但是后序遍历的非递归实现则十分麻烦。

    将递归算法转化为非递归算法，除了利用栈来模拟实现，也可以尝试直接利用迭代来实现。

    思路就是将数组按gap个数据为一组分为多组，每两个相邻的组进行插入合并，随后gap变为原来的两倍，再次重复以上过程，直到gap大于数组长度。

    当然，最后一组可能分配不到gap个数据，也可能只能分出奇数个组，针对这些问题，进行插入合并（归并）的代码进行了调整。

    1. //归并排序非递归
    2. void MergeSortNonR(int* arr, int len)
    3. {
    4. 	int* copy = (int*)malloc(sizeof(int) * len);
    5. 	if (copy == NULL)
    6. 	{
    7. 		perror("malloc fail");
    8. 		return;
    9. 	}
    10.  
    11. 	for (int gap = 1; gap < len; gap *= 2)
    12. 	{
    13. 		for (int i = 0; i < len; i += 2 * gap)
    14. 		{
    15. 			int begin1 = i, end1 = i + gap - 1;
    16. 			int begin2 = i + gap, end2 = i + 2 * gap - 1;
    17. 			//第二组都越界，不归并了
    18. 			if (begin2 >= len)
    19. 			{
    20. 				break;
    21. 			}
    22. 			//第二组越界部分，修正并归并
    23. 			if (end2 >= len)
    24. 			{
    25. 				end2 = len - 1;
    26. 			}
    27. 			int cur = i;
    28. 			while (begin1 <= end1 && begin2 <= end2)
    29. 			{
    30. 				if (arr[begin1] < arr[begin2])
    31. 				{
    32. 					copy[cur++] = arr[begin1++];
    33. 				}
    34. 				else
    35. 				{
    36. 					copy[cur++] = arr[begin2++];
    37. 				}
    38. 			}
    39.  
    40. 			while (begin1 <= end1) { copy[cur++] = arr[begin1++]; }
    41. 			while (begin2 <= end2) { copy[cur++] = arr[begin2++]; }
    42. 			memcpy(arr + i, copy + i, ((end2 - i + 1) * sizeof(int)));
    43. 		}
    44. 	}
    45.  
    46. 	free(copy);
    47. }

    时间复杂度：O(nlogn)

    空间复杂度：O(n)

  • 相关阅读:
    QGraphicsItem图元坐标和在场景中的坐标（六）
    Verilog中parameter在仿真时的应用
    Unity脚本的基础语法(1)-游戏对象的常用操作
    快来白漂动漫头像~Python调用百度AI接口，1行代码免费转换200张
    Transformer知识点
    使用JavaScript及HTML、CSS完成秒表计时器
    阿里云+作业帮+小红书：论剑云原生时代的 SRE与智能运维
    什么是同源策略？
    消息队列 RabbitMQ入门：Linux（Docker）中安装和卸载RabbitMQ服务
    设计模式——原型模式
  • 原文地址：https://blog.csdn.net/2302_80372340/article/details/139247172