• c语言的各种排序

     

    本篇文章的排序讲解有：

    1. 冒泡排序

    2. 选择排序

    3. 直接插入排序

    4. 希尔排序

    5. 堆排序

    6. 快速排序

    7. 归并排序

    讲解的大致的排序 就是这七种，讲解主要从思路，然后根据思路实现代码，然后进行计算优化，还有计算其时间复杂度，空间复杂度，稳定性

     开篇：

    那么，先从简单的开始：

    冒泡排序

    从c语言开始学到学完大致所有基本排序，第一个想必学的肯定是冒泡排序，冒泡排序，大致实现思路就是先经过一次的遍历将最大的（升序）放到最后一位，依次进行将倒数第二大的放在倒数第二位，反之降序相反。其实现过程大致同冒泡一样，排好一个数字就像冒出来一样，完成了一部分，故因此得名 

    大致运行动画如下： 

     那么代码实现思路就是，先将排好后该再最后一位的排好，对于升序，就像先比较，大的放在后面，代码就是：

    1. if(arr[i]>arr[i+1])
    2. swap(&arr[i],arr[i+1]);

    然后遍历全部，就是加上循环，就可以遍历全部，这样就排好了一个//结束条件先不说

    for (int j = 0; j <   ; j++)

     然后需要排号len-1个数就排好了全部

    for (int i = 0; i < len - 1; i++)//趟数

    所以代码全部即使：

    1. void  Bubble_sort(int* a, int len)
    2. {
    3. 	for (int i = 0; i < len - 1; i++)//趟数
    4. 	{
    5. 		for (int j = 0; j < len - i - 1; j++)
    6. 		{
    7. 			if (a[j] > a[j + 1])
    8. 			{
    9. 				swap(&a[j], &a[j + 1]);
    10. 				count = 1;
    11. 			}
    12. 		}
    13. 	}
    14. }

    但是，如果存在某一个数排好后，（但不是最后一个）再继续循环，就会空空浪费空间，所以优化：

    1. void  Bubble_sort(int* a, int len)
    2. {
    3. 	for (int i = 0; i < len - 1; i++)//趟数
    4. 	{
    5.  
    6.  
    7. //优化：		int count = 0;
    8. 		for (int j = 0; j < len - i - 1; j++)
    9. 		{
    10. 			if (a[j] > a[j + 1])
    11. 			{
    12. 				swap(&a[j], &a[j + 1]);
    13. 				count = 1;
    14. 			}
    15. 		}
    16.  
    17. //优化：
    18. 		if (count == 0)
    19. 		{
    20. 			break;
    21. 		}
    22. 	}
    23. }

    时间复杂度：0（n^2）;

    空间复杂度：0（1）； 

    快速排序

    然而有了冒泡排序，我们发现他的时间复杂度有点大，所有就有了与他同属于交换排序的——快速排序

     快速排序是由东尼·霍尔所发展的一种排序算法，使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

    快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了， 那么我们先讲解一下 霍尔 版的快速排序

    其大致子路就为一个指针（left）从左开始，一个从右（right）开始，然后取left/right值为关键数

    key，

    left从左往右找到比key大的停止，

    right从右往左找比key小的停止。          然后进行交换

    结束条件就为left与right相遇，

    最后在将key与相遇点的值交换（需要注意怎么确定相遇点是比key大还是比key小呢？）

    对于这一点霍尔大佬也想到了解决方法：

    如果开始选左边作为key，那么右边先走，保证了相遇点比key小/就为key的值。

               反之右边作为key，那么在边先走，保证了相遇点比key大/就为key的值。

    那么这时候相遇点左边全为比key小的值，右边全为比key大的值

    然后在以相遇点为分界线分割  分为三个区间【left，相遇点-1】相遇点【相遇点+1，right】 

    然后依次循环直到left>right条件结束

    运行效果动画：

                                                 实行起来还是比较容易的

    1. int part(int* a, int left, int right)
    2. {
    3. 	//这里不采用指针，而是下标访问，如果感兴趣的话，可以尝试指针写法
    4. 	int key = left;
    5. 	while (left < right)
    6. 	{
    7. 		while (left < right && a[right] >= a[key])
    8. 		{
    9. 			right--;
    10. 		}
    11. 		while (left<right && a[left] <= a[key])//前一个是为了防止，在内存while已经不满足条件
    12. 		{
    13. 			left++;
    14. 		}
    15. 		swap(&a[left], &a[right]);
    16. 	}
    17. 	swap(&a[left], &a[key]);
    18. 	return left;
    19. }
    20. void Hoare_sort(int* a, int left, int right)
    21. {
    22. 	if(left >= right)
    23. 	{
    24. 		return;
    25. 	}
    26. 	int key = part(a, left, right);
    27. 	Hoare_sort(a, left, key - 1);
    28. 	Hoare_sort(a, key + 1, right);
    29. 	return ;
    30. }

    时间复杂度： O(nlogn)

    空间复杂度：0（1）；

    虽然在最坏的情况下 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

    快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

    本段取自菜鸟教程 

    针对优化就是key每次选择都为left与right与中间数的中间值，优化起来比较简单，不进行讲解，只展示代码，优化原理：防止了最坏情况0(n^2)的情况，   对应案例：（本来就有序）；             

     

    1. int Get_key_Index(int* a, int left, int right)
    2. {
    3. 	int mid = (left + right) / 2;
    4. 	if (a[left] < a[right])
    5. 	{
    6. 		if (a[left] > a[mid])
    7. 		{
    8. 			return left;
    9. 		}
    10. 		else if (a[right] < a[mid])
    11. 		{
    12. 			return right;
    13. 		}
    14. 		else
    15. 		{
    16. 			return mid;
    17. 		}
    18. 	}
    19. 	else if(a[left]==a[right])
    20. 	{
    21. 		return left;
    22. 	}
    23. 	else
    24. 	{
    25. 		if (a[right] > a[mid])
    26. 		{
    27. 			return right;
    28. 		}
    29. 		else if (a[left] < a[mid])
    30. 		{
    31. 			return left;
    32. 		}
    33. 		else
    34. 		{
    35. 			return mid;
    36. 		}
    37. 	}
    38. }
    39. int part_1_sort(int* a, int left, int right)
    40. {
    41. 	int midi = Get_key_Index(a,left,right);	
    42. 	swap(&a[midi], &a[left]);
    43. 	int keyi = left;
    44. 	while (left < right)
    45. 	{
    46. 		while (left < right && a[keyi] <= a[right])
    47. 		{
    48. 			right--;
    49. 		}
    50. 		while (left<right && a[keyi] >= a[left])
    51. 		{
    52. 			left++;
    53. 		}
    54. 		swap(&a[left], &a[right]);
    55. 	}
    56. 	swap(&a[left], &a[keyi]);
    57. 	return left;//返回此时keyi的下标数
    58. }
    59. void Quick_sort_Hoare(int* a,int begin,int end)
    60. {
    61. 	if (begin >= end)
    62. 	{
    63. 		return;
    64. 	}
    65. 	int keyi = part_1_sort(a, begin, end);
    66. 	//三个区间  [begin,keyi-1]  keyi  [keyi+1,end]
    67. 	Quick_sort_Hoare(a, begin, keyi - 1);
    68. 	Quick_sort_Hoare(a, keyi + 1, end);
    69. }

    后人对于快排，有进行了别的版本1：挖坑版     2：双指针

                                               挖坑版： 

    与霍尔版本不一样的就为key的位置想象为了坑，多了一个变量存储坑的下标，下面的实现原理跟霍尔相似了，只不过right与left找到对应的位置，将这个值补到这个坑，再将right/left的位置设置为坑

                                     代码展示：

    1. int part_2(int* a, int left, int right)
    2. {
    3. 	int key = a[left];
    4. 	int hole = left;
    5. 	while (left < right)
    6. 	{
    7. 		while (left < right && a[right] >= key)
    8. 		{
    9. 			right--;
    10. 		}
    11. 		a[hole] = a[right];
    12. 		hole = right;
    13. 		while (left < right && key >= a[left])
    14. 		{
    15. 			left++;
    16. 		}
    17. 		a[hole] = a[left];
    18. 		hole = left;
    19. 	}
    20. 	a[hole] = key;
    21. 	return left;//返回此时keyi的下标数
    22. }
    23. void Hole_sort(int* a, int left, int right)
    24. {
    25. 	if (left >= right)
    26. 	{
    27. 		return;
    28. 	}
    29. 	int key = part_2(a, left, right);
    30. 	Hole_sort(a, left, key - 1);
    31. 	Hole_sort(a, key + 1, right);
    32. }

    双指针法：

    双指针法也是我认为快排最好实现的一种

    其思路就为：

    prev为头指针     cur为prev下一个的指针    key仍为最左边

    1.然后cur找到比key小的

    2.找到了先++prev，在swap（cur与prev） 

    3.在++cur

    4.最后cur与prev之间全为比key大的，（当cur>right结束）

    4.再进行swap（key与prev），key=prev   return  key；

    最后递归结束条件：left>=right

    代码实现比较简单：

    1. void part_3_sort(int* a,int left,int right)
    2. {
    3. 	if (left >= right)
    4. 	{
    5. 		return;
    6. 	}
    7. 	int midi = Get_key_Index(a, left, right);
    8. 	swap(&a[midi], &a[left]);
    9. 	int keyi =left;
    10. 	int cur = left+1;
    11. 	int prev = left;
    12. 	while (cur <= right)
    13. 	{
    14. 		if (a[cur] < a[keyi] && ++prev != cur)		
    15. 		{
    16. 			swap(&a[cur], &a[prev]);
    17. 		}
    18. 		cur++;
    19. 	}
    20. 	swap(&a[keyi], &a[prev]);
    21. 	keyi = prev;
    22. 	part_3_sort(a, left, keyi - 1);
    23. 	part_3_sort(a, keyi + 1, right);
    24. }
    25. void Quick_sort_Pointer_item(int* a, int begin, int end)
    26. {
    27. 	part_3_sort(a, begin, end);
    28. }

    利用栈去实现快排，这里就不讲解了，实现起来比较简单，需要注意的是栈是后进先出，然后入栈的时候入栈的为区间的边界值；

     直接插入排序：

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

    插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

    算法思路实现：

    第一趟的情况下：将第一待排序序列第一个元素看做一个有序序列，把第二个元素当为最后一个进行，然后按照正常排序进行排序，

    第二趟就将前2个待排序的元素看为一个有序序列，然后把第三个为最后一个，然后进行正常排序

    动画演示如下： 

     

    代码实现如下： 

    1. void Insertion_sort(int* a,int len)
    2. {
    3. 	for (int i = 0; i < len-1; i++)
    4. 	{
    5. 		int end = i;
    6. 		int tmp = a[i+1];
    7. 		while (end >= 0)
    8. 		{
    9. 			if (a[end] > tmp)
    10. 			{
    11. 				a[end + 1] = a[end];
    12. 				end--;
    13. 			}
    14. 			else
    15. 			{
    16. 				break;
    17. 			}
    18. 			a[end + 1] = tmp;
    19. 		}
    20. 	}
    21. }

     时间复杂度：0（n^2）;

    空间复杂度：0（1）；

    希尔排序：

    希尔排序是由插入排序进行优化而来的 

    其原理很插入很相似，但是他是将间隔为gap（任意一个数，但不大于n），的为一组，然后总计gap个组

    对每一组进行排序，这一整步骤为：预排序，达到的效果为：接近有序

    然后再将gap的值缩小，在进行预排序，知道gap=1那一次排完后结束，

    代码再实现的基础上就在插入上修改的一点地方

    1. void shell_sort_1(int* a, int n)
    2. {
    3. 	int gap = n;
    4. 	while (gap > 1)
    5. 	{
    6. 		gap = gap / 3 + 1;//分组，将间隔为gap分为一组，共gap个组
    7. 		for (int i = 0; i < gap; i++)
    8. 		{
    9. 			for (int j = i; j < n - gap; j += gap)
    10. 			{
    11. 				int end = j;
    12. 				int tmp = a[end+gap];
    13. 				while (end >= 0)
    14. 				{
    15. 					if (tmp < a[end])
    16. 					{
    17. 						a[end + gap] = a[end];
    18. 						end -= gap;
    19. 					}
    20. 					else
    21. 					{
    22. 						break;
    23. 					}
    24. 				}
    25. 				a[end + gap] = tmp;
    26. 			}
    27. 		}
    28. 	}
    29. }

    对比一下后 ，红笔为添加的，蓝色为修改的

    然后我们还是可以优化的，将两个for循环转化为一个：

    1. void shell_sort_2(int* a, int n)
    2. {
    3. 	int gap = n;
    4. 	while (gap > 1)
    5. 	{
    6. 		//前gap个全不为一组
    7. 		gap = gap / 3 + 1;//分组，将间隔为gap分为一组，共gap个组
    8. 		for (int i = 0; i < n - gap; i++)
    9. 		{
    10. 			int end = i;
    11. 			int tmp = a[end + gap];
    12. 			while (end >= 0)
    13. 			{
    14. 				if (tmp < a[end])
    15. 				{
    16. 					a[end + gap] = a[end];
    17. 					end -= gap;
    18. 				}
    19. 				else
    20. 				{
    21. 					break;
    22. 				}
    23. 			}
    24. 			a[end + gap] = tmp;
    25. 		}
    26. 	}
    27. }

     时间复杂度：0（n^1.3~(logn)^2);//这个我是搜的，大概是这个，反之就是很快

    空间复杂度：0(1);

    选择排序：

     选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

     

    观看完动画我们也大概得知其实现原理，这里就不在多描述， 

    1. void Select_sort(int* a, int len)
    2. {
    3. 	int left = 0;
    4. 	int right = len - 1;
    5. 	while (left < right)
    6. 	{
    7. 		int min = left;
    8. 		for (int i = left; i <= right; i++)
    9. 		{
    10. 			if (a[min] > a[i])
    11. 			{
    12. 				min = i;
    13. 			}
    14. 		}
    15. 		//交换
    16. 		swap(&a[min], &a[left]);
    17. 		left++;
    18. 	}
    19. }

    又或者两边同时走，这样写，进行优化。 

    1. void Select_sort(int* a, int len)
    2. {
    3. 	int left = 0;
    4. 	int right = len - 1;
    5. 	while (left < right)
    6. 	{
    7. 		int min = left;
    8. 		int max = right;
    9. 		for (int i = left; i <= right; i++)
    10. 		{
    11. 			if (a[min] > a[i])
    12. 			{
    13. 				min = i;
    14. 			}
    15. 			if (a[max] < a[i])
    16. 			{
    17. 				max = i;
    18. 			}
    19. 		}
    20. 		//交换
    21. 		if (max == left)
    22. 		{
    23. 			max = min;
    24. 		}
    25. 		swap(&a[min], &a[left]);
    26. 		swap(&a[max], &a[right]);
    27. 		left++;
    28. 		right--;
    29. 	}
    30. }

     

    时间复杂度：0（n ^2）；

    空间复杂度：0（1）；

    堆排序： 

     堆排序，就是利用了二叉树进行实现，其实先原理比较简单，但是代码用c实现比较多，这里不在展示，

    提醒一点向下调整的整体效果是远远大于向上调整的。

    时间复杂度：0（n logn）；

    空间复杂度：0（1）；

     归并排序：

     归并排序

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

    作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

    • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
    • 自下而上的迭代；

    在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

    However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

    然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

    实现动画： 

     

    大致的实现图像： 

    再我首次学这个排序的时候，我都在想这个分的过程

    在学玩后，就了解完了，无论任何情况，分的结果就为分为：每组只有一个数据，那么肯定这数据是有序的，然后再将相邻的两个组进行正常排序到另一个数组，这个过程就为治，就如图上所说：8  与   4这个两个组排好后就为4 ，8 这个是有序的，同理又有一组 5，7那么这两组在进行治，结果就如图：4，5，7，8

    那么代码：（这个代码还是实现比较复杂的，首先要分，还要治）

    分这很好解决，治是主要

    这就为分：

    1. 	int mid = (left + right) / 2;//(begin+end)>>1;
    2. 	//[left,mid],[mid+1,right]
    3. 	_MergeSort(a, left, mid, tmp);
    4. 	_MergeSort(a, mid + 1, right, tmp);

     归并排序还要另外开辟一个大小同样的数组，那么这个数组就是在治，的步骤使用

    分完以后两个组，每组只有一个元素，然后进行排序拷贝到tmp数组，在将有序的再次拷回去 

    用语言表示很简单，但是对于递归理解还是有一定要求的，

    还是需要练习：

    代码：

    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;//(begin+end)>>1;
    8. 	//[left,mid],[mid+1,right]
    9. 	_MergeSort(a, left, mid, tmp);
    10. 	_MergeSort(a, mid + 1, right, tmp);
    11.  
    12. 	//排完序了
    13. 	int i = left;
    14. 	//进行拷贝
    15.  
    16. 	int begin1 = left, begin2 = mid + 1;
    17. 	int end1 = mid, end2 = right;
    18. 	while (begin1 <= end1 && begin2 <= end2)
    19. 	{
    20. 		if (a[begin1] < a[begin2])//选1进
    21. 		{
    22. 			tmp[i++] = a[begin1++];
    23. 		}
    24. 		else
    25. 		{
    26. 			tmp[i++] = a[begin2++];
    27. 		}
    28. 	}
    29.  
    30. 	//不管谁先结束，再将剩下的拷贝进去
    31.  
    32. 	if (begin1 > end1)//1先结束  2没结束
    33. 	{
    34. 		while (begin2 <= end2)
    35. 		{
    36. 			tmp[i++] = a[begin2++];
    37. 		}
    38. 	}
    39. 	else
    40. 	{
    41. 		while (begin1 <= end1)
    42. 		{
    43. 			tmp[i++] = a[begin1++];
    44. 		}
    45. 	}
    46.  
    47. 	//再最后拷贝回去
    48.  
    49. 	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
    50. }
    51.  
    52. void MergeSort(int* a, int n)
    53. {
    54. 	int* tmp = malloc(sizeof(int) * n);
    55. 	_MergeSort(a, 0, n - 1, tmp);
    56. }

     对于递归理解不了的，可以看一下非递归实现：

    1.  
    2. //归并排序--非递归实现
    3.  
    4. void _MergeSort_non(int* a, int left, int right, int* tmp)
    5. {
    6. 	int gap = 1;//每组的大小
    7. 	int n = right + 1;
    8. 	while (gap < n)
    9. 	{
    10. 		for (int i = 0; i <= right; i += gap * 2)
    11. 		{
    12. 			int j = i;
    13. 			int begin1 = i,begin2= i + gap;
    14. 			int end1 = i + gap - 1, end2 = i + 2 * gap - 1;
    15.  
    16. 			//printf("[%d,%d][%d,%d]\n", begin1, endl, begin2, end2);
    17.  
    18. 			//修正区间--防止越界
    19. 			if (begin2 >= n)
    20. 			{
    21. 				break;
    22. 			}
    23. 			if (end2 >= n)
    24. 			{
    25. 				end2 = n - 1;
    26. 			}
    27.  
    28. 			//进行区间排序--两个组合并排序，先排好序进去到tmp中，再拷贝回去
    29. 			while (begin1 <= end1 && begin2 <= end2)
    30. 			{
    31. 				if (a[begin1] > a[begin2])//2进去
    32. 				{
    33. 					tmp[j++] = a[begin2++];
    34. 				}
    35. 				else
    36. 				{
    37. 					tmp[j++] = a[begin1++];
    38. 				}
    39. 			}
    40. 			//不管谁先结束，再将剩下的拷贝进去
    41.  
    42. 			if (begin1 > end1)//1先结束  2没结束
    43. 			{
    44. 				while (begin2 <= end2)
    45. 				{
    46. 					tmp[j++] = a[begin2++];
    47. 				}
    48. 			}
    49. 			else
    50. 			{
    51. 				while (begin1 <= end1)
    52. 				{
    53. 					tmp[j++] = a[begin1++];
    54. 				}
    55. 			}
    56.  
    57. 			//再从tmp拷回去
    58.  
    59. 			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    60. 		}
    61. 		gap *= 2;
    62. 	}
    63. }
    64. void MergeSort_non(int* a, int n)
    65. {
    66. 	int* tmp = malloc(sizeof(int) * n);
    67. 	_MergeSort_non(a, 0, n - 1, tmp);
    68. }

     时间复杂度：0（logn）;

    空间复杂度：0（n）；

  • 相关阅读:
    东方博宜OJ——1.整数运算题解
    荧光素标记海藻糖；FITC-Trehalose Dihydrate,FITC荧光标记黑曲霉糖/水苏糖/阿卡波糖
    怎么把多张图片合成gif？教你简单几步快速制作gif
    【重识云原生】第六章容器6.3.4节——etcd组件
    随笔2022.12.6
    C# 第五章『面向对象』◆第9节：抽象类和密封类
    Vue官方文档（45）：过滤器
    【OpenCV4】拉普拉斯算子提取边缘 cv::Laplacian() 用法详解和代码示例（c++）
    【LeetCode刷题-滑动窗口】--340.至多包含K个不同字符的最长子串
    Linux项目自动化构建工具：make与Makefile的基本用法
  • 原文地址：https://blog.csdn.net/2301_81265915/article/details/138169488