• 排序算法（二）

    本篇博客是上篇博客【排序算法（一）】的继续。

    目录

    三、交换排序

    1.冒泡排序

    （1）代码实现（升序）

    （2）分析

    2.快速排序

    （1）基本思想

    （2）代码实现（升序）

    <1>递归版本

    <2>非递归版本

    （3）分析

    四、归并排序

    二路归并排序

    （1）基本思想

    （2）代码实现（升序）

    <1>递归版本

    <2>非递归版本

    （3）分析

    三、交换排序

    1.冒泡排序

    该算法也是C语言入门阶段熟知的排序算法，不再做详细论述。

    （1）代码实现（升序）

    1. void Swap(int* x, int* y)
    2. {
    3. 	int temp = *x;
    4. 	*x = *y;
    5. 	*y = temp;
    6. }
    7.  
    8.  
    9. void BubbleSort(int* a, int n)
    10. {
    11. 	for(int i = 0; i < n - 1; i++)
    12. 	{
    13. 		bool exchange = false;
    14. 		for (int j = 0; j < n - i - 1; j++)
    15. 		{
    16. 			if (a[j] < a[j + 1])  //
    17. 			{
    18. 				Swap(a + j, a + j + 1);
    19. 				exchange = true;
    20. 			}
    21. 		}
    22. 		if (exchange == false)
    23. 			break;
    24. 	}
    25. }

    （2）分析

    时间复杂度为O\left ( n^2 \right )

    空间复杂度为O\left ( 1 \right )

    该算法是稳定的。

    2.快速排序

    （1）基本思想

    任取待排序序列中的某元素作为基准值（一般为第一个元素），通过调整将该基准值放在正确位置上，使得以该基准值为界将序列分成左右两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值（以升序为例）；然后左右子序列重复该过程，直到所有元素均排列在正确的位置上。

    （2）代码实现（升序）

    <1>递归版本

    从基本思想中可以看出该算法具有递归性，因此将其实现为递归算法是最自然、最好理解的。

    首先列出递归的基本框架：

    1. void QuickSort(int* a, int begin, int end)
    2. {
    3. 	if (begin >= end)//退出递归的条件
    4. 		return;
    5.  
    6. 	int keyi = PartSort(a, begin, end);//进行调整，将基准值放到正确位置
    7. 	
    8.     QuickSort(a, begin, keyi - 1);//左子序列递归
    9. 	QuickSort(a, keyi + 1, end);//右子序列递归
    10. }

    现在的核心就是实现PartSort()函数，将基准值放到正确位置。

    如何进行调整呢？其实方法还是有很多的，这里着重介绍3种方法：

    ①hoare版本

    hoare版本是最开始的方法，因为快速排序就是由Hoare于1962年提出的。由于该方法需要注意的细节很多，其他方法都是后来对该方法的优化，写起来不容易出错。

    基本想法为：

    选定第一个元素为基准值，然后从右边开始逐个往前寻找比基准值小的元素，找到即停，接着从左边开始逐个往后寻找比基准值大的元素，找到即停；交换找到的两个元素；继续上述寻找操作，直到相遇；最后交换相遇位置元素和首元素（基准值）。（可以证明，相遇时的元素一定小于基准值）

    1. //hoare 
    2. int PartSort1(int* a, int begin, int end)
    3. {
    4. 	int keyi = begin;
    5. 	int left = begin;
    6. 	int right = end;
    7.  
    8. 	while (left < right)
    9. 	{
    10. 		//升序:右边找小
    11. 		while (left < right && a[right] >= a[keyi]) //
    12. 		{
    13. 			right--;
    14. 		}
    15. 		//升序:左边找大
    16. 		while (left < right && a[left] <= a[keyi]) //
    17. 		{
    18. 			left++;
    19. 		}
    20.  
    21. 		Swap(a + left, a + right);
    22. 	}
    23. 	Swap(a + left, a + keyi);
    24.  
    25. 	return left;
    26. }

    ②挖坑法

    基本思想为：

    先将基准值保存起来，并将该位置设为坑位；从右边找到比基准值小的元素后，将该元素值放在坑位里，并更新坑位，将该位置设为新的坑位；从左边找到比基准值大的元素后，将该元素值放在坑位里并更新坑位；重复寻找操作，直到相遇；最后将保存好的基准值放在相遇位置即可。

    可以看出，挖坑法与hoare版本的区别在于：挖坑法在单次寻找后就要改变元素的值，而hoare版本在一组寻找（左、右各一次）后才会交换元素的值。

    1. //挖坑法
    2. int PartSort2(int* a, int begin, int end)
    3. {
    4. 	int key = a[begin];
    5. 	int holei = begin;
    6. 	int left = begin;
    7. 	int right = end;
    8.  
    9. 	while (left < right)
    10. 	{
    11. 		while (left < right && a[right] >= key) //
    12. 		{
    13. 			right--;
    14. 		}
    15. 		a[holei] = a[right];
    16. 		holei = right;
    17.  
    18. 		while (left < right && a[left] <= key) //
    19. 		{
    20. 			left++;
    21. 		}
    22. 		a[holei] = a[left];
    23. 		holei = left;
    24. 	}
    25. 	a[holei] = key;
    26.  
    27. 	return holei;
    28. }

    ③双指针法

    基本思想为：

    开始时左指针指向首元素（基准值），右指针指向左指针的下一个位置（第二个元素）；两个指针的移动规则为：右指针每次向右移动一个元素，左指针只有在右指针指向的元素比基准值小时才会向右移动一个元素，左指针移动后立即交换左右指针指向的元素；直到右指针到达元素末尾停止；（此时左指针指向了最后一个比基准值小的元素）最后交换左指针值和基准值。

    1. //双指针
    2. static int PartSort3(int* a, int begin, int end)
    3. {
    4. 	int prev = begin;
    5. 	int cur = begin + 1;
    6.  
    7. 	while (cur <= end)
    8. 	{
    9. 		if (a[cur] < a[begin]) //
    10. 		{
    11. 			prev++;
    12. 			Swap(a + prev, a + cur);
    13. 		}
    14. 		cur++;
    15. 	}
    16. 	Swap(a + begin, a + prev);
    17.  
    18. 	return prev;
    19. }

    至此，一个初始版本的快速排序就写好了。

    该版本总是以第一个元素为基准值，虽然方便，但是存在一个弊端：对接近有序的元素集合排序时效率太低，为了解决弊端，可以进一步优化该算法：每次比较首元素、中间元素和末尾元素，选择三数的中间值作为基准值。为了使代码的改动相对较小，可以实现一个挑选函数，在PartSort()函数开始时调用该函数，交换首元素和该函数的返回值即可：

    1. //快排优化:
    2. //三数取中选key值
    3. int ChooseKeyi(int* a, int begin,int end)
    4. {
    5. 	if (a[begin] > a[end])
    6. 	{
    7. 		if (a[(begin + end) / 2] > a[begin])
    8. 			return begin;
    9. 		else if (a[(begin + end) / 2] < a[end])
    10. 			return end;
    11. 		else
    12. 			return (begin + end) / 2;
    13. 	}
    14. 	else
    15. 	{
    16. 		if (a[(begin + end) / 2] < a[begin])
    17. 			return begin;
    18. 		else if (a[(begin + end) / 2] > a[end])
    19. 			return end;
    20. 		else
    21. 			return (begin + end) / 2;
    22. 	}
    23. }

    至此，一个相对完美的递归版本的快速排序就完成了，下面对其进行了优化汇总：

    1. int ChooseKeyi(int* a, int begin,int end)
    2. {
    3. 	if (a[begin] > a[end])
    4. 	{
    5. 		if (a[(begin + end) / 2] > a[begin])
    6. 			return begin;
    7. 		else if (a[(begin + end) / 2] < a[end])
    8. 			return end;
    9. 		else
    10. 			return (begin + end) / 2;
    11. 	}
    12. 	else
    13. 	{
    14. 		if (a[(begin + end) / 2] < a[begin])
    15. 			return begin;
    16. 		else if (a[(begin + end) / 2] > a[end])
    17. 			return end;
    18. 		else
    19. 			return (begin + end) / 2;
    20. 	}
    21. }
    22.  
    23. //hoare
    24. int PartSort1(int* a, int begin, int end)
    25. {
    26. 	Swap(a + ChooseKeyi(a, begin, end), a + begin);
    27.  
    28. 	int keyi = begin;
    29. 	int left = begin;
    30. 	int right = end;
    31.  
    32. 	while (left < right)
    33. 	{
    34. 		//升序:右边找小
    35. 		while (left < right && a[right] >= a[keyi]) //
    36. 		{
    37. 			right--;
    38. 		}
    39. 		//升序:左边找大
    40. 		while (left < right && a[left] <= a[keyi]) //
    41. 		{
    42. 			left++;
    43. 		}
    44.  
    45. 		Swap(a + left, a + right);
    46. 	}
    47. 	Swap(a + left, a + keyi);
    48.  
    49. 	return left;
    50. }
    51.  
    52. //挖坑法
    53. int PartSort2(int* a, int begin, int end)
    54. {
    55. 	Swap(a + ChooseKeyi(a, begin, end), a + begin);
    56.  
    57. 	int key = a[begin];
    58. 	int holei = begin;
    59. 	int left = begin;
    60. 	int right = end;
    61.  
    62. 	while (left < right)
    63. 	{
    64. 		while (left < right && a[right] >= key) //
    65. 		{
    66. 			right--;
    67. 		}
    68. 		a[holei] = a[right];
    69. 		holei = right;
    70.  
    71. 		while (left < right && a[left] <= key) //
    72. 		{
    73. 			left++;
    74. 		}
    75. 		a[holei] = a[left];
    76. 		holei = left;
    77. 	}
    78. 	a[holei] = key;
    79.  
    80. 	return holei;
    81. }
    82.  
    83. //双指针
    84. int PartSort3(int* a, int begin, int end)
    85. {
    86. 	Swap(a + ChooseKeyi(a, begin, end), a + begin);
    87.  
    88. 	int prev = begin;
    89. 	int cur = begin + 1;
    90.  
    91. 	while (cur <= end)
    92. 	{
    93. 		if (a[cur] < a[begin]) //
    94. 		{
    95. 			prev++;
    96. 			Swap(a + prev, a + cur);
    97. 		}
    98. 		cur++;
    99. 	}
    100. 	Swap(a + begin, a + prev);
    101.  
    102. 	return prev;
    103. }
    104.  
    105.  
    106. void QuickSort(int* a, int begin, int end)
    107. {
    108. 	if (begin >= end)
    109. 		return;
    110.  
    111. 	int keyi = PartSort3(a, begin, end);//三个版本选择其一即可
    112. 	QuickSort(a, begin, keyi - 1);
    113. 	QuickSort(a, keyi + 1, end);
    114. }
    <2>非递归版本

    所有递归算法均可转化为非递归，该算法也不例外。

    只需要借助栈，每次将元素的处理区间进栈，以便左区间处理完后可以找到右区间即可。（该算法用到的有关栈的接口函数与博客【特殊的线性表——栈和队列及其C语言实现】保持一致。）

    1. void QuickSortNonR(int* a, int begin, int end)
    2. {
    3. 	ST stack;
    4. 	STInit(&stack);
    5. 	STPush(&stack, end);
    6. 	STPush(&stack, begin);
    7.  
    8. 	while (!STEmpty(&stack))
    9. 	{
    10. 		int left = STTop(&stack);
    11. 		STPop(&stack);
    12. 		int right = STTop(&stack);
    13. 		STPop(&stack);
    14.  
    15. 		int keyi = PartSort3(a, left, right);
    16. 		if (keyi + 1 < right)
    17. 		{
    18. 			STPush(&stack, right);
    19. 			STPush(&stack, keyi+1);
    20. 		}
    21. 		if (left < keyi - 1)
    22. 		{
    23. 			STPush(&stack, keyi-1);
    24. 			STPush(&stack, left);
    25. 		}
    26. 	}
    27. 	STDestroy(&stack);
    28. }

    （3）分析

    若将快速排序的时间以示意图的形式表示，是一颗二叉树，树高为log_{2}n，而每层的时间为O(n)：

    因此，快速排序的时间复杂度为O\left ( n*log_{2}n \right )

    递归版本需要不断地开辟栈帧，非递归版本需要额外空间来存放区间信息，栈帧对应的空间可以复用，区间是不断地减半的，因此不论哪种，空间复杂度为O\left ( log_{2}n \right )

    显然，快速排序是不稳定的。

    四、归并排序

    二路归并排序

    （1）基本思想

    将已经有序的两个子序列合并，得到一个完全有序的序列。

    （2）代码实现（升序）

    如何进行合并呢？先开辟一块连续空间用于存放合并的结果，然后利用两个“指针”分别遍历两个有序子序列，遍历时每次比较两个指针所指向值的大小，将值小的元素放在结果区并将该指针移动一个元素；任意一个序列遍历完毕后，另一个序列若有剩余元素，将其逐个添加至结果区即可。

    <1>递归版本
    1. void _MergeSort(int* a, int begin, int end, int* tmp)
    2. {
    3. 	if (begin >= end)
    4. 		return;
    5.  
    6. 	int mid = (begin + end) / 2;
    7. 	_MergeSort(a, begin, mid, tmp);
    8. 	_MergeSort(a, mid+1, end, tmp);
    9.  
    10. 	int index1 = begin;
    11. 	int index2 = mid + 1;
    12. 	int i = begin;
    13. 	while (index1 <= mid && index2 <= end)
    14. 	{
    15. 		if (a[index1] < a[index2]) //
    16. 		{
    17. 			tmp[i++] = a[index1++];
    18. 		}
    19. 		else
    20. 		{
    21. 			tmp[i++] = a[index2++];
    22. 		}
    23. 	}
    24. 	while (index1 <= mid)
    25. 	{
    26. 		tmp[i++] = a[index1++];
    27. 	}
    28. 	while (index2 <= end)
    29. 	{
    30. 		tmp[i++] = a[index2++];
    31. 	}
    32. 	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
    33. }
    34.  
    35. void MergeSort(int* a, int n)
    36. {
    37. 	int* tmp = (int*)malloc(sizeof(int) * n);
    38. 	if (tmp == NULL)
    39. 	{
    40. 		perror("malloc error");
    41. 		return;
    42. 	}
    43.  
    44. 	_MergeSort(a, 0, n - 1, tmp);
    45. 	free(tmp);
    46. }
    <2>非递归版本

    非递归直接模拟合并过程即可。

    1. void MergeSortNonR(int* a, int n)
    2. {
    3. 	int* tmp = (int*)malloc(sizeof(int) * n);
    4. 	if (tmp == NULL)
    5. 	{
    6. 		perror("malloc error");
    7. 		return;
    8. 	}
    9.  
    10. 	int gap = 1;
    11. 	while (gap < n)
    12. 	{
    13. 		for (int i = 0; i < n; i += 2 * gap)
    14. 		{
    15. 			int begin1 = i, end1 = i + gap - 1;
    16. 			int begin2 = i + gap, end2 = i + 2 * gap - 1;
    17. 			if (end1 >= n || begin2 >= n)
    18. 				break;
    19. 			if (end2 >= n)
    20. 				end2 = n - 1;
    21.  
    22. 			int j = i;
    23. 			while (begin1 <= end1 && begin2 <= end2)
    24. 			{
    25. 				if (a[begin1] < a[begin2]) //
    26. 				{
    27. 					tmp[j++] = a[begin1++];
    28. 				}
    29. 				else
    30. 				{
    31. 					tmp[j++] = a[begin2++];
    32. 				}
    33. 			}
    34. 			while (begin1 <= end1)
    35. 			{
    36. 				tmp[j++] = a[begin1++];
    37. 			}
    38. 			while (begin2 <= end2)
    39. 			{
    40. 				tmp[j++] = a[begin2++];
    41. 			}
    42. 			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    43. 		}
    44. 		gap *= 2;
    45. 	}
    46.  
    47. 	free(tmp);
    48. }

    （3）分析

    时间复杂度为O\left ( n*log_{2}n \right )

    归并过程需要开辟空间来暂存归并结果，因此空间复杂度为O\left ( n \right )

    归并后相同元素的相对次序并不会改变，二路归并是稳定的。

  • 相关阅读:
    网络总结上
    Docker 学习笔记总结(二)
    莱特兄弟的家庭教育
    一个AI玩遍多个游戏
    HTML期末大学生网页设计作业——奇恩动漫HTML (1页面) HTML+CSS+JS网页设计期末课程大作业
    适用于LLM的代理搜索增强事实评估器 (Search-Augmented Factuality Evaluator，SAFE)
    EEG微状态：注意力缺陷多动症ADHD新的功能生物标记物
    jQuery网页开发案例:jQuery常用API--jQuery 元素操作
    LLM之幻觉（一）：大语言模型幻觉解决方案综述
    在SPDK中使能E810网卡ADQ特性
  • 原文地址：https://blog.csdn.net/m0_74440699/article/details/136110259