`
lovnet
  • 浏览: 6710585 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

C++排序算法总结

 
阅读更多

【1】插入排序：

是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度：O(n^2)，空间复杂度：O(1)。是稳定的排序方法。

代码：

[cpp] view plaincopyprint?
  1. //insertion sort
  2. #include <iostream>
  3. using namespace std;
  5. //insertion sort
  6. void InsertionSort(int *a,int n)
  7. {
  8. int temp;
  9. for(int i = 1;i < n;++i)
  10. {
  11. temp = *(a + i);
  12. int j = i - 1;
  13. while(j >= 0 && *(a + j) > temp)
  14. {
  15. *(a + j + 1) = *(a + j);
  16. --j;
  17. }
  18. *(a + j + 1) = temp;
  19. }
  20. }
  22. int main()
  23. {
  24. int n,temp;
  25. cout<<"please input the number of the values that need to sort:"<<endl;
  26. cin>>n;
  27. int *a = (int*)malloc(n *sizeof(int));
  28. cout<<"please input each value:"<<endl;
  29. for(int i = 0;i < n;++i)
  30. {
  31. cin>>temp;
  32. *(a + i) = temp;
  33. }
  34. /*
  35. //insertion sort
  36. for(int i = 1;i < n;++i)
  37. {
  38. temp = *(a + i);
  39. int j = i - 1;
  40. while(j >= 0 && *(a + j) > temp)
  41. {
  42. *(a + j + 1) = *(a + j);
  43. --j;
  44. }
  45. *(a + j + 1) = temp;
  46. }*/
  47. InsertionSort(a,n);
  49. cout<<"the values after sort:"<<endl;
  50. for(int i = 0;i < n;++i)
  51. cout<<*(a + i)<<" ";
  1. free(a);
  1. }

数据测试：


上述代码可以改进的一个地方是：在查找插入位置的时候可以采用二分查找，但是这样依然不可以把时间复杂度降低为O(nlogn)，因为移动元素的复杂度没有降低。所以时间复杂度仍然是O(n^2)。

做此改进需要添加函数InsertLoc用于二分查找需要插入的位置，以及修改函数InsertionSort的实现。具体如下：

[cpp] view plaincopyprint?
  1. //改进：用二分查找来找到插入的位置
  2. //在数组a[low]---a[high]查找val插入的位置
  3. int InsertLoc(int *a,int low,int high,int val)
  4. {
  5. if(low == high)
  6. {
  7. if(val > *(a + low))return (low + 1);
  8. else
  9. return low;
  10. }
  11. int mid = (low + high) / 2;
  12. if(val > *(a + mid) && val > *(a + mid + 1))
  13. return InsertLoc(a,mid + 1,high,val);
  14. else if(val < *(a + mid) && val < *(a + mid + 1))
  15. return InsertLoc(a,low,mid,val);
  16. else
  17. return mid;
  18. }
  20. void InsertionSort(int *a,int n)
  21. {
  22. int temp,insert_location;
  23. for(int i = 1;i < n;++i)
  24. {
  25. temp = *(a + i);
  26. int j = i - 1;
  27. insert_location = InsertLoc(a,0,j,temp);
  28. cout<<"insert_location:"<<insert_location<<endl;
  29. while(j >= insert_location)
  30. {
  31. *(a + j + 1) = *(a + j);
  32. --j;
  33. }
  34. *(a + insert_location) = temp;
  35. for(int m = 0;m <= i;++m)
  36. cout<<*(a + m)<<" ";
  37. cout<<endl;
  38. }
  39. }

【2】选择排序

第一次找出A[0,...,n-1]的最小的元素，与A[0]交换，接着，找出A[1,...,n-1]的次小得元素，与A[1]互换。对A中头n-1个元素执行这一过程。时间复杂度：O(n^2)，空间复杂度O(1)。是不稳定的排序方法。比如序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序是不稳定的排序算法。

但是严蔚敏的《数据结构》书上面Page289页说，所有时间复杂度为O(n^2)的简单排序都是稳定的。不知道为什么？求指导~~

其给出的简单排序的伪代码：

[cpp] view plaincopyprint?
  1. void SelectSort(SqList &L)
  2. {
  3. //对顺序表L做简单排序
  4. for(i = 1;i < L.length;++i)//选择第i小得记录，并交换到位
  5. {
  6. j = SelectMinKey(L,i);//在L.r[i..L.length]中选择key最小的记录
  7. if(i != j)//与第i个记录交换
  8. {
  9. temp = L.r[i];
  10. L.r[i] = L.r[j];
  11. L.r[j] = temp;
  12. }
  13. }
  14. }

代码：

[cpp] view plaincopyprint?
  1. //选择排序
  2. #include <iostream>
  3. using namespace std;
  5. void ChoseSort(int* a,int n)
  6. {
  7. int temp,minVal,minIndex;
  8. for(int i = 0;i < n - 1;++i)
  9. {
  10. minVal = *(a + i);//记录a[i,...,n-1]之间的最小值
  11. minIndex = i;//记录a[i,...,n-1]之间的最小值的下标
  12. for(int j = i + 1;j < n;++j)
  13. {
  14. if(minVal > *(a + j))
  15. {
  16. minVal = *(a + j);
  17. minIndex = j;
  18. }
  19. }
  20. //交换a[i]和a[i,...,n-1]之间的最小值最小值
  21. if(minIndex != i)
  22. {
  23. temp = *(a + i);
  24. *(a + i) = *(a + minIndex);
  25. *(a + minIndex) = temp;
  26. }
  27. }
  28. }
  30. int main()
  31. {
  32. int n,temp;
  33. cout<<"please input the number of the values that need to sort:"<<endl;
  34. cin>>n;
  35. int *a = (int*)malloc(n *sizeof(int));
  36. cout<<"please input each value:"<<endl;
  37. for(int i = 0;i < n;++i)
  38. {
  39. cin>>temp;
  40. *(a + i) = temp;
  41. }
  42. ChoseSort(a,n);
  43. cout<<"the values after sort:"<<endl;
  44. for(int i = 0;i < n;++i)
  45. cout<<*(a + i)<<" ";
  46. free(a);
  47. }

【3】合并排序

采用分治法。将n个元素分成各含n/2个元素的子序列，用合并排序法对两个子序列递归的排序(子序列长度为1时递归结束)，最后合并两个已排序的子序列得到结果。时间复杂度：O(nlogn)，空间复杂度：O(n)。是稳定的排序方法。

代码：

[cpp] view plaincopyprint?
  1. //合并排序
  2. #include <iostream>
  3. using namespace std;
  5. #define MAX_VALUE 100000//用于设置哨兵，避免检查是否每一个堆都是空的
  7. //合并两个子数组的函数
  8. void Merge(int *a,int p,int q,int r)
  9. {
  10. int num1,num2;
  11. num1 = q - p + 1;
  12. num2 = r - q;
  13. int *a1 = (int*)malloc((num1 + 1) *sizeof(int));
  14. int *a2 = (int*)malloc((num2 + 1) *sizeof(int));
  15. for(int i = 0;i < num1;++i)
  16. *(a1 + i) = *(a + p + i);
  17. *(a1 + num1) = MAX_VALUE;//设置哨兵元素
  18. for(int i = 0;i < num2;++i)
  19. *(a2 + i) = *(a + q + 1 + i);
  20. *(a2 + num2) = MAX_VALUE;//设置哨兵元素
  22. //进行排序
  23. int index1 = 0;
  24. int index2 = 0;
  25. for(int i = p;i <= r;++i)
  26. {
  27. if(*(a1 + index1) < *(a2 + index2))
  28. {
  29. *(a + i) = *(a1 + index1);
  30. ++index1;
  31. }
  32. else
  33. {
  34. *(a + i) = *(a2 + index2);
  35. ++index2;
  36. }
  37. }
  38. free(a1);
  1. free(a2);
  1. }
[cpp] view plaincopyprint?
  1. //递归合并排序算法
  2. void MergeSort(int *a,int p,int r)
  3. {
  4. if(p < r)
  5. {
  6. int q = (p + r) / 2;
  7. MergeSort(a,p,q);
  8. MergeSort(a,q + 1,r);
  9. Merge(a,p,q,r);
  10. }
  11. }
  13. int main()
  14. {
  15. int n,temp;
  16. cout<<"please input the number of the values that need to sort:"<<endl;
  17. cin>>n;
  18. int *a = (int*)malloc(n *sizeof(int));
  19. cout<<"please input each value:"<<endl;
  20. for(int i = 0;i < n;++i)
  21. {
  22. cin>>temp;
  23. *(a + i) = temp;
  24. }
  25. MergeSort(a,0,n - 1);
  26. cout<<"the values after sort:"<<endl;
  27. for(int i = 0;i < n;++i)
  28. cout<<*(a + i)<<" ";
  29. free(a);
  1. }

如果不使用哨兵元素，需要修改Merge函数，如下：

[cpp] view plaincopyprint?
  1. //合并两个子数组的函数(不使用哨兵元素)
  2. void Merge(int *a,int p,int q,int r)
  3. {
  4. int num1,num2;
  5. num1 = q - p + 1;
  6. num2 = r - q;
  7. int *a1 = (int*)malloc(num1 *sizeof(int));
  8. int *a2 = (int*)malloc(num2 *sizeof(int));
  9. for(int i = 0;i < num1;++i)
  10. *(a1 + i) = *(a + p + i);
  11. for(int i = 0;i < num2;++i)
  12. *(a2 + i) = *(a + q + 1 + i);
  14. //进行排序
  15. int index1 = 0;
  16. int index2 = 0;
  17. int index = p;
  18. while(index1 < num1 && index2 <num2)
  19. {
  20. if(*(a1 + index1) < *(a2 + index2))
  21. {
  22. *(a + index) = *(a1 + index1);
  23. ++index;
  24. ++index1;
  25. }
  26. else{
  27. *(a + index) = *(a2 + index2);
  28. ++index;
  29. ++index2;
  30. }
  31. }
  32. while(index1 < num1)
  33. {
  34. *(a + index) = *(a1 + index1);
  35. ++index;
  36. ++index1;
  37. }
  38. while(index2 < num2)
  39. {
  40. *(a + index) = *(a2 + index2);
  41. ++index;
  42. ++index2;
  43. }
  44. free(a1);<pre class="cpp" name="code"> free(a2);</pre>
  45. <pre></pre>
  46. <pre class="cpp" name="code">}</pre>
  47. <p><span style="color: rgb(255, 0, 0); font-family: KaiTi_GB2312; font-size: 24px;"><strong>【4】冒泡排序</strong></span></p>
  48. <p>每一趟都比较相邻两个元素，若是逆序的，则交换。结束的条件应该是“在一趟排序过程中没有进行过交换元素的操作”。时间复杂度：O(n^2)，空间复杂度O(1)。是稳定的排序。</p>
  49. <pre class="cpp" name="code">#include <iostream>
  50. using namespace std;
  52. void BubbleSort(int *a,int n)
  53. {
  54. int flag,temp;//标记是否进行过交换操作
  55. for(int i = 0;i < n - 1;++i)
  56. {
  57. flag = 0;
  58. for(int j = 0;j < n - 1 - i;++j)
  59. {
  60. if(*(a + j) > *(a + j + 1))
  61. {
  62. temp = *(a + j);
  63. *(a + j) = *(a + j + 1);
  64. *(a + j + 1) = temp;
  65. flag = 1;
  66. }
  67. }
  68. if(flag == 0)break;
  69. }
  70. }
  72. int main()
  73. {
  74. int n,temp;
  75. cout<<"please input the number of the values that need to sort:"<<endl;
  76. cin>>n;
  77. int *a = (int*)malloc(n *sizeof(int));
  78. cout<<"please input each value:"<<endl;
  79. for(int i = 0;i < n;++i)
  80. {
  81. cin>>temp;
  82. *(a + i) = temp;
  83. }
  84. BubbleSort(a,n);
  85. cout<<"the values after sort:"<<endl;
  86. for(int i = 0;i < n;++i)
  87. cout<<*(a + i)<<" ";
  88. <pre class="cpp" name="code"> free(a);</pre>
  89. <pre></pre>
  90. <pre class="cpp" name="code">}</pre>
  91. <p><span style="color: rgb(255, 0, 0); font-family: KaiTi_GB2312; font-size: 24px;"><strong>【5】快速排序</strong></span></p>
  92. <p>它是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序元素分成两个部分，其中一部分元素比另一部分元素小。再分别对这两部分元素进行排序。以达到整个元素序列有序。时间复杂度：O(nlogn)，空间复杂度O(logn)，是不稳定的算法。</p>
  93. <p>代码：</p>
  94. <pre class="cpp" name="code">#include <iostream>
  95. using namespace std;
  97. int Partition(int *a,int low,int high)
  98. {
  99. int PivotKey = *(a + low);//用第一个元素做枢轴
  100. while(low < high)
  101. {
  102. while(low < high && *(a + high) > PivotKey)--high;
  103. *(a + low) = *(a + high);
  104. while(low < high && *(a + low) < PivotKey)++low;
  105. *(a + high) = *(a + low);
  106. }
  107. *(a + low) = PivotKey;
  108. return low;
  109. }
  111. void QuickSort(int *a,int low,int high)
  112. {
  113. if(low < high)
  114. {
  115. int PivotLoc = Partition(a,low,high);
  116. QuickSort(a,low,PivotLoc - 1);
  117. QuickSort(a,PivotLoc + 1,high);
  118. }
  119. }
  121. int main()
  122. {
  123. int n,temp;
  124. cout<<"please input the number of the values that need to sort:"<<endl;
  125. cin>>n;
  126. int *a = (int*)malloc(n *sizeof(int));
  127. cout<<"please input each value:"<<endl;
  128. for(int i = 0;i < n;++i)
  129. {
  130. cin>>temp;
  131. *(a + i) = temp;
  132. }
  133. QuickSort(a,0,n - 1);
  134. cout<<"the values after sort:"<<endl;
  135. for(int i = 0;i < n;++i)
  136. cout<<*(a + i)<<" ";
  137. free(a);}</pre>
  138. <p><br>
  139. </p>
  140. <p><span style="color: rgb(255, 0, 0); font-family: KaiTi_GB2312; font-size: 24px;"><strong>【6】计数排序</strong></span></p>
  141. <p>计数排序的思想是对每一个输入元素x，确定出小于x的元素的个数。然后我们就可以直接把它放在嘴中输出数组中相应的位置上。</p>
  142. <p>但是计数排序基于这样一个假设：n个输入元素的每一个大小范围都是[0,k]。</p>
  143. <p>代码：</p>
  144. <p><pre class="cpp" name="code">#include <iostream>
  145. using namespace std;
  147. //Counting Sort Algorithm
  148. //A:array before sorting
  149. //B:array after sorting
  150. //n:the number of A
  151. //k:all the elements is in [0,k]
  152. void CountintSort(int A[],int *B,int n,int k,int *C)
  153. {
  154. //初始化C数组
  155. for (int i = 0;i <= k;++i)
  156. {
  157. C[i] = 0;
  158. }
  160. for (int i = 0;i < n;++i)
  161. {
  162. ++C[A[i]];//C[i]：值等于i的元素的个数
  163. }
  165. for (int i = 1;i <= k;++i)
  166. {
  167. C[i] += C[i - 1];//C[i]：值小于等于i的元素的个数
  168. }
  170. for (int i = n - 1;i >= 0;--i)
  171. {
  172. B[C[A[i]] - 1] = A[i];//注意：下标索引从0开始！
  173. --C[A[i]];
  174. }
  175. }
  177. int main()
  178. {
  179. int A[6] = {2,7,1,4,0,3};
  180. int n = 6;
  181. int k = 7;
  182. int *B = (int *)malloc(n *sizeof(int));
  183. int *C = (int *)malloc((k + 1) *sizeof(int));
  184. cout << "排序之前的元素：" << endl;
  185. for (int i = 0;i < n;++i)
  186. {
  187. cout << A[i] << " ";
  188. }
  189. cout << endl;
  190. CountintSort(A,B,n,k,C);
  191. cout << "排序之后的元素：" << endl;
  192. for (int i = 0;i < n;++i)
  193. {
  194. cout << B[i] << " ";
  195. }
  196. cout << endl;
  197. free(B);
  198. free(C);
  199. }</pre><br>
  200. 运行结果：<p></p>
  201. <p><img alt="" src="http://my.csdn.net/uploads/201206/10/1339316958_2887.jpg"><br>
  202. </p>
  203. <p><strong>时间复杂度分析：</strong></p>
  204. <p>时间复杂度是O(k + n)。一般，当k = O(n)时，常常采用计数排序。这时候的运行时间为O(n)。</p>
  205. <p>计数排序是稳定的排序。</p>
  206. <p><br>
  207. </p>
  208. <p>一些好的参考资料：不同排序算法间的比较：<a href="http://commons.wikimedia.org/wiki/File:SortingAlgoComp.png">http://commons.wikimedia.org/wiki/File:SortingAlgoComp.png</a><br>
  209. 一些排序算法的 C 及 Pascal 实现 ：<br>
  210. <a href="http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95">http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95</a></p>
  211. <p>最后，简要比较一下各排序算法，转自维基百科：</p>
  212. <p><span id=".E7.AE.80.E8.A6.81.E6.AF.94.E8.BE.83"class="mw-headline">简要比较</span>
  213. <table class="wikitable ">
  214. <tbody>
  215. <tr>
  216. <th rowSpan="2">名称</th>
  217. <th rowSpan="2">数据对象</th>
  218. <th rowSpan="2">稳定性</th>
  219. <th colSpan="2">时间复杂度</th>
  220. <th rowSpan="2">空间复杂度</th>
  221. <th rowSpan="2">描述</th>
  222. </tr>
  223. <tr>
  224. <th>平均</th>
  225. <th>最坏</th>
  226. </tr>
  227. <tr>
  228. <td>插入排序</td>
  229. <td>数组、链表</td>
  230. <td>√</td>
  231. <td colSpan="2"><span dir="ltr"class="texhtml"><em>O</em>(<em>n</em><sup>2</sup>)</span></td>
  232. <td>O(1)</td>
  233. <td>(有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。</td>
  234. </tr>
  235. <tr>
  236. <td rowSpan="2">直接选择排序</td>
  237. <td>数组</td>
  238. <td>×</td>
  239. <td rowSpan="2" colSpan="2"><span dir="ltr"class="texhtml"><em>O</em>(<em>n</em><sup>2</sup>)</span></td>
  240. <td rowSpan="2">O(1)</td>
  241. <td rowSpan="2">(有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。 对数组：比较得多，换得少。</td>
  242. </tr>
  243. <tr>
  244. <td>链表</td>
  245. <td>√</td>
  246. </tr>
  247. <tr>
  248. <td>堆排序</td>
  249. <td>数组</td>
  250. <td>×</td>
  251. <td colSpan="2">O(nlogn)</td>
  252. <td>O(1)</td>
  253. <td>(最大堆,有序区)。从堆顶把根卸出来放在有序区之前，再恢复堆。</td>
  254. </tr>
  255. <tr>
  256. <td>归并排序</td>
  257. <td>数组、链表</td>
  258. <td>√</td>
  259. <td colSpan="2">O(nlogn)</td>
  260. <td>O(n) +O(logn) ， 如果不是从下到上</td>
  261. <td>把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。</td>
  262. </tr>
  263. <tr>
  264. <td>快速排序</td>
  265. <td>数组</td>
  266. <td>×</td>
  267. <td>O(nlogn)</td>
  268. <td><span dir="ltr" class="texhtml"><em>O</em>(<em>n</em><sup>2</sup>)</span></td>
  269. <td>O(logn) ,O(n)</td>
  270. <td>(小数,枢纽元,大数)。</td>
  271. </tr>
  272. <tr>
  273. <td>Accum qsort</td>
  274. <td>链表</td>
  275. <td>√</td>
  276. <td>O(nlogn)</td>
  277. <td><span dir="ltr" class="texhtml"><em>O</em>(<em>n</em><sup>2</sup>)</span></td>
  278. <td>O(logn) ,O(n)</td>
  279. <td>(无序区,有序区)。把无序区分为(小数,枢纽元,大数)，从后到前压入有序区。</td>
  280. </tr>
  281. <tr>
  282. <td colSpan="7"> </td>
  283. <td> </td>
  284. </tr>
  285. <tr>
  286. <td>决策树排序</td>
  287. <td> </td>
  288. <td>√</td>
  289. <td colSpan="2">O(logn!)</td>
  290. <td>O(n!)</td>
  291. <td>O(n) <O(logn!) <O(nlogn)</td>
  292. </tr>
  293. <tr>
  294. <td colSpan="7"> </td>
  295. <td> </td>
  296. </tr>
  297. <tr>
  298. <td>计数排序</td>
  299. <td>数组、链表</td>
  300. <td>√</td>
  301. <td colSpan="2">O(n)</td>
  302. <td>O(n+m)</td>
  303. <td>统计小于等于该元素值的元素的个数 i，于是该元素就放在目标数组的索引 i位。(i≥0)</td>
  304. </tr>
  305. <tr>
  306. <td>桶排序</td>
  307. <td>数组、链表</td>
  308. <td>√</td>
  309. <td colSpan="2">O(n)</td>
  310. <td>O(m)</td>
  311. <td>将值为 i 的元素放入i 号桶，最后依次把桶里的元素倒出来。</td>
  312. </tr>
  313. <tr>
  314. <td>基数排序</td>
  315. <td>数组、链表</td>
  316. <td>√</td>
  317. <td colSpan="2"> </td>
  318. <td> </td>
  319. <td>一种多关键字的排序算法，可用桶排序实现。</td>
  320. </tr>
  321. </tbody>
  322. </table>
  323. <p></p>
  324. <ul>
  325. <li>均按从小到大排列 </li><li>n 代表数据规模 </li><li>m 代表数据的最大值减最小值 </li></ul>
  326. <div><pre class="cpp" name="code"></pre></div><div></div><pre></pre>
  327. <pre></pre>
  328. <pre></pre>
  329. <pre></pre>
  330. <pre></pre>
  331. <pre></pre>
  332. <pre></pre>
  333. <pre></pre>
  334. </pre>
分享到：
| C++标准库头文件介绍
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics