• 排序(希尔、快速、归并排序)

    文章目录

            1.排序的概念及其运用

            2.插入排序

            3.选择排序

    文章内容

    1.排序的概念及其运用

    1.1排序的概念

            排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

            稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

            内部排序：数据元素全部放在内存中的排序。

            外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

    1.2排序运用

    1.3 常见的排序算法

          排序接口及性能测试的代码 (注意头文件) ：

    1. // 排序实现的接口
    2. // 插入排序
    3. void InsertSort(int* a, int n);
    4. // 希尔排序
    5. void ShellSort(int* a, int n);
    6. // 选择排序
    7. void SelectSort(int* a, int n);
    8. // 堆排序
    9. void AdjustDwon(int* a, int n, int root);
    10. void HeapSort(int* a, int n);
    11. // 冒泡排序
    12. void BubbleSort(int* a, int n)
    13. // 快速排序递归实现
    14. // 快速排序hoare版本
    15. int PartSort1(int* a, int left, int right);
    16. // 快速排序挖坑法
    17. int PartSort2(int* a, int left, int right);
    18. // 快速排序前后指针法
    19. int PartSort3(int* a, int left, int right);
    20. void QuickSort(int* a, int left, int right);
    21. // 快速排序 非递归实现
    22. void QuickSortNonR(int* a, int left, int right)
    23. // 归并排序递归实现
    24. void MergeSort(int* a, int n)
    25. // 归并排序非递归实现
    26. void MergeSortNonR(int* a, int n)
    27. // 计数排序
    28. void CountSort(int* a, int n)
    29. // 测试排序的性能对比
    30. void TestOP()
    31. {
    32. srand(time(0));
    33. const int N = 100000;
    34. int* a1 = (int*)malloc(sizeof(int)*N);
    35. int* a2 = (int*)malloc(sizeof(int)*N);
    36. int* a3 = (int*)malloc(sizeof(int)*N);
    37. int* a4 = (int*)malloc(sizeof(int)*N);
    38. int* a5 = (int*)malloc(sizeof(int)*N);
    39. int* a6 = (int*)malloc(sizeof(int)*N);
    40. for (int i = 0; i < N; ++i)
    41. {
    42. a1[i] = rand();
    43. a2[i] = a1[i];
    44. a3[i] = a1[i];
    45. a4[i] = a1[i];
    46. a5[i] = a1[i];
    47. a6[i] = a1[i];
    48. }
    49. int begin1 = clock();
    50. InsertSort(a1, N);
    51. int end1 = clock();
    52. int begin2 = clock();
    53. ShellSort(a2, N);
    54. int end2 = clock();
    55. int begin3 = clock();
    56. SelectSort(a3, N);
    57. int end3 = clock();
    58. int begin4 = clock();
    59. HeapSort(a4, N);
    60. int end4 = clock();
    61. int begin5 = clock();
    62. QuickSort(a5, 0, N-1);
    63. int end5 = clock();
    64. int begin6 = clock();
    65. MergeSort(a6, N);
    66. int end6 = clock();
    67. printf("InsertSort:%d\n", end1 - begin1);
    68. printf("ShellSort:%d\n", end2 - begin2);
    69. printf("SelectSort:%d\n", end3 - begin3);
    70. printf("HeapSort:%d\n", end4 - begin4);
    71. printf("QuickSort:%d\n", end5 - begin5);
    72. printf("MergeSort:%d\n", end6 - begin6);
    73. free(a1);
    74. free(a2);
    75. free(a3);
    76. free(a4);
    77. free(a5);
    78. free(a6);
    79. }

     2.插入排序

    2.1基本思想：

            直接插入排序是一种简单的插入排序法，其基本思想是：

            把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

            实际中我们玩扑克牌时，就用了插入排序的思想

            我们先保证【0，end】有序，之后再插入后一个，也使其变得有序。end是从起始位置开始，依次向后，这样就能保证【0，end】有序，end不断＋＋，表示不断向数组内插入新元素。

            

    2.2直接插入排序：

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

    直接插入排序的特性总结：
    1. 元素集合越接近有序，直接插入排序算法的时间效率越高
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)，它是一种稳定的排序算法
    4. 稳定性：稳定

    2.3 希尔排序( 缩小增量排序 )

            希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

        核心思想：让小的(大的)数，快速的到前面

    希尔排序的特性总结：

            1. 希尔排序是对直接插入排序的优化。
            2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
            3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
    希尔排序的时间复杂度都不固定：

            《数据结构(C语言版)》--- 严蔚敏

            

            希尔排序代码实现：

            单趟shell排序：

            相同颜色块发生交换，但交换完成后不能保证白块内的三个子块有序。随着gap的值不断减小，当gap = 1 时候，便是直接插入排序。

    希尔排序：

    1. void ShellSort(int* a, int n)
    2. {
    3.  
    4. 	//单躺希尔排序
    5. 	//int gap = 3;
    6.  
    7. 	//for (int j = 0; j < gap; j++)
    8. 	//{
    9. 	//	for (int i = 0; i < n - gap; i += gap)
    10. 	//	{
    11. 	//		int end = i;
    12. 	//		int tmp = a[end + gap];
    13.  
    14. 	//		while (end >= 0)
    15. 	//		{
    16. 	//			if (a[end] > tmp)
    17. 	//			{
    18. 	//				a[end + gap] = a[end];
    19. 	//				end -= gap;
    20. 	//			}
    21.  
    22. 	//			else
    23. 	//			{
    24. 	//				break;
    25. 	//			}
    26. 	//		}
    27. 	//		a[end + gap] = tmp;
    28. 	//	}
    29. 	//}
    30.  
    31.  
    32.  
    33.  
    34. 	int gap = n;
    35. 	while (gap > 1)
    36. 	{
    37. 		gap = gap / 3 + 1;
    38.  
    39. 		for (int i = 0; i < n - gap; ++i)
    40. 		{
    41. 			int end = i;
    42. 			int tmp = a[end + gap];
    43. 			while (end >= 0)
    44. 			{
    45. 				if (tmp < a[end])
    46. 				{
    47. 					a[end + gap] = a[end];
    48. 					end -= gap;
    49. 				}
    50. 				else
    51. 				{
    52. 					break;
    53. 				}
    54. 			}
    55. 			a[end + gap] = tmp;
    56. 		}
    57. 	}
    58.  
    59.  
    60. }

     

     3.选择排序

            3.1基本思想：

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

            3.2 直接选择排序:

      在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

    代码：

    1. void SelsctSort(int* a, int n)
    2. {
    3.  
    4. 	int begin = 0;
    5. 	int end = n - 1;
    6.  
    7. 	while (begin < end)
    8. 	{
    9. 		int mini = begin;
    10. 		int maxi = end;
    11.  
    12. 		for (int i = begin + 1; i <= end; i++)
    13. 		{
    14. 			if (a[i] < a[mini])
    15. 			{
    16. 				mini = i;
    17. 			}
    18.  
    19. 			if (a[i] > a[maxi])
    20. 			{
    21. 				maxi = i;
    22. 			}
    23.  
    24. 		}
    25. 		Swap(&a[begin] , &a[mini]);
    26.  
    27. 		//begin 位置与 maxi位置重合 
    28. 		//在上一步中最大值已经被挪到下标为mini的位置
    29. 		if (begin == maxi)
    30. 		{
    31. 			maxi = mini;
    32. 		}
    33.  
    34. 		Swap(&a[maxi], &a[end]);
    35. 		end--;
    36. 		begin++;
    37.  
    38. 	}
    39.  
    40. }

    直接选择排序的特性总结：
    1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)
    4. 稳定性：不稳定

    3.3 堆排序

            堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

            堆排序前面的博客讲过此处不再细讲：

     

    1. void AdjustDown(int* a, int size , int parent )
    2. {
    3. 	int child = parent * 2 + 1;
    4.  
    5. 	while (child < size)
    6. 	{
    7. 		if (a[child] < a[child + 1] && child + 1 < size)
    8. 		{
    9. 			child = child + 1;
    10. 		}
    11.  
    12. 		if (a[parent] < a[child])
    13. 		{
    14. 			Swap(&a[child], &a[parent]);
    15. 			parent = child;
    16. 			child = child * 2 + 1;
    17. 		}
    18. 		else
    19. 		{
    20. 			break;
    21. 		}
    22. 	}
    23.  
    24. }
    25.  
    26.  
    27.  
    28. void HeapSort(int* a, int n)
    29. {
    30. 	for (int i = (n - 2) / 2; i >= 0; i--)
    31. 	{
    32. 		AdjustDown(a, n , i);
    33. 	}
    34.  
    35. 	int end = n - 1;
    36.  
    37. 	while (end > 0)
    38. 	{
    39. 		Swap(&a[0],&a[end]);
    40. 		AdjustDown(a , end , 0);
    41. 		end--;
    42. 	}
    43.  
    44. }

    直接选择排序的特性总结：
    1. 堆排序使用堆来选数，效率就高了很多。
    2. 时间复杂度：O(N*logN)
    3. 空间复杂度：O(1)
    4. 稳定性：不稳定

    4.交换排序

           4.1 基本思想：

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

           4.2冒泡排序：

    冒泡排序老相识了......

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

    冒泡排序的特性总结：
    1. 冒泡排序是一种非常容易理解的排序
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)
    4. 稳定性：稳定

    4.3 快速排序

            快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

            快速排序有三个版本：

    1. hoare版本

            ​​​​​​​选出key一般为最左端的值，然后让右边先走，找出比key小的值，之后左端走，找出比key大的值，然后交换，相遇停止，把key值放在停止的位置。

            单趟排完以后要求左边的比key小，右边的比key大。

    问题来了，为什么选左边为key，先让右边的走？

            先说结论，因为要保证相遇位置的值小于key位置对应的值或者相遇位置就是key。

    第一种情况：R先走遍历完整个数组，没有发现小于key位置对应的值，与key位置相交。

    第二种情况：(R遇L)R找到比key位置小的值，L开始走找到比key位置大的值，交换。R向前走，此时与L相遇，这时下标对应的值是小于key，(L遇R)当R找到比key小，然后L开始走但是一直没找到比key大的值，直到相遇，这是相遇位置的值还是比key位置值小的值。

    代码：

    2. 挖坑法

            首先将坑位元素存储到key，然后找到小的元素放到坑位，之后对应小的元素就是坑位。如此循环往复。

    1. //挖坑法
    2.  
    3. void PartSort2(int* a, int begin, int end)
    4. {
    5. 	int key = a[begin];
    6. 	int piti = begin;
    7.  
    8. 	while (begin < end)
    9. 	{
    10. 		//右找小
    11. 		while (begin < end && a[end] >= key )
    12. 		{
    13. 			end--;
    14. 		}
    15.  
    16. 		a[piti] = a[end];
    17. 		piti = end;
    18.  
    19. 		//左找大
    20. 		while (begin < end && a[begin] <= key)
    21. 		{
    22. 			begin++;
    23. 		}
    24. 		
    25. 		a[piti] = begin;
    26. 		piti = begin;
    27.  
    28. 	}
    29.  
    30. 	a[piti] = key;
    31. 	return piti;
    32.  
    33. }

    3. 前后指针法

    注意红框地方，是前置++再去判断，不管进没有进判断语句，prev已经++

    1. int PatrSort3(int* a, int begin, int end)
    2. {
    3.  
    4. 	int prev = begin, cur = begin+1;
    5.  
    6. 	int keyi = begin;
    7.  
    8. 	int midi = GetMidIndex(a , begin ,end);
    9. 	Swap(&a[keyi],&a[midi]);
    10.  
    11. 	while (cur <= end)
    12. 	{
    13. 		//cur位置小于keyi发生交换
    14. 		if (a[cur] < a[keyi] && ++prev != cur)
    15. 		{
    16. 			//++prev;
    17. 			Swap(&a[prev], &a[cur]);
    18. 		}
    19.  
    20. 		cur++;
    21. 	}
    22.  
    23. 	Swap(&a[keyi],&a[prev]);
    24.  
    25. 	keyi = prev;
    26. 	return keyi;
    27.  
    28. }

    找到大小剧中的key，对快排优化。 

    1. int GetMidIndex(int* a, int begin, int end)
    2. {
    3. 	int mid = (begin + end) / 2;
    4. 	if (a[begin] < a[mid])
    5. 	{
    6. 		if (a[mid] < a[end])
    7. 		{
    8. 			return mid;
    9. 		}
    10. 		else if (a[begin] < a[end])
    11. 		{
    12. 			return end;
    13. 		}
    14. 		else
    15. 		{
    16. 			return begin;
    17. 		}
    18. 	}
    19. 	else // (a[begin] >= a[mid])
    20. 	{
    21. 		if (a[mid] > a[end])
    22. 		{
    23. 			return mid;
    24. 		}
    25. 		else if (a[begin] < a[end])
    26. 		{
    27. 			return begin;
    28. 		}
    29. 		else
    30. 		{
    31. 			return end;
    32. 		}
    33. 	}
    34. }

    快速排序：当end 与 begin 差值过小时，选择直接插入排序。

    1. void QuickSort(int* a, int begin, int end)
    2. {
    3. 	if (begin >= end)
    4. 	{
    5. 		return;
    6. 	}
    7.  
    8. 	if (end - begin > 10)
    9. 	{
    10. 		int keyi = PatrSort3(a , begin , end);
    11.  
    12. 		QuickSort(a , begin ,keyi- 1);
    13. 		QuickSort(a , keyi+1, end);
    14. 	}
    15. 	else
    16. 	{
    17. 		InsertSort(a+ begin , end-begin+1);
    18. 	}
    19.  
    20. }

    5. 归并排序

    5.1基本思想

            归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

    5.2归并排序 

    归并排序类似于后序遍历  左边return后，右边return  回到“根”后 ，然后开始排序。

    下图为归并排序的展开逻辑图。

    1. void _MergeSort(int* a, int begin , int end ,int* tmp)
    2. {
    3. 	if (begin >= end)
    4. 	{
    5. 		return;
    6. 	}
    7.  
    8. 	int mid = (begin + end) / 2;
    9. 	_MergeSort(a,begin,mid,tmp);
    10. 	_MergeSort(a, mid+1, end, tmp);
    11.  
    12. 	//归并
    13. 	int begin1 = begin;
    14. 	int end1 = mid;
    15. 	int begin2 = mid + 1;
    16. 	int end2 = end;
    17.  
    18. 	int i = begin1;
    19. 	while (begin1 <= end1 && begin2 <= end2)
    20. 	{
    21. 		if (a[begin1] < a[begin2])
    22. 		{
    23. 			tmp[i++] = a[begin1++];
    24. 		}
    25. 		else
    26. 		{
    27. 			tmp[i++] = a[begin2++];
    28. 		}
    29. 	}
    30.  
    31. 	while(begin1 <= end1)
    32. 	{
    33. 		tmp[i++] = a[begin1++];
    34. 	}
    35. 	while (begin2 <= end2)
    36. 	{
    37. 		tmp[i++] = a[begin2++];
    38. 	}
    39.  
    40. 	memcpy(a+begin , tmp+begin,(end-begin +1)* sizeof(int));
    41. }
    42.  
    43.  
    44.  
    45. void MergeSort(int* a, int n)
    46. {
    47. 	int* tmp = (int*)malloc(sizeof(int)* n);
    48. 	if (tmp == NULL)
    49. 	{
    50. 		perror("malloc fail");
    51. 	}
    52.  
    53. 	_MergeSort(a,0,n-1,tmp);
    54.  
    55. 	free(tmp);
    56. }

  • 相关阅读:
    文本和二进制混合存储
    华为面试宝典OD
    Python学习----Demo(pyecharts)
    SQL必会知识点（一）
    蓝桥杯真题：纯质数
    面试题——RabbitMQ
    面试被吊打系列：Android 性能优化应该怎么学？
    屎山代码踩坑记录：不要将一个类写的臃肿
    vscode 通过ssh 连接虚拟机vmware(ubuntu)
    Java中方法的定义及注意事项
  • 原文地址：https://blog.csdn.net/kqs__/article/details/132818086