• 【玄说✅数据结构与算法】【初阶】—— 排序

    目录

    🎈 排序的概念及其运用

    🎈 插入排序 

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

    🎈 选择排序

    🎈 堆排序 

    🎈 冒泡排序

    🎈 快速排序 

    🎈 归并排序

    🎈 非递归排序

    排序的概念及其运用

    排序的概念

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

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

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

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

    排序运用 

    常见的排序算法 

     

    插入排序 

    插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

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

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

    1. // 插入排序
    2. void InsertSort(int* a, int n)
    3. {
    4. 	assert(a);
    5.  
    6. 	for (int i = 0; i < n - 1; i++)
    7. 	{
    8. 		// 将x插入[0, end]有序区间
    9. 		int end = i;
    10. 		int x = a[end + 1];
    11. 		while (end >= 0)
    12. 		{
    13. 			if (a[end] > x)
    14. 			{
    15. 				a[end + 1] = a[end];
    16. 				--end;
    17. 			}
    18. 			else
    19. 			{
    20. 				break;
    21. 			}
    22. 		}
    23. 		a[end + 1] = x;
    24. 	}
    25. }

    直接插入排序的特性总结：

    1. 元素集合越接近有序，直接插入排序算法的时间效率越高

    2. 时间复杂度： O(N^2)

    3. 空间复杂度： O(1 )，它是一种稳定的排序算法

    4. 稳定性：稳定

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

    直接插入排序的思想上优化

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

    希尔排序的特性总结：

    1. 希尔排序是对直接插入排序的优化。

    2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

    3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定：

     4. 稳定性：不稳定

    选择排序

    基本思想：

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

    直接选择排序: 

    • 在元素集合array[i]--array[n-1 ]中选择关键码最大(小)的数据元素
    • 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
    • 在剩余的array[i]--array[n-2]（array[i+1 ]--array[n-1 ]）集合中，重复上述步骤，直到集合剩余1个元素
    1. void swap(int *a,int *b) //交換兩個變數
    2. {
    3.     int temp = *a;
    4.     *a = *b;
    5.     *b = temp;
    6. }
    7. void selection_sort(int arr[], int len)
    8. {
    9.     int i,j;
    10.  
    11.         for (i = 0 ; i < len - 1 ; i++)
    12.     {
    13.                 int min = i;
    14.                 for (j = i + 1; j < len; j++)     //走訪未排序的元素
    15.                         if (arr[j] < arr[min])    //找到目前最小值
    16.                                 min = j;    //紀錄最小值
    17.                 swap(&arr[min], &arr[i]);    //做交換
    18.         }
    19. }

    堆排序 

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

     

    直接选择排序的特性总结：

    1. 堆排序使用堆来选数，效率就高了很多。

    2. 时间复杂度： O(N*logN)

    3. 空间复杂度： O(1 )

    4. 稳定性：不稳定
     

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 100010;
    7.  
    8. int n, m;
    9. int h[N], size;
    10.  
    11. void down(int u)
    12. {
    13.     int t = u;
    14.     if(u * 2 <= size && h[u * 2] < h[t] ) t = u * 2;
    15.     if(u * 2 + 1<= size && h[u * 2 + 1] < h[t] ) t = u * 2 + 1;
    16.     if(u != t)
    17.     {
    18.         swap(h[u], h[t]);
    19.         down(t);
    20.     }
    21. }
    22.  
    23. int main()
    24. {
    25.     cin >> n >> m;
    26.     for(int i = 1; i <= n ; i ++ ) scanf("%d", h[i]);
    27.     
    28.     for(int i = n / 2; i; i -- ) down(i);
    29.     
    30.     while(m -- )
    31.     {
    32.         printf("%d ", h[1]);
    33.         h[1] = h[size --];
    34.         down(1);
    35.     }
    36. }

    冒泡排序

    冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

    作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

    算法步骤

    比较相邻的元素。如果第一个比第二个大，就交换他们两个。

    对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

    针对所有的元素重复以上的步骤，除了最后一个。

    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    1. #include 
    2. void bubble_sort(int arr[], int len) {
    3.         int i, j, temp;
    4.         for (i = 0; i < len - 1; i++)
    5.                 for (j = 0; j < len - 1 - i; j++)
    6.                         if (arr[j] > arr[j + 1]) {
    7.                                 temp = arr[j];
    8.                                 arr[j] = arr[j + 1];
    9.                                 arr[j + 1] = temp;
    10.                         }
    11. }
    12. int main() {
    13.         int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    14.         int len = (int) sizeof(arr) / sizeof(*arr);
    15.         bubble_sort(arr, len);
    16.         int i;
    17.         for (i = 0; i < len; i++)
    18.                 printf("%d ", arr[i]);
    19.         return 0;
    20. }

    快速排序 

    快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

    算法描述

    快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

    • 从数列中挑出一个元素，称为 “基准”（pivot）；
    • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
    • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 1e6 + 10;
    6.  
    7. int n;
    8. int q[N];
    9.  
    10. void quick_sort(int l, int r)
    11. {
    12.     if(l >= r) return;
    13.     
    14.     int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    15.     while(i < j)
    16.     {
    17.         do i ++ ; while(q[i] < x);
    18.         do j -- ; while(q[j] > x);
    19.         if(i < j) swap(q[i], q[j]);
    20.     }
    21.     
    22.     quick_sort(l, j), quick_sort(j + 1, r);
    23. }
    24.  
    25. int main()
    26. {
    27.     cin >> n;
    28.     for(int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    29.     
    30.     quick_sort(0, n - 1);
    31.     
    32.     for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    33.     
    34.     return 0;
    35. }

    归并排序

    归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

    归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

    基本思想

    归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

    • 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
    • 解决（Conquer）：用合并排序法对两个子序列递归的排序。
    • 合并（Combine）：合并两个已排序的子序列已得到排序结果。

     

    归并排序的特性总结：

    1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

    2. 时间复杂度： O(N*logN)

    3. 空间复杂度： O(N)

    4. 稳定性：稳定

    1. void _MergeSort(int* a, int left, int right, int* tmp)
    2. {
    3. 	if (left >= right) return;
    4.  
    5. 	int mid = (left + right) / 2;
    6.  
    7. 	_MergeSort(a, left, mid, tmp);
    8. 	_MergeSort(a, mid + 1, right, tmp);
    9.  
    10. 	int begin1 = left, end1 = mid;
    11. 	int begin2 = mid + 1, end2 = right;
    12. 	int i = left;
    13.  
    14. 	while (begin1 <= end1 && begin2 <= end2)
    15. 	{
    16. 		if (a[begin1] < a[begin2])
    17. 		{
    18. 			tmp[i++] = a[begin1++];
    19. 		}
    20. 		else
    21. 		{
    22. 			tmp[i++] = a[begin2++];
    23. 		}
    24. 	}
    25.  
    26. 	while (begin1 <= end1)
    27. 	{
    28. 		tmp[i++] = a[begin1++];
    29. 	}
    30.  
    31. 	while (begin2 <= end2)
    32. 	{
    33. 		tmp[i++] = a[begin2++];
    34. 	}
    35.  
    36. 	// tmp数组拷贝回a
    37. 	for (int j = left; j <= right; j++)
    38. 	{
    39. 		a[j] = tmp[j];
    40. 	}
    41. }
    42.  
    43. void MergeSort(int* a, int n)
    44. {
    45. 	int* tmp = (int*)malloc(sizeof(int) * n);
    46. 	if (tmp == NULL)
    47. 	{
    48. 		printf("malloc fail\n");
    49. 		exit(-1);
    50. 	}
    51.  
    52. 	_MergeSort(a, 0, n - 1, tmp);
    53.  
    54. 	free(tmp);
    55.  
    56. 	return;
    57. }
    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 1e6 + 10;
    7.  
    8. int n;
    9. int q[N], tmp[N];
    10.  
    11. void m_g(int l, int r)
    12. {
    13.     if(l >= r) return;
    14.     
    15.     int mid = l + r >> 1;
    16.     m_g(l, mid), m_g(mid + 1, r);
    17.     
    18.     int i = l, j = mid + 1, k = 0;
    19.     while(i <= mid && j <= r)
    20.         if(q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
    21.         else tmp[k ++ ] = q[j ++ ];
    22.  
    23.     
    24.     while(i <= mid) tmp[k ++ ] = q[i ++ ];
    25.     while(j <= r) tmp[k ++ ] = q[j ++ ];
    26.     
    27.     for(i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
    28. }
    29.  
    30. int main()
    31. {
    32.     cin >> n;
    33.     for(int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    34.     
    35.     m_g(0, n - 1);
    36.     
    37.     for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    38.     
    39.     return 0;
    40. }

    非递归排序

     归并排序(非递归实现)_liuwxye的博客-CSDN博客_归并排序非递归

  • 相关阅读:
    excel自动翻译-excel一键自动翻译免费
    2386. 找出数组的第 K 大和 (每日一难phase2-day2)
    《C++新经典》第19章 STL标准模板库大局观
    python学习之5个让日常编码更方便简单的库
    【Python Web】Flask框架（九）前端+python+MYSQL案例
    Mysql数据库文件太大无法导入数据库
    BS-GX-018 基于SSM实现在校学生考试系统
    MathType需要安装一个较新版本的MT Extra(TrueType)字体解决办法
    BRPC学习
    chattr：修改文件的特殊属性
  • 原文地址：https://blog.csdn.net/forever_bryant/article/details/126082452