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

9种排序算法对比_排序算法比较

作者：IT小白 | 2024-04-12 17:29:09

赞

踩

排序算法比较

目录

本文里所有代码均为本人原创，若有错误请指正！！！

目录

  • 前言
  • 一、插入排序
    • 1.直接插入
    • 2.折半插入
    • 3.希尔排序
  • 二、选择排序
    • 1.直接选择
    • 2.树形选择
  • 三、交换排序
    • 1.冒泡排序
    • 2.快速排序
  • 四、其他排序
    • 1.归并排序
    • 2.基数排序
  • 总结

前言

        本人目前为大二学生，算法基础相对薄弱，写此blog来加强自己的算法能力，为ACM等竞赛打好基础。此blog可能有许多错误，还望各位大佬指正！若有志同道合的朋友，可以一起学习算法，共同进步！

提示：以下代码仅供参考！！！

一、插入排序

        插入排序，顾名思义，就是在待排序的数组中间插入元素，最终实现排序数组的效果。

1.直接插入

        直接插入是最基础的排序方法，其原理为：我们认为前面k个数组是已经排序好的状态，数组中的第k+1个元素，和前面k个元素进行比较，找到他要插入的位置，将后面的元素依次往后移即可。时间复杂度为O(n^2)。（为了方便对比数组大小均为100000（10^5），并且于直接插入算法进行比较）。

具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <time.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. void Print(int* a, int n);
  10. void direct_sort(int* a, int n);
  11.  
  12. void direct_sort(int* a, int n)
  13. {
  14. 	if (n <= 1)
  15. 	{
  16. 		cout << "Array Error!" << endl;
  17. 	}
  18. 	for (int i = 1; i < n; i++)
  19. 	{
  20. 		int k = 0;
  21. 		while (a[i] > a[k])k++;
  22. 		int temp = a[i];
  23. 		for (int j = i; j > k; j--)
  24. 		{
  25. 			a[j] = a[j - 1];
  26. 		}
  27. 		a[k] = temp;
  28. 	}
  29. }
  30.  
  31. void Print(int* a, int n)
  32. {
  33. 	for (int i = 0; i < n; i++)
  34. 	{
  35. 		cout << a[i] << " ";
  36. 	}
  37. 	cout << endl;
  38. }
  39.  
  40. int main()
  41. {
  42. 	srand((unsigned)time(NULL));
  43. 	int n;
  44. 	cout << "请输入待排序的数组大小：";
  45. 	cin >> n;
  46. 	int* num = new int[n];
  47. 	int* num1 = new int[n];
  48. 	for (int i = 0; i < n; i++)
  49. 	{
  50. 		num[i] = rand();
  51. 		num1[i] = num[i];
  52. 	}
  53. 	clock_t start = clock();
  54. 	direct_sort(num, n);
  55. 	clock_t end = clock();
  56. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  57. 	sort(num1, num1 + n);
  58. 	bool equal = true;
  59. 	for (int i = 0; i < n; i++)
  60. 	{
  61. 		if (num[i] != num1[i])
  62. 		{
  63. 			equal = false;
  64. 			break;
  65. 		}
  66. 	}
  67. 	if (equal)cout << "Right!" << endl;
  68. 	else cout << "Error!" << endl;
  69. 	delete[]num;
  70. 	delete[]num1;
  71. 	return 0;
  72. }

        排序数组大小为100000是数组（10^5）共用时5727ms。经验证结果正确。

 2.折半插入

       折半插入就是在直接插入算法的基础上的一个升级，其实我们并不需要去遍历前面的k个元素进行比较，我们只需要和前面数组大小为k的数组的中间值进行比较即可。如果这个数比中间值大，那么就把区间放到都半部分去继续进行比较；否则就在半部分进行比较。最后一定会找到插入的位置，这个查找的时间复杂度就降低到了O(logn)。找到位置后，在继续插入即可。这样这个算法的时间复杂度就是O(nlogn)。

       具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <omp.h>
  4. #include <stdlib.h>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. void Binary_Sort(int* a, int n);
  10. void Print(int* a, int n);
  11. int find_insert_point(int* a, int n, int l, int r, int i);
  12. void direct_sort(int* a, int n);
  13.  
  14. void direct_sort(int* a, int n)
  15. {
  16. 	if (n <= 1)
  17. 	{
  18. 		cout << "Array Error!" << endl;
  19. 	}
  20. 	for (int i = 1; i < n; i++)
  21. 	{
  22. 		int k = 0;
  23. 		while (a[i] > a[k])k++;
  24. 		int temp = a[i];
  25. 		for (int j = i; j > k; j--)
  26. 		{
  27. 			a[j] = a[j - 1];
  28. 		}
  29. 		a[k] = temp;
  30. 	}
  31. }
  32.  
  33. int find_insert_point(int* a, int n, int l, int r, int i)
  34. {
  35. 	if (l > r)return l;
  36. 	int m = (l + r) / 2;
  37. 	if (a[i] < a[m])return find_insert_point(a, n, l, m - 1, i);
  38. 	else return find_insert_point(a, n, m + 1, r, i);
  39. }
  40.  
  41. void Binary_Sort(int* a, int n)
  42. {
  43. 	for (int i = 1; i < n; i++)
  44. 	{
  45. 		int p = find_insert_point(a, n, 0, i - 1, i);
  46. 		int temp = a[i];
  47. 		for (int j = i; j > p; j--)
  48. 		{
  49. 			a[j] = a[j - 1];
  50. 		}
  51. 		a[p] = temp;
  52. 	}
  53. }
  54.  
  55. void Print(int* a, int n)
  56. {
  57. 	for (int i = 0; i < n; i++)
  58. 	{
  59. 		cout << a[i] << " ";
  60. 	}
  61. 	cout << endl;
  62. }
  63.  
  64. int main()
  65. {
  66. 	srand((unsigned)time(NULL));
  67. 	cout << "请输入待排序的数组大小：";
  68. 	int n;
  69. 	cin >> n;
  70. 	int* num = new int[n];
  71. 	int* num1 = new int[n];
  72. 	for (int i = 0; i < n; i++)
  73. 	{
  74. 		num[i] = rand();
  75. 		num1[i] = num[i];
  76. 	}
  77. 	clock_t start = clock();
  78. 	Binary_Sort(num, n);
  79. 	clock_t end = clock();
  80. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  81. 	//Print(num, n);
  82. 	clock_t start1 = clock();
  83. 	direct_sort(num1, n);
  84. 	clock_t end1 = clock();
  85. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  86. 	bool equal = true;
  87. 	for (int i = 0; i < n; i++)
  88. 	{
  89. 		if (num[i] != num1[i])
  90. 		{
  91. 			equal = false;
  92. 			break;
  93. 		}
  94. 	}
  95. 	if (equal)cout << "Right!" << endl;
  96. 	else cout << "Error!" << endl;
  97. 	delete[]num;
  98. 	delete[]num1;
  99. 	return 0;
  100. }

        该算法排序数组大小为100000的数组需要2845ms。经验证结果正确。 

           时间上有问题，代码不知道哪里有问题，还望大佬指出！！！

3.希尔排序

        希尔排序的原理为：将数组中间隔gap的元素分为一组，并将组内进行排序，然后逐步减小gap，当gap为1时，数组就已经排序好了。这里我们选择的是让gap/=2，来逐步减小gap，这样这个算法的时间复杂度就是O(nlogn^2)或者是O(n^1.3)了。

具体代码：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. void Shell_Sort(int* a, int n);
  10. void Print(int* a, int n);
  11. void Swap(int& a, int& b);
  12. void direct_sort(int* a, int n);
  13.  
  14. void direct_sort(int* a, int n)
  15. {
  16. 	if (n <= 1)
  17. 	{
  18. 		cout << "Array Error!" << endl;
  19. 	}
  20. 	for (int i = 1; i < n; i++)
  21. 	{
  22. 		int k = 0;
  23. 		while (a[i] > a[k])k++;
  24. 		int temp = a[i];
  25. 		for (int j = i; j > k; j--)
  26. 		{
  27. 			a[j] = a[j - 1];
  28. 		}
  29. 		a[k] = temp;
  30. 	}
  31. }
  32.  
  33. void Swap(int& a, int& b)
  34. {
  35. 	int temp = a;
  36. 	a = b;
  37. 	b = temp;
  38. }
  39.  
  40. void Shell_Sort(int* a, int n)
  41. {
  42. 	//Print(a, n,n);
  43. 	for (int gap = n/2; gap >= 1; gap >>= 1)
  44. 	{
  45. 		for (int i = gap; i < n; i++)
  46. 		{
  47. 			int temp = a[i];
  48. 			for (int j = i - gap; j >= 0; j -= gap)
  49. 			{
  50. 				if (temp < a[j])Swap(a[j + gap], a[j]);
  51. 				else break;
  52. 			}
  53. 		}
  54. 	}
  55. }
  56.  
  57. void Print(int* a, int n)
  58. {
  59. 	for (int i = 0; i < n; i++)
  60. 	{
  61. 		printf("%d ",a[i]);
  62. 		//if ((i+1) % gap == 0)cout << endl;
  63. 	}
  64. 	cout << endl;
  65. }
  66.  
  67. int main()
  68. {
  69. 	srand((unsigned)time(NULL));
  70. 	int n;
  71. 	cout << "请输入待排序的数组的大小：";
  72. 	cin >> n;
  73. 	int* num = new int[n];
  74. 	int* num1 = new int[n];
  75. 	for (int i = 0; i < n; i++)
  76. 	{
  77. 		num[i] = rand();
  78. 		num1[i] = num[i];
  79. 	}
  80. 	clock_t start = clock();
  81. 	Shell_Sort(num, n);
  82. 	clock_t end = clock();
  83. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  84. 	//Print(num, n);
  85. 	clock_t start1 = clock();
  86. 	direct_sort(num1, n);
  87. 	clock_t end1 = clock();
  88. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  89. 	bool equal = true;
  90. 	for (int i = 0; i < n; i++)
  91. 	{
  92. 		if (num[i] != num1[i])
  93. 		{
  94. 			equal = false;
  95. 			break;
  96. 		}
  97. 	}
  98. 	if (equal)cout << "Right!" << endl;
  99. 	else cout << "Error!" << endl;
  100. 	delete[]num;
  101. 	delete[]num1;
  102. 	return 0;
  103. }

         该算法排序数组大小为100000的数组仅需要28ms。经验证结果正确。 

 

二、选择排序

        选择排序，就是每次都选出这个数组中最大或者最小的元素，这样就可以将数组排序好了。

1.直接选择

        直接排序是最直接的排序方式，循环n次，每次都选出数组中第k小的数据，并把它放在数组的第k个位置。时间复杂度为O(n^2)。

具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. void Choose_Sort(int* a, int n);
  10. void Print(int* a, int n);
  11. void Swap(int& a, int& b);
  12. void direct_sort(int* a, int n);
  13.  
  14. void direct_sort(int* a, int n)
  15. {
  16. 	if (n <= 1)
  17. 	{
  18. 		cout << "Array Error!" << endl;
  19. 	}
  20. 	for (int i = 1; i < n; i++)
  21. 	{
  22. 		int k = 0;
  23. 		while (a[i] > a[k])k++;
  24. 		int temp = a[i];
  25. 		for (int j = i; j > k; j--)
  26. 		{
  27. 			a[j] = a[j - 1];
  28. 		}
  29. 		a[k] = temp;
  30. 	}
  31. }
  32.  
  33. void Swap(int& a, int& b)
  34. {
  35. 	int temp = a;
  36. 	a = b;
  37. 	b = temp;
  38. }
  39.  
  40. void Print(int* a, int n)
  41. {
  42. 	for (int i = 0; i < n; i++)
  43. 	{
  44. 		printf("%d ", a[i]);
  45. 		//if ((i+1) % gap == 0)cout << endl;
  46. 	}
  47. 	cout << endl;
  48. }
  49.  
  50. void Choose_Sort(int* a, int n)
  51. {
  52. 	for (int i = 0; i < n; i++)
  53. 	{
  54. 		int m = a[i];
  55. 		int dex = i;
  56. 		for (int j = i + 1; j < n; j++)
  57. 		{
  58. 			if (a[j] < m)
  59. 			{
  60. 				m = a[j];
  61. 				dex = j;
  62. 			}
  63. 		}
  64. 		Swap(a[i], a[dex]);
  65. 	}
  66. }
  67.  
  68. int main()
  69. {
  70. 	srand((unsigned)time(NULL));
  71. 	cout << "请输入待排序的数组的大小：";
  72. 	int n;
  73. 	cin >> n;
  74. 	int* num = new int[n];
  75. 	int* num1 = new int[n];
  76. 	for (int i = 0; i < n; i++)
  77. 	{
  78. 		num[i] = rand();
  79. 		num1[i] = num[i];
  80. 	}
  81. 	clock_t start = clock();
  82. 	Choose_Sort(num, n);
  83. 	clock_t end = clock();
  84. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  85. 	//Print(num, n);
  86. 	clock_t start1 = clock();
  87. 	direct_sort(num1, n);
  88. 	clock_t end1 = clock();
  89. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  90. 	bool equal = true;
  91. 	for (int i = 0; i < n; i++)
  92. 	{
  93. 		if (num[i] != num1[i])
  94. 		{
  95. 			equal = false;
  96. 			break;
  97. 		}
  98. 	}
  99. 	if (equal)cout << "Right!" << endl;
  100. 	else cout << "Error!" << endl;
  101. 	delete[]num;
  102. 	delete[]num1;
  103. 	return 0;
  104. }

        该算法排序数组大小为100000的数组需要4945ms。经验证结果正确。

2.树形选择

        树形选择排序就是利用空间换取时间的思想。将一个数组弄成补成一个2的k次方的数组，多出来的部分用无穷大进行表示。这样我们就可以形成一个完全二叉树，并且每次对比都把2个中最小的一个数，赋值给该节点，这样头节点的数据就是这个数组中最小的数据。然后将这个数据赋值给原数组，并将该数设置为无穷大，进行下一轮迭代。这个算法的时间复杂度为O(nlogn)。

具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6. #define M 0x7fffffff
  7.  
  8. using namespace std;
  9.  
  10. void Tree_Sort(int* a, int n);
  11. void Print(int* a, int n);
  12. void Swap(int& a, int& b);
  13. void direct_sort(int* a, int n);
  14.  
  15.  
  16. void Swap(int& a, int& b)
  17. {
  18. 	int temp = a;
  19. 	a = b;
  20. 	b = temp;
  21. }
  22.  
  23. void Print(int* a, int n)
  24. {
  25. 	for (int i = 0; i < n; i++)
  26. 	{
  27. 		printf("%d ", a[i]);
  28. 	}
  29. 	cout << endl;
  30. }
  31.  
  32. void direct_sort(int* a, int n)
  33. {
  34. 	if (n <= 1)
  35. 	{
  36. 		cout << "Array Error!" << endl;
  37. 	}
  38. 	for (int i = 1; i < n; i++)
  39. 	{
  40. 		int k = 0;
  41. 		while (a[i] > a[k])k++;
  42. 		int temp = a[i];
  43. 		for (int j = i; j > k; j--)
  44. 		{
  45. 			a[j] = a[j - 1];
  46. 		}
  47. 		a[k] = temp;
  48. 	}
  49. }
  50.  
  51. void Tree_Sort(int* a, int n)
  52. {
  53. 	int n1 = n,t = 0;
  54. 	while (n1)
  55. 	{
  56. 		n1 >>= 1;
  57. 		t++;
  58. 	}
  59. 	int n2 = 1;
  60. 	n2 <<= t;
  61. 	int n_max = 2 * n2 - 1;
  62. 	int* num = new int[n_max];
  63. 	for (int i = 0; i < n2; i++)
  64. 	{
  65. 		if (i < n)num[i] = a[i];
  66. 		else num[i] = M;
  67. 	}
  68. 	for (int i = n2; i < n_max; i++)
  69. 	{
  70. 		num[i] = min(num[(i - n2) * 2], num[(i - n2) * 2 + 1]);
  71. 	}
  72. 	int h = n2;
  73. 	int pre1 = 0;
  74. 	for (int i = 0; i < 2 * n2 - 1; i++)
  75. 	{
  76. 		cout << num[i] << " ";
  77. 		if (i+1 == pre1 + h)
  78. 		{
  79. 			pre1 += h;
  80. 			cout << endl;
  81. 			h >>= 1;		
  82. 		}
  83. 	}
  84. 	cout << endl;
  85. 	a[0] = num[n_max-1];
  86. 	for (int i = 0; i < n - 1; i++)
  87. 	{
  88. 		int temp = num[n_max - 1];
  89. 		int t = n_max - 1;
  90. 		while (t >= n2)
  91. 		{
  92. 			if (num[(t - n2) * 2] == temp)t = (t - n2) * 2;
  93. 			else t = (t - n2) * 2 + 1;
  94. 		}
  95. 		num[t] = M;
  96. 		while (t < n_max - 1)
  97. 		{
  98. 			num[n2 + t / 2] = min(num[t], num[t ^ 1]);
  99. 			t = n2 + t / 2;
  100. 		}
  101. 		a[i + 1] = num[n_max - 1];
  102. 	}
  103. 	delete[]num;
  104. }
  105.  
  106. int main()
  107. {
  108. 	srand((unsigned)time(NULL));
  109. 	cout << "请输入待排序的数组大小：";
  110. 	int n;
  111. 	cin >> n;
  112. 	int* num = new int[n];
  113. 	int* num1 = new int[n];
  114. 	for (int i = 0; i < n; i++)
  115. 	{
  116. 		num[i] = rand();
  117. 		num1[i] = num[i];
  118. 	}
  119. 	clock_t start = clock();
  120. 	Tree_Sort(num, n);
  121. 	clock_t end = clock();
  122. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  123. 	//Print(num, n);
  124. 	clock_t start1 = clock();
  125. 	direct_sort(num1, n);
  126. 	clock_t end1 = clock();
  127. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  128. 	bool equal = true;
  129. 	for (int i = 0; i < n; i++)
  130. 	{
  131. 		if (num[i] != num1[i])
  132. 		{
  133. 			equal = false;
  134. 			break;
  135. 		}
  136. 	}
  137. 	if (equal)cout << "Right!" << endl;
  138. 	else cout << "Error!" << endl;
  139. 	delete[]num;
  140. 	delete[]num1;
  141. 	return 0;
  142. }

 

        该算法排序数组大小为100000的数组仅需要29ms，不过需要大量的空间来实现。经验证后结果正确。

三、交换排序

        交换排序就是不断的将大的数与小的数交换，将数组进行排序的算法。

1.冒泡排序

        冒泡排序就是不断地将大的数和小的数进行交换，大的数放在后面，把最大的数放在数组的末尾。当某一次遍历时若没有发生交换，说明该数组已经排序好了，这时候我们就可以break，跳出循环了。该算法的时间复杂度为O(n^2)。

具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. void Bubble_Sort(int* a, int n);
  10. void Print(int* a, int n);
  11. void Swap(int& a, int& b);
  12. void direct_sort(int* a, int n);
  13.  
  14. void Swap(int& a, int& b)
  15. {
  16. 	int temp = a;
  17. 	a = b;
  18. 	b = temp;
  19. }
  20.  
  21. void Print(int* a, int n)
  22. {
  23. 	for (int i = 0; i < n; i++)
  24. 	{
  25. 		printf("%d ", a[i]);
  26. 	}
  27. 	cout << endl;
  28. }
  29.  
  30. void direct_sort(int* a, int n)
  31. {
  32. 	if (n <= 1)
  33. 	{
  34. 		cout << "Array Error!" << endl;
  35. 	}
  36. 	for (int i = 1; i < n; i++)
  37. 	{
  38. 		int k = 0;
  39. 		while (a[i] > a[k])k++;
  40. 		int temp = a[i];
  41. 		for (int j = i; j > k; j--)
  42. 		{
  43. 			a[j] = a[j - 1];
  44. 		}
  45. 		a[k] = temp;
  46. 	}
  47. }
  48.  
  49. void Bubble_Sort(int* a, int n)
  50. {
  51. 	for (int i = 0; i < n; i++)
  52. 	{
  53. 		bool over = true;
  54. 		for (int j = 0; j < n - i - 1; j++)
  55. 		{
  56. 			if (a[j] > a[j + 1])
  57. 			{
  58. 				Swap(a[j], a[j + 1]);
  59. 				over = false;
  60. 			}
  61. 		}
  62. 		if (over)break;
  63. 	}
  64. }
  65.  
  66. int main()
  67. {
  68. 	srand((unsigned)time(NULL));
  69. 	int n;
  70. 	cout << "请输入待排序的数组的大小：";
  71. 	cin >> n;
  72. 	int* num = new int[n];
  73. 	int* num1 = new int[n];
  74. 	for (int i = 0; i < n; i++)
  75. 	{
  76. 		num[i] = rand();
  77. 		num1[i] = num[i];
  78. 	}
  79. 	clock_t start = clock();
  80. 	Bubble_Sort(num, n);
  81. 	clock_t end = clock();
  82. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  83. 	//Print(num, n);
  84. 	clock_t start1 = clock();
  85. 	direct_sort(num1, n);
  86. 	clock_t end1 = clock();
  87. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  88. 	bool equal = true;
  89. 	for (int i = 0; i < n; i++)
  90. 	{
  91. 		if (num[i] != num1[i])
  92. 		{
  93. 			equal = false;
  94. 			break;
  95. 		}
  96. 	}
  97. 	if (equal)cout << "Right!" << endl;
  98. 	else cout << "Error!" << endl;
  99. 	delete[]num;
  100. 	delete[]num1;
  101. 	return 0;
  102. }

         该算法排序数组大小为100000的数组需要25806ms，时间开销较大。经验证后结果正确。

2.快速排序

         快速排序是在数组里面选取一个中间的数作为比较值，将比该值大的元素放在右边，比该元素小的元素放在左边。这样再对这个左右2个数组进行相同的操作，当两个边的边界值相差1时数组就已经排序好了。

        这里我们选取3个数进行比较选其中中间值，让中间值尽可能地接近该数组的中位数，来减少递归后的数组的时间复杂度，并且当数组足够小时，可以不需要递归调用，可以选择直接插入的算法进行排序，这样也可以减少时间复杂度。最终时间复杂度为O(nlogn)。

具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. void Quick_Sort(int* a, int n);
  10. void Quick_Divide(int* a, int left, int right);
  11. void Print(int* a, int n);
  12. void Swap(int& a, int& b);
  13. void direct_sort(int* a, int left,int right);
  14.  
  15. void Swap(int& a, int& b)
  16. {
  17. 	int temp = a;
  18. 	a = b;
  19. 	b = temp;
  20. }
  21.  
  22. void Print(int* a, int n)
  23. {
  24. 	for (int i = 0; i < n; i++)
  25. 	{
  26. 		printf("%d ", a[i]);
  27. 	}
  28. 	cout << endl;
  29. }
  30.  
  31. void direct_sort(int* a, int left,int right)
  32. {
  33. 	if (left > right)
  34. 	{
  35. 		cout << "Array Error!" << endl;
  36. 	}
  37. 	for (int i = left + 1; i <= right; i++)
  38. 	{
  39. 		int k = left;
  40. 		while (a[i] > a[k])k++;
  41. 		int temp = a[i];
  42. 		for (int j = i; j > k; j--)
  43. 		{
  44. 			a[j] = a[j - 1];
  45. 		}
  46. 		a[k] = temp;
  47. 	}
  48. }
  49.  
  50. void Quick_Divide(int* a, int left, int right)
  51. {
  52. 	if (right <= left)return;
  53. 	if (right - left < 10)
  54. 	{
  55. 		direct_sort(a, left, right);
  56. 		return;
  57. 	}
  58. 	int num[3] = { a[left],a[right],a[(left + right) / 2] };
  59. 	sort(num, num+3);
  60. 	int dex;
  61. 	if (num[1] == a[left])dex = left;
  62. 	else if (num[1] == a[right])dex = right;
  63. 	else dex = (left + right) / 2;
  64. 	Swap(a[dex], a[left]);
  65. 	int i = left, j = right;
  66. 	int temp = a[left];
  67. 	while (i < j)
  68. 	{
  69. 		while (i < j && a[i] < temp)i++;
  70. 		while (i < j && a[j] >= temp)j--;
  71. 		Swap(a[i], a[j]);
  72. 	}
  73. 	if (a[i] > temp)
  74. 	{
  75. 		Quick_Divide(a, left, i - 1);
  76. 		Quick_Divide(a, i, right);
  77. 	}
  78. 	else
  79. 	{
  80. 		Quick_Divide(a, left, i);
  81. 		Quick_Divide(a, i + 1, right);
  82. 	}
  83. }
  84.  
  85. void Quick_Sort(int* a, int n)
  86. {
  87. 	Quick_Divide(a, 0, n - 1);
  88. }
  89.  
  90. int main()
  91. {
  92. 	srand((unsigned)time(NULL));
  93. 	int n;
  94. 	cout << "请输入待排序的数组的大小：";
  95. 	cin >> n;
  96. 	int* num = new int[n];
  97. 	int* num1 = new int[n];
  98. 	for (int i = 0; i < n; i++)
  99. 	{
  100. 		num[i] = rand();
  101. 		num1[i] = num[i];
  102. 	}
  103. 	clock_t start = clock();
  104. 	Quick_Sort(num, n);
  105. 	clock_t end = clock();
  106. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  107. 	//Print(num, n);
  108. 	clock_t start1 = clock();
  109. 	direct_sort(num1, 0, n - 1);
  110. 	clock_t end1 = clock();
  111. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  112. 	bool equal = true;
  113. 	for (int i = 0; i < n; i++)
  114. 	{
  115. 		if (num[i] != num1[i])
  116. 		{
  117. 			equal = false;
  118. 			break;
  119. 		}
  120. 	}
  121. 	if (equal)cout << "Right!" << endl;
  122. 	else cout << "Error!" << endl;
  123. 	delete[]num;
  124. 	delete[]num1;
  125. 	return 0;
  126. }

         该算法排序数组大小为100000的数组仅需要14ms。经验证后结果正确。

 

四、其他排序

1.归并排序

        归并排序就是将数组逐步拆分为大小较小的数组，然后逐渐把数组进行合并这样就可以将时间复杂度降低到O(nlogn)了。

        注意：这里我们需要把原数组的大小拓展为2的k次方。

        具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. #define M 0x7fffffff
  10.  
  11. void Merge_Sort(int* a, int n);
  12. void Print(int* a, int n);
  13. void Swap(int& a, int& b);
  14. void direct_sort(int* a, int n);
  15. void Merge(int* a, int n, int hn);
  16.  
  17. void direct_sort(int* a, int n)
  18. {
  19. 	if (n <= 1)
  20. 	{
  21. 		cout << "Array Error!" << endl;
  22. 	}
  23. 	for (int i = 1; i < n; i++)
  24. 	{
  25. 		int k = 0;
  26. 		while (a[i] > a[k])k++;
  27. 		int temp = a[i];
  28. 		for (int j = i; j > k; j--)
  29. 		{
  30. 			a[j] = a[j - 1];
  31. 		}
  32. 		a[k] = temp;
  33. 	}
  34. }
  35.  
  36. void Swap(int& a, int& b)
  37. {
  38. 	int temp = a;
  39. 	a = b;
  40. 	b = temp;
  41. }
  42.  
  43. void Merge_Sort(int* a, int n)
  44. {
  45. 	//Print(a, n);
  46. 	int t = 0;
  47. 	int n1 = n;
  48. 	while (n1)
  49. 	{
  50. 		n1 >>= 1;
  51. 		t++;
  52. 	}
  53. 	int n2 = 1;
  54. 	for (int i = 0; i < t; i++)
  55. 	{
  56. 		n2 <<= 1;
  57. 	}
  58. 	int* num = new int[n2];
  59. 	for (int i = 0; i < n; i++)
  60. 	{
  61. 		num[i] = a[i];
  62. 	}
  63. 	for (int i = n; i < n2; i++)
  64. 	{
  65. 		num[i] = M;
  66. 	}
  67. 	for (int i = 0; i < n2 / 2; i++)
  68. 	{
  69. 		if (num[2 * i] > num[2 * i + 1])Swap(num[2 * i], num[2 * i + 1]);
  70. 	}
  71. 	int hn = 2;
  72. 	while (hn <= n2 / 2)
  73. 	{
  74. 		Merge(num, n2, hn);
  75. 		hn <<= 1;
  76. 		//Print(num, n);
  77. 	}
  78. 	//Print(num, n2);
  79. 	for (int i = 0; i < n; i++)
  80. 	{
  81. 		a[i] = num[i];
  82. 		
  83. 	}
  84. 	//Print(a, n);
  85. }
  86. void Merge(int* num, int n, int hn)
  87. {
  88. 	int* num1 = new int[n];
  89. 	for (int i = 0; i < n; i++)
  90. 	{
  91. 		num1[i] = num[i];
  92. 	}
  93. 	int t = 2 * hn;
  94. 	for (int i = 0; i < n / t; i++)
  95. 	{
  96. 		int start = i * t, end = start + t - 1, k = start, p1 = start, p2 = start + hn;
  97. 		while (p1 < start + hn && p2<=end)
  98. 		{
  99. 			if (num1[p1] <= num[p2])
  100. 			{				
  101. 				num[k++] = num1[p1++];
  102. 				//if (k == 1)cout << num[0] << endl;
  103. 			}
  104. 			else
  105. 			{
  106. 				num[k++] = num1[p2++];
  107. 				//if (k == 1)cout << num[0] << endl;
  108. 			}
  109. 		}
  110. 		while (p1 < start + hn)num[k++] = num1[p1++];
  111. 		while (p2 <= end)num[k++] = num1[p2++];
  112. 	}
  113. 	delete[]num1;
  114. }
  115. void Print(int* a, int n)
  116. {
  117. 	for (int i = 0; i < n; i++)
  118. 	{
  119. 		printf("%d ",a[i]);
  120. 		//if ((i+1) % gap == 0)cout << endl;
  121. 	}
  122. 	cout << endl;
  123. }
  124.  
  125. int main()
  126. {
  127. 	srand((unsigned)time(NULL));
  128. 	cout << "请输入待排序的数组的大小：";
  129. 	int n;
  130. 	cin >> n;
  131. 	int* num = new int[n];
  132. 	int* num1 = new int[n];
  133. 	for (int i = 0; i < n; i++)
  134. 	{
  135. 		num[i] = rand();
  136. 		num1[i] = num[i];
  137. 	}
  138. 	clock_t start = clock();
  139. 	Merge_Sort(num, n);
  140. 	clock_t end = clock();
  141. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  142. 	//Print(num, n);
  143. 	clock_t start1 = clock();
  144. 	direct_sort(num1, n);
  145. 	clock_t end1 = clock();
  146. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  147. 	bool equal = true;
  148. 	for (int i = 0; i < n; i++)
  149. 	{
  150. 		if (num[i] != num1[i])
  151. 		{
  152. 			equal = false;
  153. 			break;
  154. 		}
  155. 	}
  156. 	if (equal)cout << "Right!" << endl;
  157. 	else cout << "Error!" << endl;
  158. 	delete[]num;
  159. 	delete[]num1;
  160. 	return 0;
  161. }

        该算法排序数组大小为100000的数组仅需要15ms。经验证后结果正确。

2.基数排序

        基数排序，就是以某一个进制为基础，将该数组分为若干个数组（几进制就用几个数组），将余数相同的数放在一个数组里，然后将这个数右移一位。这里需要找到，最大的一个数的最高位次，就可以知道需要迭代多少轮了。这样排序后都是按照位次一步一步排序好的，所以最后结果也是对的，不过这个需要大量的空间去存放数据。时间复杂度为O(nlogn)。

具体代码为：

  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. void Base_Sort(int* a, int n);
  10. void Print(int* a, int n);
  11. void Swap(int& a, int& b);
  12. void direct_sort(int* a, int n);
  13. void Base_Sort_pre(int* a, int n, int loop);
  14.  
  15. void direct_sort(int* a, int n)
  16. {
  17. 	if (n <= 1)
  18. 	{
  19. 		cout << "Array Error!" << endl;
  20. 	}
  21. 	for (int i = 1; i < n; i++)
  22. 	{
  23. 		int k = 0;
  24. 		while (a[i] > a[k])k++;
  25. 		int temp = a[i];
  26. 		for (int j = i; j > k; j--)
  27. 		{
  28. 			a[j] = a[j - 1];
  29. 		}
  30. 		a[k] = temp;
  31. 	}
  32. }
  33.  
  34. void Swap(int& a, int& b)
  35. {
  36. 	int temp = a;
  37. 	a = b;
  38. 	b = temp;
  39. }
  40.  
  41. void Print(int* a, int n)
  42. {
  43. 	for (int i = 0; i < n; i++)
  44. 	{
  45. 		printf("%d ", a[i]);
  46. 		//if ((i+1) % gap == 0)cout << endl;
  47. 	}
  48. 	cout << endl;
  49. }
  50.  
  51.  
  52. void Base_Sort_pre(int* a, int n,int loop)
  53. {
  54. 	//cout << t << endl;	
  55. 	int d[10] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };
  56. 	int* bucket[10] = {  };
  57. 	int c[10] = { 0 };
  58. 	for (int j = 0; j < n; j++)
  59. 	{
  60. 		c[(a[j] / d[loop]) % 10]++;
  61. 	}
  62. 	for (int k = 0; k < 10; k++)
  63. 	{
  64. 		bucket[k] = (int*)malloc(c[k] * sizeof(int));
  65. 	}
  66. 	for (int m = 0; m < 10; m++)c[m] = 0;
  67. 	for (int l = 0; l < n; l++)
  68. 	{
  69. 		int row = (a[l] / d[loop]) % 10;
  70. 		bucket[row][c[row]] = a[l];
  71. 		c[row]++;
  72. 	}
  73. 	int s = 0;
  74. 	for (int x = 0; x < 10; x++)
  75. 	{
  76. 		for (int y = 0; y < c[x]; y++)
  77. 		{
  78. 			a[s] = bucket[x][y];
  79. 			s++;
  80. 		}
  81. 	}
  82. 	for (int p = 0; p < 10; p++)
  83. 	{
  84. 		free(bucket[p]);
  85. 	}
  86. }
  87.  
  88. void Base_Sort(int* a, int n)
  89. {
  90. 	int ma = 0;
  91. 	for (int i = 0; i < n; i++)
  92. 	{
  93. 		if (a[i] > ma)ma = a[i];
  94. 	}
  95. 	int t = 0;
  96. 	int ai = ma;
  97. 	//cout << ai << endl;
  98. 	while (ai)
  99. 	{
  100. 		ai /= 10;
  101. 		t++;
  102. 	}
  103. 	for (int i = 0; i < t; i++)
  104. 	{
  105. 		Base_Sort_pre(a, n, i);
  106. 	}
  107. }
  108. int main()
  109. {
  110. 	srand((unsigned)time(NULL));
  111. 	cout << "请输入待排序的数组的大小：";
  112. 	int n;
  113. 	cin >> n;
  114. 	int* num = new int[n];
  115. 	int* num1 = new int[n];
  116. 	for (int i = 0; i < n; i++)
  117. 	{
  118. 		num[i] = rand();
  119. 		num1[i] = num[i];
  120. 	}
  121. 	clock_t start = clock();
  122. 	Base_Sort(num, n);
  123. 	clock_t end = clock();
  124. 	cout << "Sort " << n << " datas use " << (double)(end - start) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  125. 	//Print(num, n);
  126. 	clock_t start1 = clock();
  127. 	direct_sort(num1,n);
  128. 	clock_t end1 = clock();
  129. 	cout << "Sort " << n << " datas use " << (double)(end1 - start1) / CLOCKS_PER_SEC * 1000 << " ms." << endl;
  130. 	bool equal = true;
  131. 	for (int i = 0; i < n; i++)
  132. 	{
  133. 		if (num[i] != num1[i])
  134. 		{
  135. 			equal = false;
  136. 			break;
  137. 		}
  138. 	}
  139. 	//printf("%d\n", equal);
  140. 	if (equal)cout << "Right!" << endl;
  141. 	else cout << "Error!" << endl;
  142. 	delete[]num;
  143. 	delete[]num1;
  144. 	return 0;
  145. }

        该算法排序数组大小为100000的数组仅需要13ms。经验证结果正确。

 

总结

        这个9种排序算法的时间快慢为：基数排序>快速排序>归并排序>希尔排序>树形排序>折半插入>直接选择>直接插入>冒泡排序。

         其中，空间开销较大的有：基数排序和树形排序。

        每个排序算法都有自己的用途，不能单独从时间快慢上判断这个排序算法的好坏！

        以上代码为本人自己原创，可能有许多错误和理解不到位的地方，还望各位大佬指正！！！

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号