经典四讲贯通C++排序之四选择排序

　　我们都知道C++排序方法中，有四种常用方法插入排序、希尔排序、交换排序以及选择排序。这篇文章我们介绍选择排序。（本系列文章统一测试程序）

10年积累的网站制作、成都网站制作经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站制作后付款的网站建设流程，更有侯马免费网站建设让你可以放心的选择与我们合作。

　　选择排序

　　基本思想是：每次选出第i小的记录，放在第i个位置(i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了)。当i=N-1时就排完了。

　　直接选择排序

　　直选排序简单的再现了选择排序的基本思想，***次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。

 
 
 
  
  
  template   
  
  
  void SelectSort(T a[], int N, int& KCN, int& RMN)  
  
  
  {  
  
  
  KCN = 0; RMN = 0;  
  
  
  for (int i = 0; i < N; i++)  
  
  
  {  
  
  
  for (int j = i + 1, k = i; j < N; j++) if (++KCN && a[j] < a[k]) k = j;//select min  
  
  
  if (k != i) { swap(a[k], a[i]); RMN += 3; }  
  
  
  }  
  
  
  }

　　测试结果：

 
 
 
  
  
  Sort ascending N=10000 TimeSpared: 721ms  
  
  
  KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25  
  
  
  RMN=0 RMN/N=0 RMN/N^2=0 RMN/NlogN=0  
  
  
  Sort randomness N=10000 TimeSpared: 711ms  
  
  
  KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25  
  
  
  RMN=29955 RMN/N=2.9955 RMN/N^2=0.00029955 RMN/NlogN=0.225434  
  
  
  Sort descending N=10000 TimeSpared: 711ms  
  
  
  KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25  
  
  
  RMN=15000 RMN/N=1.5 RMN/N^2=0.00015 RMN/NlogN=0.112886

　　可以看到KCN固定为n(n-1)/2。另外一件有趣的事是，RMN=0的正序花的时间居然比RMN接近3(n-1)的乱序还多。一是说明测试精度不够，在我的机器上多次测试结果上下浮动10ms是常有的事;二是说明和KCN的n(n-1)/2相比，RMN的3(n-1)有些微不足道。

#p#

　　锦标排序

　　从直选排序看来，算法的瓶颈在于KCN，而实际上，对于后续的寻找最小值来说，时间复杂度可以降到O(logn)。最为直接的做法是采用锦标赛的办法，将冠军拿走之后，只要把冠军打过的比赛重赛一遍，那么剩下的人中的“冠军”就产生了，而重赛的次数就是竞赛树的深度。实际写的时候，弄不好就会写得很“蠢”，不只多余占用了大量内存，还会导致无用的判断。我没见过让人满意的例程(殷版上的实在太恶心了)，自己又写不出来漂亮的，也就不献丑了(其实这是惰性的缘故，有了快排之后，大多数人都不会对其他内排感兴趣，除了基数排序)。实在无聊的时候，不妨写(或者改进)锦标排序来打发时间，^_^。

　　堆排序

　　锦标排序的附加储存太多了，而高效的寻找***值或最小值(O(logn))，我们还有一种方法是堆。这里使用了***堆，用待排记录的空间充当堆空间，将堆顶的记录(目前***)和堆的***一个记录交换，当堆逐渐缩小成1的时候，记录就排序完成了。显而易见的，时间复杂度为O(nlogn)，并且没有很糟的情况。

 
 
 
  
  
  template   
  
  
  void FilterDown(T a[], int i, int N, int& KCN, int& RMN)  
  
  
  {  
  
  
  int child = 2 * i + 1; T temp = a[i];  
  
  
  while (child < N)  
  
  
  {  
  
  
  if (child < N - 1 && a[child] < a[child+1]) child++;  
  
  
  if (++KCN && temp >= a[child]) break;//不需调整，结束调整  
  
  
  a[i] = a[child]; RMN++;  
  
  
  i = child; child = 2 * i + 1;  
  
  
  }  
  
  
  a[i] = temp; RMN++;  
  
  
  }  
  
  
  template   
  
  
  void HeapSort(T a[], int N, int& KCN, int& RMN)  
  
  
  {  
  
  
  int i;  
  
  
  for (i = (N - 2)/2; i >= 0; i--) FilterDown (a, i, N, KCN, RMN); //生成***堆   
  
  
  for (i = N - 1; i > 0; i--)  
  
  
  {  
  
  
  swap(a[0], a[i]); RMN += 3;  
  
  
  FilterDown(a, 0, i, KCN, RMN);  
  
  
  }  
  
  
  }

　　测试结果，直接测试的是N=100000：

 
 
 
  
  
  Sort ascending N=100000 TimeSpared: 110ms  
  
  
  KCN=1556441 KCN/N=15.5644 KCN/N^2=0.000155644KCN/NlogN=0.937071  
  
  
  RMN=2000851 RMN/N=20.0085 RMN/N^2=0.000200085RMN/NlogN=1.20463  
  
  
  Sort randomness N=100000 TimeSpared: 160ms  
  
  
  KCN=3047006 KCN/N=30.4701 KCN/N^2=0.000304701KCN/NlogN=1.83448  
  
  
  RMN=3898565 RMN/N=38.9857 RMN/N^2=0.000389857RMN/NlogN=2.34717  
  
  
  Sort descending N=100000 TimeSpared: 90ms  
  
  
  KCN=4510383 KCN/N=45.1038 KCN/N^2=0.000451038KCN/NlogN=2.71552  
  
  
  RMN=5745996 RMN/N=57.46 RMN/N^2=0.0005746 RMN/NlogN=3.45943

　　整体性能非常不错，附加储存1，还没有很糟的情况，如果实在不放心快排的最坏情况，堆排确实是个好选择。这里仍然出现了KCN、RMN多的反而消耗时间少的例子——误差70ms是不可能的，看来CPU优化的作用还是非常明显的(可能还和Cache有关)。

文章题目：经典四讲贯通C++排序之四选择排序
分享网址：http://www.hantingmc.com/qtweb/news45/290395.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容