devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

九大排序算法汇总+性能分析实验报告（插入排序、希尔排序、折半插入排序、冒泡排序、归并排序、快速排序、基数排序、堆排序、选择排序）_排序算法对比分析实验

作者：神奇cpp | 2024-07-14 10:36:13

赞

踩

排序算法对比分析实验

一、实验目的和要求

1.熟练掌握九种排序算法原理和时间复杂度

2.综合比较各种排序算法时间性能

3.排序算法实验经验总结

二、实验内容与方法

1.插入排序

思路：从第一张开始拿牌，将这张牌前面的牌数比这张牌大的往后挪。
          没有比这张牌大的就放在这空隙中，那么到最后，每张牌前面的牌的大小都比自己小

步骤：
    用一个指针j代表他前面的牌，如果j这张牌比自己大，就让他往后面挪
    如果这张牌没自己大，就把自己放前面的牌后面（保证牌大小是从小到大）

插入排序代码

  1. void insertionSort(vector<int>& arr) {
  2. 	for (int i = 1; i < arr.size(); i++) {
  3. 		int key = arr[i];
  4. 		int j = i - 1;
  5. 		while (j >= 0 && arr[j] > key) {
  6. 			arr[j + 1] = arr[j];
  7. 			j--;
  8. 		}
  9. 		arr[j + 1] = key;
  10. 	}
  11. }

2.希尔排序（shell排序）

思路：先进行分组，不断细分。每组进行分别插入排序，这个算法优点是可以不用一位一位的移动并且减少逆序对数量
          越往后移动的次数越来越少，相较于一步一步移动，根据分组跳着移动，能够更快的移动到自己真正的位置

步骤：
    第一步分组，从每组n/2个数开始，每次每组大小除以二，直到每个组一个数，即朴素插入排序
    第二步从第gap到n每个数往回跳gap步，落脚点j就是他所在的分组，进行插入排序
    第三步重复一二步，在分成每个组一个数进行最后一次排序，即得到有序数列

shell排序代码

  1. void shellSort(vector<int>& arr) {
  2. 	int n = arr.size();
  3. 	for (int gap = n / 2; gap > 0; gap >>= 1) {
  4. 		for (int i = gap; i < n; i++) {
  5. 			int temp = arr[i];
  6. 			int j;
  7. 			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
  8. 				arr[j + gap] = arr[j];
  9. 			}
  10. 			arr[j + gap] = temp;
  11. 		}
  12. 	}
  13. }

3.折半插入排序

思路：插牌的时候一张牌一张牌看太慢了，所以用眼睛找一下该插入的位置（二分做眼睛找位置）

折半插入排序代码

  1. void binaryInsertionSort(vector<int>& arr) {
  2. 	for (int i = 1; i < arr.size(); i++) {
  3. 		int key = arr[i];
  4. 		int left = 0, right = i - 1;
  5. 		while (left <= right) {
  6. 			int mid = (left + right) / 2;
  7. 			if (arr[mid] > key) {
  8. 				right = mid - 1;
  9. 			}
  10. 			else {
  11. 				left = mid + 1;
  12. 			}
  13. 		}
  14. 		for (int j = i - 1; j >= left; j--) {		//将要找的位置的最右面数开始到找到的位置都往后挪，为插入的数腾位置
  15. 			arr[j + 1] = arr[j];
  16. 		}
  17. 		arr[left] = key;
  18. 	}
  19. }

4.冒泡排序

思路：每次都是将数组中最大的泡泡挪到最后
          若数组没发生挪动说明每个泡泡后面的泡泡都比他大

冒泡排序代码

  1. void bubbleSort(vector<int>& arr) {
  2. 	bool flag = true;
  3. 	for (int i = 0; i < arr.size() - 1 && flag; i++) {
  4. 		flag = false;
  5. 		for (int j = 0; j < arr.size() - i - 1; j++) {
  6. 			if (arr[j] > arr[j + 1]) {
  7. 				swap(arr[j], arr[j + 1]);
  8. 				flag = true;
  9. 			}
  10. 		}
  11. 	}
  12. }

5.归并排序

思路：先将每个数分到一个文件夹中，而后合并每两个文件夹，使合并后的大文件夹是有序的，最终合并到一个文件里

步骤：
    第一步将数列不断二分，分成小片段，对小片段进行操作
    第二步开出两个空间，分别存两个文件夹的数
    第三步为完成将两个空间（这两个空间数都是有序的）中最小的数提出了，放数组里。
          所以用两个指针i，j 分别比较两个空间内第一个数（即该空间最小数）将较小的放入数组，被放入的空间指针++
    第四步当有一个空间的数全都放入了数组里，则直接将剩余空间的所有数放入数组里
    当从小文件合并到大文件之后，就得到有序数列

归并排序代码

  1. void merge(vector<int>& arr, int l, int m, int r) {
  2. 	int n1 = m - l + 1;
  3. 	int n2 = r - m;
  4. 	vector<int> L(n1), R(n2);
  5. 	for (int i = 0; i < n1; i++) {
  6. 		L[i] = arr[l + i];
  7. 	}
  8. 	for (int j = 0; j < n2; j++) {
  9. 		R[j] = arr[m + 1 + j];
  10. 	}
  11. 	int i = 0, j = 0, k = l;
  12. 	while (i < n1 && j < n2) {
  13. 		if (L[i] <= R[j]) {
  14. 			arr[k] = L[i];
  15. 			i++;
  16. 		}
  17. 		else {
  18. 			arr[k] = R[j];
  19. 			j++;
  20. 		}
  21. 		k++;
  22. 	}
  23. 	while (i < n1) {
  24. 		arr[k] = L[i];
  25. 		i++;
  26. 		k++;
  27. 	}
  28. 	while (j < n2) {
  29. 		arr[k] = R[j];
  30. 		j++;
  31. 		k++;
  32. 	}
  33. }
  34.  
  35. void mergeSort(vector<int>& arr, int l, int r) {
  36. 	if (l < r) {
  37. 		int m = l + (r - l) / 2;
  38. 		mergeSort(arr, l, m);
  39. 		mergeSort(arr, m + 1, r);
  40. 		merge(arr, l, m, r);
  41. 	}
  42. }

6.快速排序

思路：分治思想 保证每个数左边的数都比他小，右边的数都比他大

步骤：
    第一步让最后一个数成为基准privot
    第二步确认指针i，如果从开始到最后有数比基准小，交换指针指向的数和这个数，则i和i左边的数一定是小于基准的
    （刚开始arr[i]是最左边的数，将小于基准的数和arr[i]进行交换，即将小于基准的数放在左边）
    第三步将i+1位置与基准交换，则基准的左边一定是小于基准的，基准右边的一定是大于基准的
    第四步从调整整个数组的基准，到每个数都是基准（即确保每个数的左边小于基准，右边大于基准）得到有序数列

快速排序代码

  1. int partition(vector<int>& arr, int low, int high) {
  2. 	int pivot = arr[high];
  3. 	int i = low - 1;
  4. 	for (int j = low; j < high; j++) {
  5. 		if (arr[j] < pivot) {
  6. 			i++;
  7. 			swap(arr[i], arr[j]);
  8. 		}
  9. 	}
  10. 	swap(arr[i + 1], arr[high]);
  11. 	return i + 1;
  12. }
  13. void quickSort(vector<int>& arr, int low, int high) {
  14. 	if (low < high) {
  15. 		int pi = partition(arr, low, high);
  16. 		quickSort(arr, low, pi - 1);
  17. 		quickSort(arr, pi + 1, high);
  18. 	}
  19. }

7.基数排序

思路：用空间换时间，比较两个数是高位大小比低位大小更重要，
    所以我们低位开始，相同位层进行排序，后面操作影响前面排序顺序即高位重要性高于低位，
    每个位层的排序为一个轮次，排序到最后就得到了有序

步骤：
    第一步找到最高位，求出轮次的次数
    第二步开出一个备用空间用来存每个轮次的结果 
    第三步开出十个桶进行位层排序，将这些数进行重要性分级
    第四步求前缀和，画出分区，将不同重要级区分开来
    第五步将桶中的数存进备用空间
    第六步更新数组
    第七步重复三四五六步得到有序数列

基数排序代码

  1. void countSort(vector<int>& arr, int exp) {
  2. 	int n = arr.size();
  3. 	vector<int> output(n);
  4. 	vector<int> count(10, 0);
  5. 	for (int i = 0; i < n; i++) {
  6. 		count[(arr[i] / exp) % 10]++;
  7. 	}
  8. 	for (int i = 1; i < 10; i++) {
  9. 		count[i] += count[i - 1];
  10. 	}
  11. 	for (int i = n - 1; i >= 0; i--) {
  12. 		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
  13. 		count[(arr[i] / exp) % 10]--;
  14. 	}
  15. 	for (int i = 0; i < n; i++) {
  16. 		arr[i] = output[i];
  17. 	}
  18. }
  19.  
  20. void radixSort(vector<int>& arr) {
  21. 	int maxVal = *max_element(arr.begin(), arr.end());
  22. 	for (int exp = 1; maxVal / exp > 0; exp *= 10) {
  23. 		countSort(arr, exp);
  24. 	}
  25. }

8.堆排序

思路：利用堆的性质找到最大值，再用选择排序原理进行排序

步骤：
    第一步先构建堆结构（根的值最大，每个节点一定是他那个子树的最大值，但不和同层的有什么关系）
    第二步将根（最大值）与最后一个元素交换，使得保证最后的节点是最大值
    第三步将被交换的元素放回堆里，使得剩余元素再次构成堆结构，保证根是最大值
    第四步 循环二三步，使得从最后到开始是从大到小，即得到开始到结束是从小到大

堆排序代码

  1. void heapify(vector<int>& arr, int n, int i) {
  2. 	int largest = i;
  3. 	int l = 2 * i + 1;
  4. 	int r = 2 * i + 2;
  5. 	if (l < n && arr[l] > arr[largest]) {
  6. 		largest = l;
  7. 	}
  8. 	if (r < n && arr[r] > arr[largest]) {
  9. 		largest = r;
  10. 	}
  11. 	if (largest != i) {
  12. 		swap(arr[i], arr[largest]);
  13. 		heapify(arr, n, largest);
  14. 	}
  15. }
  16.  
  17. void treeSelectionSort(vector<int>& arr) {
  18. 	int n = arr.size();
  19. 	for (int i = n / 2 - 1; i >= 0; i--) {
  20. 		heapify(arr, n, i);
  21. 	}
  22. 	for (int i = n - 1; i > 0; i--) {
  23. 		swap(arr[0], arr[i]);
  24. 		heapify(arr, i, 0);
  25. 	}
  26. }

9.选择排序

思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

选择排序代码

  1. void selectionSort(vector<int>& arr) {
  2. 	int n = arr.size();
  3. 	for (int i = 0; i < n - 1; i++) {
  4. 		int minIndex = i;
  5. 		for (int j = i + 1; j < n; j++) {
  6. 			if (arr[j] < arr[minIndex]) {
  7. 				minIndex = j;
  8. 			}
  9. 		}
  10. 		swap(arr[i], arr[minIndex]);
  11. 	}
  12. }

三、实验步骤和过程

1.算法性能分析

 说明：通过C++语言实现多种排序方式，分别对这些排序算法进行测试。记录数据与绘制对数图表如下。本实验选取的理论值基准均为数据规模为1000000时的测试数据。 但由于设备能力有限，数据来源于其他博客，本文附上的代码只是简单的对比各个排序算法在100000数据量时的运行时间对比，让读者能够更直观的看到各个排序算法时间复杂度方面的差距，从而更好的理解这些算法。

理论上各个算法的时间复杂度、空间复杂度和稳定性如下表，其中堆排序、快速排序和归并排序复杂度是（n\log_2 n）较为优秀，在一定情况下基数排序的速度出奇快，但是他的条件更为苛刻，适用面相较于其他更窄。其他时间复杂度是（n^2）主要是思路简单，代码量少，但对大数据实用性差。

（图片来源：https://blog.csdn.net/ytusdc/article/details/102528482）

2.算法对比分析

实验步骤：分别对各个排序算法进行运行时间的测量，数据规模从10-1000000。通过记录每个算法运行的时间，记录成表格，绘制成折线图。来更直观的比对每种排序算法的时间复杂度优劣，进而分析其优缺点。

冒泡排序插入排序折半插入排序希尔排序归并排序堆排序快速排序基数排序选择排序
100.00050.00040.00040.000533.40E-060.000171.00E-080.000274.00E-04
1000.001050.00150.00130.00212.60E-050.001051.00E-080.000391.30E-03
10000.004580.003050.001850.006040.00030.00160.0000950.0005650.00205
100000.47130.111150.07890.013950.0080.00240.001450.003040.0915
10000046.271710.12056.69590.05560.12460.04070.01780.02569.6635
10000004569.761059.13736.4410.67441.308950.42470.208350.1802921.265

（图片原创）

根据图表可以将这几个排序算法分成三类：

        第一类，简单排序。即冒泡、选择和插入排序。这几种排序方法的优点在于简单直观，代码好写，并且在数据规模较小时运算速度有些微优势。缺点在于，当数据规模增大时，简单排序的耗时会很快增加到令人难以忍受的程度。因此，这三种排序算法适用于数据规模小的情况。推荐插入排序和选择排序。

        第二类，希尔排序、归并排序和堆排序。这三种排序的时间复杂度优于O(n^2).可以应对较多情况。 

        第三类，快速排序、基数排序和计数排序。基数排序和计数排序时间复杂度到达线性级别。而快速排序复杂度中隐含的常数因子很小，是(n\log_2n)复杂度级别中最快的一种排序方法。这三种排序方法速度极快，然而空间占用较高(归并排序也有空间占用的问题)，并且对待排序数据有要求(快排数据不能是顺序的，基数排序需要数据有基数，基数排序需要数据可以计数)。在数据规模特别大时，需要考虑空间复杂度的问题。

四、实验结论和体会

实验结论：在处理小规模数据排序问题时，插入排序和选择排序是较好的选择，冒泡排序也是可选的算法。在数据规模较大时，应该选择希尔排序、堆排序、归并排序、快速排序、基数排序或基数排序。并且，数据规模大时，若采用归并排序、快速排序、基数排序或计数排序，需要考虑空间复杂度的问题。

实验体会：我们需要应对不同情况使用不同的排序算法。待排序数据的规模，极差，类型和基础有序度，都是我们选择排序算法时需要考虑的东西。不同的排序算法适合不同的数据，当我们遇到问题时不要只盯着一种排序算法用，还需要考虑数据性质。

五、实验代码

  1. //大作业：八大排序算法（ 插入排序 希尔排序 折半插入排序 树形选择排序 冒泡排序 
  2. //						归并排序 快速排序 基数排序）
  3. #include <iostream>
  4. #include <chrono>
  5. #include <random>
  6. #include <vector>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. // 插入排序
  11. /*
  12. 	思路：从第一张开始拿牌，将这张牌前面的牌数比这张牌大的往后挪。
  13. 		  没有比这张牌大的就放在这空隙中，那么到最后，每张牌前面的牌的大小都比自己小
  14. 	用一个指针j代表他前面的牌，如果j这张牌比自己大，就让他往后面挪
  15. 	如果这张牌没自己大，就把自己放前面的牌后面（保证牌大小是从小到大）
  16. */
  17. void insertionSort(vector<int>& arr) {
  18. 	for (int i = 1; i < arr.size(); i++) {
  19. 		int key = arr[i];
  20. 		int j = i - 1;
  21. 		while (j >= 0 && arr[j] > key) {
  22. 			arr[j + 1] = arr[j];
  23. 			j--;
  24. 		}
  25. 		arr[j + 1] = key;
  26. 	}
  27. }
  28.  
  29. // 希尔排序
  30. /*
  31. 	思路：先进行分组，不断细分。每组进行分别插入排序，这个算法优点是可以不用一位一位的移动并且减少逆序对数量
  32. 		  越往后移动的次数越来越少，相较于一步一步移动，根据分组跳着移动，能够更快的移动到自己真正的位置
  33. 	第一步分组，从每组n/2个数开始，每次每组大小除以二，直到每个组一个数，即朴素插入排序
  34. 	第二步从第gap到n每个数往回跳gap步，落脚点j就是他所在的分组，进行插入排序
  35. 	第三步重复一二步，在分成每个组一个数进行最后一次排序，即得到有序数列
  36. */
  37. void shellSort(vector<int>& arr) {
  38. 	int n = arr.size();
  39. 	for (int gap = n / 2; gap > 0; gap >>= 1) {
  40. 		for (int i = gap; i < n; i++) {
  41. 			int temp = arr[i];
  42. 			int j;
  43. 			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
  44. 				arr[j + gap] = arr[j];
  45. 			}
  46. 			arr[j + gap] = temp;
  47. 		}
  48. 	}
  49. }
  50.  
  51. // 折半插入排序
  52. /*
  53. 	思路：插牌的时候一张牌一张牌看太慢了，所以用眼睛找一下该插入的位置（二分做眼睛找位置）
  54. */
  55. void binaryInsertionSort(vector<int>& arr) {
  56. 	for (int i = 1; i < arr.size(); i++) {
  57. 		int key = arr[i];
  58. 		int left = 0, right = i - 1;
  59. 		while (left <= right) {
  60. 			int mid = (left + right) / 2;
  61. 			if (arr[mid] > key) {
  62. 				right = mid - 1;
  63. 			}
  64. 			else {
  65. 				left = mid + 1;
  66. 			}
  67. 		}
  68. 		for (int j = i - 1; j >= left; j--) {		//将要找的位置的最右面数开始到找到的位置都往后挪，为插入的数腾位置
  69. 			arr[j + 1] = arr[j];
  70. 		}
  71. 		arr[left] = key;
  72. 	}
  73. }
  74.  
  75. // 冒泡排序
  76. /*
  77. 	思路：每次都是将数组中最大的泡泡挪到最后
  78. 	      若数组没发生挪动说明每个泡泡后面的泡泡都比他大
  79. */
  80. void bubbleSort(vector<int>& arr) {
  81. 	bool flag = true;
  82. 	for (int i = 0; i < arr.size() - 1 && flag; i++) {
  83. 		flag = false;
  84. 		for (int j = 0; j < arr.size() - i - 1; j++) {
  85. 			if (arr[j] > arr[j + 1]) {
  86. 				swap(arr[j], arr[j + 1]);
  87. 				flag = true;
  88. 			}
  89. 		}
  90. 	}
  91. }
  92.  
  93. // 归并排序
  94. /*
  95. 	思路：先将每个数分到一个文件夹中，而后合并每两个文件夹，使合并后的大文件夹是有序的，最终合并到一个文件里
  96. 	第一步将数列不断二分，分成小片段，对小片段进行操作
  97. 	第二步开出两个空间，分别存两个文件夹的数
  98. 	第三步为完成将两个空间（这两个空间数都是有序的）中最小的数提出了，放数组里。
  99. 		  所以用两个指针i，j 分别比较两个空间内第一个数（即该空间最小数）将较小的放入数组，被放入的空间指针++
  100. 	第四步当有一个空间的数全都放入了数组里，则直接将剩余空间的所有数放入数组里
  101. 	当从小文件合并到大文件之后，就得到有序数列
  102. */
  103. void merge(vector<int>& arr, int l, int m, int r) {
  104. 	int n1 = m - l + 1;
  105. 	int n2 = r - m;
  106. 	vector<int> L(n1), R(n2);
  107. 	for (int i = 0; i < n1; i++) {
  108. 		L[i] = arr[l + i];
  109. 	}
  110. 	for (int j = 0; j < n2; j++) {
  111. 		R[j] = arr[m + 1 + j];
  112. 	}
  113. 	int i = 0, j = 0, k = l;
  114. 	while (i < n1 && j < n2) {
  115. 		if (L[i] <= R[j]) {
  116. 			arr[k] = L[i];
  117. 			i++;
  118. 		}
  119. 		else {
  120. 			arr[k] = R[j];
  121. 			j++;
  122. 		}
  123. 		k++;
  124. 	}
  125. 	while (i < n1) {
  126. 		arr[k] = L[i];
  127. 		i++;
  128. 		k++;
  129. 	}
  130. 	while (j < n2) {
  131. 		arr[k] = R[j];
  132. 		j++;
  133. 		k++;
  134. 	}
  135. }
  136.  
  137. void mergeSort(vector<int>& arr, int l, int r) {
  138. 	if (l < r) {
  139. 		int m = l + (r - l) / 2;
  140. 		mergeSort(arr, l, m);
  141. 		mergeSort(arr, m + 1, r);
  142. 		merge(arr, l, m, r);
  143. 	}
  144. }
  145.  
  146. // 快速排序
  147. /*
  148. 	思路：分治思想 保证每个数左边的数都比他小，右边的数都比他大
  149. 	第一步让最后一个数成为基准privot
  150. 	第二步确认指针i，如果从开始到最后有数比基准小，交换指针指向的数和这个数，则i和i左边的数一定是小于基准的
  151. 	（刚开始arr[i]是最左边的数，将小于基准的数和arr[i]进行交换，即将小于基准的数放在左边）
  152. 	第三步将i+1位置与基准交换，则基准的左边一定是小于基准的，基准右边的一定是大于基准的
  153. 	第四步从调整整个数组的基准，到每个数都是基准（即确保每个数的左边小于基准，右边大于基准）得到有序数列
  154. */
  155. int partition(vector<int>& arr, int low, int high) {
  156. 	int pivot = arr[high];
  157. 	int i = low - 1;
  158. 	for (int j = low; j < high; j++) {
  159. 		if (arr[j] < pivot) {
  160. 			i++;
  161. 			swap(arr[i], arr[j]);
  162. 		}
  163. 	}
  164. 	swap(arr[i + 1], arr[high]);
  165. 	return i + 1;
  166. }
  167. void quickSort(vector<int>& arr, int low, int high) {
  168. 	if (low < high) {
  169. 		int pi = partition(arr, low, high);
  170. 		quickSort(arr, low, pi - 1);
  171. 		quickSort(arr, pi + 1, high);
  172. 	}
  173. }
  174.  
  175. // 基数排序
  176. /*
  177. 	思路：用空间换时间，比较两个数是高位大小比低位大小更重要，
  178. 	所以我们低位开始，相同位层进行排序，后面操作影响前面排序顺序即高位重要性高于低位，
  179. 	每个位层的排序为一个轮次，排序到最后就得到了有序
  180. 	第一步找到最高位，求出轮次的次数
  181. 	第二步开出一个备用空间用来存每个轮次的结果 
  182. 	第三步开出十个桶进行位层排序，将这些数进行重要性分级
  183. 	第四步求前缀和，画出分区，将不同重要级区分开来
  184. 	第五步将桶中的数存进备用空间
  185. 	第六步更新数组
  186. 	第七步重复三四五六步得到有序数列
  188. */
  189. void countSort(vector<int>& arr, int exp) {
  190. 	int n = arr.size();
  191. 	vector<int> output(n);
  192. 	vector<int> count(10, 0);
  193. 	for (int i = 0; i < n; i++) {
  194. 		count[(arr[i] / exp) % 10]++;
  195. 	}
  196. 	for (int i = 1; i < 10; i++) {
  197. 		count[i] += count[i - 1];
  198. 	}
  199. 	for (int i = n - 1; i >= 0; i--) {
  200. 		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
  201. 		count[(arr[i] / exp) % 10]--;
  202. 	}
  203. 	for (int i = 0; i < n; i++) {
  204. 		arr[i] = output[i];
  205. 	}
  206. }
  207.  
  208. void radixSort(vector<int>& arr) {
  209. 	int maxVal = *max_element(arr.begin(), arr.end());
  210. 	for (int exp = 1; maxVal / exp > 0; exp *= 10) {
  211. 		countSort(arr, exp);
  212. 	}
  213. }
  214.  
  215.  
  216. // 堆排序
  217. /*
  218. 	第一步先构建堆结构（根的值最大，每个节点一定是他那个子树的最大值，但不和同层的有什么关系）
  219. 	第二步将根（最大值）与最后一个元素交换，使得保证最后的节点是最大值
  220. 	第三步将被交换的元素放回堆里，使得剩余元素再次构成堆结构，保证根是最大值
  221. 	第四步 循环二三步，使得从最后到开始是从大到小，即得到开始到结束是从小到大
  222. */
  223. void heapify(vector<int>& arr, int n, int i) {
  224. 	int largest = i;
  225. 	int l = 2 * i + 1;
  226. 	int r = 2 * i + 2;
  227. 	if (l < n && arr[l] > arr[largest]) {
  228. 		largest = l;
  229. 	}
  230. 	if (r < n && arr[r] > arr[largest]) {
  231. 		largest = r;
  232. 	}
  233. 	if (largest != i) {
  234. 		swap(arr[i], arr[largest]);
  235. 		heapify(arr, n, largest);
  236. 	}
  237. }
  238.  
  239. void treeSelectionSort(vector<int>& arr) {
  240. 	int n = arr.size();
  241. 	for (int i = n / 2 - 1; i >= 0; i--) {
  242. 		heapify(arr, n, i);
  243. 	}
  244. 	for (int i = n - 1; i > 0; i--) {
  245. 		swap(arr[0], arr[i]);
  246. 		heapify(arr, i, 0);
  247. 	}
  248. }
  249.  
  250. // 选择排序
  251. /*
  252. 	思路：每次都是找到最小的数，放在最前面
  253. */
  254. void selectionSort(vector<int>& arr) {
  255. 	int n = arr.size();
  256. 	for (int i = 0; i < n - 1; i++) {
  257. 		int minIndex = i;
  258. 		for (int j = i + 1; j < n; j++) {
  259. 			if (arr[j] < arr[minIndex]) {
  260. 				minIndex = j;
  261. 			}
  262. 		}
  263. 		swap(arr[i], arr[minIndex]);
  264. 	}
  265. }
  266.  
  267. int main() {
  268. 	int n = 100000;
  269. 	vector<int> arr;
  270. 	// 以当前时间作为随机数种子
  271. 	unsigned seed = chrono::system_clock::now().time_since_epoch().count();
  272. 	mt19937 gen(seed);
  273. 	uniform_int_distribution<int> dis(1, 1000000); // 生成 1 到 1000 之间的随机数
  274. 	for (int i = 0; i < n; i++) {
  275. 		arr.push_back(dis(gen));
  276. 	}
  277.  
  278. 	// 插入排序
  279. 	vector<int> insertionArr = arr;
  280. 	auto start1 = chrono::high_resolution_clock::now();
  281. 	insertionSort(insertionArr);
  282. 	auto end1 = chrono::high_resolution_clock::now();
  283. 	auto duration1 = chrono::duration_cast<chrono::milliseconds>(end1 - start1);
  284. 	cout << "插入排序时间（毫秒）: " << duration1.count() << endl;
  285.  
  286. 	// 希尔排序
  287. 	vector<int> shellArr = arr;
  288. 	auto start2 = chrono::high_resolution_clock::now();
  289. 	shellSort(shellArr);
  290. 	auto end2 = chrono::high_resolution_clock::now();
  291. 	auto duration2 = chrono::duration_cast<chrono::milliseconds>(end2 - start2);
  292. 	cout << "希尔排序时间（毫秒）: " << duration2.count() << endl;
  293.  
  294. 	// 折半插入排序
  295. 	vector<int> binaryInsertionArr = arr;
  296. 	auto start3 = chrono::high_resolution_clock::now();
  297. 	binaryInsertionSort(binaryInsertionArr);
  298. 	auto end3 = chrono::high_resolution_clock::now();
  299. 	auto duration3 = chrono::duration_cast<chrono::milliseconds>(end3 - start3);
  300. 	cout << "折半插入排序时间（毫秒）: " << duration3.count() << endl;
  301.  
  302. 	// 冒泡排序
  303. 	vector<int> bubbleArr = arr;
  304. 	auto start4 = chrono::high_resolution_clock::now();
  305. 	bubbleSort(bubbleArr);
  306. 	auto end4 = chrono::high_resolution_clock::now();
  307. 	auto duration4 = chrono::duration_cast<chrono::milliseconds>(end4 - start4);
  308. 	cout << "冒泡排序时间（毫秒）: " << duration4.count() << endl;
  309.  
  310. 	// 归并排序
  311. 	vector<int> mergeArr = arr;
  312. 	auto start5 = chrono::high_resolution_clock::now();
  313. 	mergeSort(mergeArr, 0, n - 1);
  314. 	auto end5 = chrono::high_resolution_clock::now();
  315. 	auto duration5 = chrono::duration_cast<chrono::milliseconds>(end5 - start5);
  316. 	cout << "归并排序时间（毫秒）: " << duration5.count() << endl;
  317.  
  318. 	// 快速排序
  319. 	vector<int> quickArr = arr;
  320. 	auto start6 = chrono::high_resolution_clock::now();
  321. 	quickSort(quickArr, 0, n - 1);
  322. 	auto end6 = chrono::high_resolution_clock::now();
  323. 	auto duration6 = chrono::duration_cast<chrono::milliseconds>(end6 - start6);
  324. 	cout << "快速排序时间（毫秒）: " << duration6.count() << endl;
  325.  
  326. 	// 基数排序
  327. 	vector<int> radixArr = arr;
  328. 	auto start7 = chrono::high_resolution_clock::now();
  329. 	radixSort(radixArr);
  330. 	auto end7 = chrono::high_resolution_clock::now();
  331. 	auto duration7 = chrono::duration_cast<chrono::milliseconds>(end7 - start7);
  332. 	cout << "基数排序时间（毫秒）: " << duration7.count() << endl;
  333.  
  334. 	// 树形选择排序
  335. 	vector<int> treeSelectionArr = arr;
  336. 	auto start8 = chrono::high_resolution_clock::now();
  337. 	treeSelectionSort(treeSelectionArr);
  338. 	auto end8 = chrono::high_resolution_clock::now();
  339. 	auto duration8 = chrono::duration_cast<chrono::milliseconds>(end8 - start8);
  340. 	cout << "树形选择排序时间（毫秒）: " << duration8.count() << endl;
  341. 	
  342. 	// 选择排序
  343. 	vector<int> selectionArr = arr;
  344. 	auto start9 = chrono::high_resolution_clock::now();
  345. 	selectionSort(selectionArr);
  346. 	auto end9 = chrono::high_resolution_clock::now();
  347. 	auto duration9 = chrono::duration_cast<chrono::milliseconds>(end9 - start9);
  348. 	cout << "选择排序时间（毫秒）: " << duration9.count() << endl;
  349.  
  350. 	return 0;
  351. }
  352.

参考博客
链接：https://blog.csdn.net/weixin_52828997/article/details/128568924

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/824375
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号