• 排序 “叁” 之交换排序

    目录

    1. 基本思想

    2.冒泡排序

    2.1 基本思想

    2.2 代码示例

    2.3 冒泡排序的特性总结

    3.快速排序

    3.1 基本思想

    🌵hoare版本

    🌵挖坑法

    ​编辑

    🌵前后指针版本

    ​编辑

    3.2 快速排序优化

    🌻三数取中法选key

    3.4 快速排序的特性总结

    1. 基本思想

            所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

    2.冒泡排序

    2.1 基本思想

    冒泡排序是一种简单直观的排序算法，其基本思想是通过不断比较相邻的元素并交换位置，将最大（或最小）的元素逐步“冒泡”到最后（或最前）。

    冒泡排序的具体步骤：

    1. 比较相邻元素：从数组的第一个元素开始，依次比较相邻的两个元素，如果顺序不对则交换它们的位置，确保较大的元素向后移动。
    2. 一轮冒泡：经过一轮比较和交换操作，最大的元素会沉到数组的最后位置。重复这个过程，直到没有需要交换的元素为止。
    3. 多轮冒泡：重复进行上述步骤，每次冒泡操作都会将当前未排序部分的最大元素移动到正确的位置。经过多轮冒泡，整个数组就会逐步有序。
    4. 优化：可以在每一轮冒泡中记录是否有元素交换的标志，如果某一轮没有元素交换，说明数组已经有序，可以提前结束排序。

    下面是一个简单的示例，演示冒泡排序的步骤：

    假设要排序的数组为：[5, 3, 8, 2, 1]

    • 第一轮冒泡：比较并交换，数组变为 [3, 5, 2, 1, 8]
    • 第二轮冒泡：比较并交换，数组变为 [3, 2, 1, 5, 8]
    • 第三轮冒泡：比较并交换，数组变为 [2, 1, 3, 5, 8]
    • 第四轮冒泡：比较并交换，数组变为 [1, 2, 3, 5, 8]

    经过四轮冒泡排序，数组变为有序状态：[1, 2, 3, 5, 8]。

    2.2 代码示例

    1. //交换
    2. void Swap(int* p, int* q)
    3. {
    4. 	int tmp = *p;
    5. 	*p = *q;
    6. 	*q = tmp;
    7. }
    8.  
    9. //冒泡排序
    10. void BubbleSort(int* a, int n)
    11. {
    12. 	for (int i = 0; i < n - 1; i++)
    13. 	{
    14. 		//标志位，用于记录本轮是否发生了元素交换
    15. 		bool flag = false;
    16. 		for (int j = 0; j < n - i - 1; j++)
    17. 		{
    18. 			if (a[j + 1] < a[j])
    19. 			{
    20. 				//交换相邻元素
    21. 				Swap(&a[j + 1], &a[j]);
    22. 				flag = true;
    23. 			}
    24. 		}
    25. 		//如果本轮没有发生元素交换，说明数组已经有序，提前结束排序
    26. 		if (!flag)
    27. 			break;
    28. 	}
    29. }
    30.  
    31. //打印
    32. void PrintSort(int* a, int n)
    33. {
    34. 	for (int i = 0; i < n; i++)
    35. 	{
    36. 		printf("%d ", a[i]);
    37. 	}
    38. 	printf("\n");
    39. }
    40.  
    41. //测试
    42. int main()
    43. {
    44. 	int a[] = { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };
    45. 	BubbleSort(a, sizeof(a) / sizeof(int));
    46. 	PrintSort(a, sizeof(a) / sizeof(int));
    47.  
    48. 	return 0;
    49. }

    2.3 冒泡排序的特性总结

    1. 时间复杂度：冒泡排序的平均时间复杂度为O(n^2)，最坏情况下为O(n^2)，最好情况下为O(n)。因此，冒泡排序对于大规模数据集并不是一个高效的选择。
    2. 空间复杂度：冒泡排序的空间复杂度为O(1)，因为它只需要一个额外的临时变量来进行元素交换。
    3. 稳定性：冒泡排序是一种稳定的排序算法，相同元素的相对位置在排序前后不会改变。
    4. 适用场景：由于冒泡排序的效率较低，通常不推荐在实际应用中使用。但对于小规模数据集或者教学目的，冒泡排序是一个很好的入门算法。
    5. 优缺点：冒泡排序的优点是实现简单，代码易于理解；缺点是效率低下，不适用于大规模数据集。

    3.快速排序

    3.1 基本思想

    快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，它的核心思想是通过分治法来实现排序。

    具体步骤如下：

    1. 选择一个基准值（通常选择第一个元素）。
    2. 将小于基准值的元素移到基准值的左边，将大于基准值的元素移到基准值的右边。
    3. 对基准值左右两侧的子数组分别递归地进行快速排序。

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

    🌵hoare版本

    思想步骤：

    1. 选择一个基准元素（通常选择数组的中间元素）。
    2. 使用两个指针，一个指向数组的起始位置，另一个指向数组的末尾位置。
    3. 右指针向左移动，直到找到一个小于基准元素的元素。
    4. 左指针向右移动，直到找到一个大于基准元素的元素。
    5. 左右指针分别找到元素后，交换它们各自位置的数值。
    6. 重复步骤3到步骤5，直到左指针和右指针相遇，将该位置的值与基准元素位置的值交换。
    7. 此时基准元素左边的元素都小于等于它，右边的元素都大于等于它。
    8. 递归地对基准元素左右两边的子数组进行快速排序。

    1. //交换
    2. void Swap(int* p, int* q)
    3. {
    4. 	int tmp = *p;
    5. 	*p = *q;
    6. 	*q = tmp;
    7. }
    8.  
    9. //快速排序
    10. void QuickSort(int* a, int begin, int end)
    11. {
    12. 	//如果子数组长度为1或0，则直接返回
    13. 	if (begin >= end)
    14. 		return;
    15.  
    16. 	//初始化左右指针和基准值
    17. 	int left = begin, right = end;
    18. 	int keyi = begin;
    19.  
    20. 	while (left < right)
    21. 	{
    22. 		//从右向左找第一个小于基准值的元素
    23. 		while (left < right && a[right] >= a[keyi])
    24. 		{
    25. 			--right;
    26. 		}
    27. 		//从左向右找第一个大于基准值的元素
    28. 		while (left < right && a[left] <= a[keyi])
    29. 		{
    30. 			++left;
    31. 		}
    32. 		//将找到的元素位置进行交换
    33. 		Swap(&a[right], &a[left]);
    34. 	}
    35. 	//将基准元素放到正确的位置上
    36. 	Swap(&a[left], &a[keyi]);
    37. 	keyi = left;
    38. 	//递归的对基准元素左右两侧的子数组进行快速排序
    39. 	QuickSort(a, begin, keyi - 1);
    40. 	QuickSort(a, keyi + 1, end);
    41. }
    42.  
    43. //打印
    44. void PrintSort(int* a, int n)
    45. {
    46. 	for (int i = 0; i < n; i++)
    47. 	{
    48. 		printf("%d ", a[i]);
    49. 	}
    50. 	printf("\n");
    51. }
    52.  
    53. //测试
    54. int main()
    55. {
    56. 	int a[] = { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };
    57. 	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
    58. 	PrintSort(a, sizeof(a) / sizeof(int));
    59.  
    60. 	return 0;
    61. }

    🌵挖坑法

    思想步骤：

    1. 先将第一个数据存放在临时变量key中，形成一个坑位。
    2. right开始向前移动，找比key位置小的值，找到后将right位置的值放进坑里，此时right位置作为新的坑。
    3. left开始向后移动，找比key位置大的值，找到后将left位置的值放进坑里，此时left位置作为新的坑。
    4. right接着向前找，left接着向后找，直到left与right相遇。
    5. 将key放入相遇时的坑里，排序完毕。

    1. // 挖坑法
    2. int PartSort(int* a, int begin, int end)
    3. {
    4.  
    5. 	//选择第一个元素作为基准元素
    6. 	int key = a[begin];
    7. 	int hole = begin;
    8.  
    9. 	while (begin < end)
    10. 	{
    11. 		//从右往左找到第一个小于基准元素的元素
    12. 		while (begin < end && a[end] >= key)
    13. 		{
    14. 			--end;
    15. 		}
    16. 		//将找到的元素填入左边的坑
    17. 		a[hole] = a[end];
    18. 		//更新坑的位置
    19. 		hole = end;
    20.  
    21. 		//从左往右找到第一个大于基准元素的元素
    22. 		while (begin < end && a[begin] <= key)
    23. 		{
    24. 			++begin;
    25. 		}
    26. 		//将找到的元素填入右边的坑
    27. 		a[hole] = a[begin];
    28. 		//更新坑的位置
    29. 		hole = begin;
    30. 	}
    31. 	//将基准元素放入最终的坑
    32. 	a[hole] = key;
    33.  
    34. 	return hole;
    35. }
    36.  
    37. void QuickSort(int* a, int begin, int end)
    38. {
    39. 	//如果子数组长度为1或0，则直接返回
    40. 	if (begin >= end)
    41. 		return;
    42.  
    43. 	int keyi = PartSort(a, begin, end);
    44. 	QuickSort(a, begin, keyi - 1);
    45. 	QuickSort(a, keyi + 1, end);
    46. }
    47.  
    48. //打印
    49. void PrintSort(int* a, int n)
    50. {
    51. 	for (int i = 0; i < n; i++)
    52. 	{
    53. 		printf("%d ", a[i]);
    54. 	}
    55. 	printf("\n");
    56. }
    57.  
    58.  
    59. //测试
    60. int main()
    61. {
    62. 	int a[] = { 1, 5, 7, 9, 0, 1, 2, 4, 8, 1, 3, 8, 6 };
    63. 	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
    64. 	PrintSort(a, sizeof(a) / sizeof(int));
    65.  
    66. 	return 0;
    67. }

     

    🌵前后指针版本

    思想步骤：

    1. 选择一个基准元素作为key（通常选择数组的第一个元素）。
    2. 使用两个指针，前指针prev指向序列开头，后指针cur指向prev指针的后一个位置。
    3. 判断cur指针指向的数据是否小于key，若小于，则prev指针后移一位（注意：prev只有在cur找到比key小的数时才加1），并将cur指向的内容与prev指向的内容交换，然后cur指针++。若大于，则cur指针++。
    4. 依次类推直到cur遍历完整个数组，最后将prev位置的值与key位置的值进行交换，则完成单趟排序。

    1. //交换
    2. void Swap(int* p, int* q)
    3. {
    4. 	int tmp = *p;
    5. 	*p = *q;
    6. 	*q = tmp;
    7. }
    8.  
    9. //前后指针法
    10. int PartSort(int* a, int begin, int end)
    11. {
    12. 	int key = begin;
    13.  
    14. 	int prev = begin;
    15. 	int cur = prev + 1;
    16.  
    17. 	while (cur <= end)
    18. 	{
    19. 		//如果cur位置的值小于key位置的值，
    20. 		//并且prev位置++后的值如果和cur位置的值不相等，
    21. 		//就交换prev位置和cur位置的值
    22. 		if (a[cur] < a[key] && ++prev != cur)
    23. 			Swap(&a[prev], &a[cur]);
    24.  
    25. 		++cur;
    26. 	}
    27.  
    28. 	Swap(&a[prev], &a[key]);
    29. 	key = prev;
    30.  
    31. 	return key;
    32. }
    33.  
    34.  
    35. void QuickSort(int* a, int begin, int end)
    36. {
    37. 	//如果子数组长度为1或0，则直接返回
    38. 	if (begin >= end)
    39. 		return;
    40.  
    41. 	int keyi = PartSort(a, begin, end);
    42. 	QuickSort(a, begin, keyi - 1);
    43. 	QuickSort(a, keyi + 1, end);
    44. }


    3.2 快速排序优化

    🌻三数取中法选key

    三数取中法是在快速排序算法中用于选择基准元素的一种策略。它的思想是从待排序数组中随机选择三个元素，然后取它们的中间值作为基准元素，这样可以尽量避免选择到极端的值作为基准元素，从而提高快速排序的效率。

    使用三数取中法选择基准元素的具体步骤：

    1. 从待排序数组中随机选择三个元素，通常是选择数组的第一个元素、中间元素和最后一个元素。
    2. 比较这三个元素，找到它们的中间值作为基准元素。可以使用简单的比较排序或者其他方法来找到中间值。
    3. 将选定的基准元素放置在数组的最左边（或者其他位置），并记录其值。
    4. 接下来的快速排序过程中，使用这个选定的基准元素进行分区操作，将小于基准元素的元素放在左边，大于基准元素的元素放在右边。

    使用三数取中法选择基准元素可以有效地避免选择到极端值作为基准元素，从而提高快速排序的效率，减少最坏情况下的时间复杂度。这种方法在实际应用中被广泛采用，用以提高快速排序的性能。

    🍂代码示例：

    1. //交换
    2. void Swap(int* p, int* q)
    3. {
    4. 	int tmp = *p;
    5. 	*p = *q;
    6. 	*q = tmp;
    7. }
    8.  
    9. //三数取中
    10. int GetMidi(int* a, int begin, int end)
    11. {
    12. 	//选择三个元素的中间值作为基准元素
    13. 	int midi = (begin + end) / 2;
    14.  
    15. 	//确保 a[begin] <= a[midi] <= a[end]
    16. 	if (a[begin] < a[midi])
    17. 	{
    18. 		if (a[midi] < a[end])
    19. 			return midi;
    20. 		else if (a[begin] > a[end])
    21. 			return begin;
    22. 		else
    23. 			return end;
    24. 	}
    25. 	else //a[begin] > a[midi]
    26. 	{
    27. 		if (a[midi] > a[end])
    28. 			return midi;
    29. 		else if (a[begin] < a[end])
    30. 			return begin;
    31. 		else
    32. 			return end;
    33. 	}
    34. }
    35.  
    36. //快速排序
    37. void QuickSort(int* a, int begin, int end)
    38. {
    39. 	//如果子数组长度为1或0，则直接返回
    40. 	if (begin >= end)
    41. 		return;
    42.  
    43. 	int midi = GetMidi(a, begin, end);
    44. 	Swap(&a[midi], &a[begin]);
    45.  
    46. 	//初始化左右指针和基准值
    47. 	int left = begin, right = end;
    48. 	int keyi = begin;
    49.  
    50. 	while (left < right)
    51. 	{
    52. 		//从右向左找第一个小于基准值的元素
    53. 		while (left < right && a[right] >= a[keyi])
    54. 		{
    55. 			--right;
    56. 		}
    57. 		//从左向右找第一个大于基准值的元素
    58. 		while (left < right && a[left] <= a[keyi])
    59. 		{
    60. 			++left;
    61. 		}
    62. 		//将找到的元素位置进行交换
    63. 		Swap(&a[right], &a[left]);
    64. 	}
    65. 	//将基准元素放到正确的位置上
    66. 	Swap(&a[left], &a[keyi]);
    67. 	keyi = left;
    68. 	//递归的对基准元素左右两侧的子数组进行快速排序
    69. 	QuickSort(a, begin, keyi - 1);
    70. 	QuickSort(a, keyi + 1, end);
    71. }
    72.  
    73. //测试
    74. int main()
    75. {
    76. 	int a[] = { 1, 5, 7, 9, 0, 2, 4, 8, 3, 8, 6 };
    77. 	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
    78. 	PrintSort(a, sizeof(a) / sizeof(int));
    79.  
    80. 	return 0;
    81. }

    3.4 快速排序的特性总结

    1. 时间复杂度：平均时间复杂度为O(N*logN)，最坏情况下为O(N^2)，最好情况下为O(N*logN)。
    2. 空间复杂度：快速排序是一种原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。
    3. 稳定性：快速排序是一种不稳定的排序算法，即相同元素的相对位置可能会发生变化。
    4. 分治思想：快速排序使用分治思想，将数组分为两部分，分别对左右子数组进行排序。
  • 相关阅读:
    数字孪生轨道交通：“智慧化”监控疏通城市运行痛点
    从0开始的异世界编程 [3]
    数字信号处理——专栏说明篇
    康耐视深度学习ViDi-Plugins菜单介绍
    Django（4）表单
    MySQL一条SQL语句的执行过程
    python打包成可执行文件app(Mac版)
    mysql-视图/存储过程/触发器
    Logistic回归实战---疝气病症预测病马的死亡率
    程序员如何优雅地解决线上问题？
  • 原文地址：https://blog.csdn.net/weixin_65931202/article/details/138028182