首页 > 编程语言 > 详细

快速排序的三种写法的效率比较

时间：2015-05-12 22:50:13      阅读：407      评论：0      收藏：0      [点我收藏+]
 
分类： C++ C语言 数据结构 2012-09-02 20:26 459人阅读 评论(0) 收藏 举报
数据结构算法null

            最近在复习排序和查找算法的时候，回想算法课程和数据结构课程上面各种写法，总结一下，顺便比较了一下它们之间的效率，

 

另《外数据结构》书本上阐述，如果比较的枢纽值不是第一个或者最后一个而是 a[low] ,a[high],a[(high+low)/2] 的中间值，效率还会好很多，但是我在实现的过程中，总是搬移到了错误的位置，没有实现

 

技术分享

 

[cpp] view plaincopy
  1. #include <iostream.h>  
  2. #include <windows.h>  
  3. #include <ctime>  
  4. #include <math.h>  
  5. #include <cstdlib>  
  6. #include <stdio.h>  
  7.   
  8. void QuickSort( int a[],int low,int high);  //比较经典的一种，将往中间扫面时找到的满足条件的交换  
  9. void QuickSort3( int a[],int low,int high); //枢纽暂存，每次找到一个比枢纽大或者小的，就放到上一次搬离的位置，最后把枢纽放回到low处（低地址必须小于高地址，不能等于）  
  10.  void QuickSort2( int a[],int low,int high);    //只有一个while，指针都从头部开始，，快指针每次都向后移动，遇到一个比枢纽大的就和慢指针交换值  
  11.   
  12. //产生随机数  
  13. int randArr(int * pint , int size);   
  14.   
  15. int size = 0;  
  16. int main()  
  17. {  
  18.      int a[] ={4,-2,3,19,0,-4,99,7,2,-5,0,-11,2,2,56,-8,0,17,200,5,1,3,5,4,6,-5,29,-1,8};  
  19.      int b[] ={ 34,51,38,65,119,76,16,27};  
  20.       //int b[] ={76, 119 };  
  21.     int tsize=150000;  
  22.      int *pint = new int[tsize];  
  23.      int *pint2 = new int[tsize];  
  24.      int *pint3 = new int[tsize];  
  25.      int id = 5;  
  26.   
  27.      if(! randArr(pint,tsize) )  
  28.         return 0;  
  29. //   memcpy(pint ,a,sizeof(int) * tsize);  
  30.      memcpy(pint2,pint,sizeof(int) * tsize);  
  31.      memcpy(pint3,pint,sizeof(int) * tsize);  
  32.   
  33.      size = tsize;  
  34.     printf("=====before====\n");  
  35.      for(id = 0 ; id< 10;id++)  
  36.      {  
  37.             printf("%3d ", pint[id]);  
  38.      }printf("=====before====\n");  
  39.   
  40.     int start  = GetTickCount();  
  41.   
  42.      QuickSort(pint,0,size -1);  
  43.     cout<<"time QuickSort used="<< GetTickCount() - start << endl;  
  44.      for(id = 0 ; id< 10;id++)  
  45.      {  
  46.             printf("%3d ", pint[id]);  
  47.      }printf("======QuickSort===\n\n");  
  48.   
  49.        
  50.      start  = GetTickCount();  
  51.   
  52.      QuickSort2(pint2,0,size -1);  
  53.     cout<<"time QuickSort2 used="<< GetTickCount() - start << endl;  
  54.      for(id = 0 ; id< 10;id++)  
  55.      {    
  56.   
  57.         printf("%3d ", pint2[id]);  
  58.   
  59.      }printf("======QuickSort2===\n\n");  
  60.   
  61.      QuickSort3(pint3,0,size -1);  
  62.     cout<<"time QuickSort3 used="<< GetTickCount() - start << endl;  
  63.      for(id = 0 ; id< tsize;id++)  
  64.      {    
  65.          if(pint[id] != pint2[id])  
  66.          {  
  67.             printf("Confliction!! %d",id);  
  68.             break;  
  69.          }  
  70.   
  71.   
  72.      }printf("======QuickSort3===\n\n");  
  73.   
  74.      return 0;  
  75. }  
  76.   
  77. void QuickSort(int a[],int l,int h)  
  78. {  
  79.     int po;  
  80.     int high = h , low = l;  
  81.     if(low < high )  
  82.     {  
  83.         po = a[l];  
  84.         low++;  
  85.         while(1)  
  86.         {  
  87.             while(low <=  high && a[high] >= po) high--;  
  88.             while(low <=  high && a[low] <= po) low++;  
  89.   
  90.             if(low < high)  
  91.             {  
  92.                 a[low] ^= a[high];  
  93.                 a[high] ^= a[low];  
  94.                 a[low] ^= a[high];  
  95.                 low++;  
  96.                 high--;  
  97.             }  
  98.             else  
  99.                 break;  
  100.         }  
  101.          a[l] =   a[high];  
  102.         a[high]  = po;  
  103.   
  104.         QuickSort(a,l,high-1);  
  105.         QuickSort(a,high+1,h);  
  106.     }  
  107.   
  108.   
  109. }  
  110.   
  111. void QuickSort2(int a[],int l ,int h)  
  112. {  
  113.     int po;  
  114.     int high = h,low = l;  
  115.     if( l < h )  
  116.     {  
  117.         po = a[l];  
  118.         while( low < high)  
  119.         {  
  120.             while( low < high && a[high] >= po ) high--;  
  121.             a[low] = a[high];  
  122.             while( low < high && a[low] <= po ) low++;  
  123.             a[high] = a[low];  
  124.         }  
  125.         a[low] = po;  
  126.   
  127.         QuickSort2(a,l,low-1);  
  128.         QuickSort2(a,low+1,h);  
  129.     }  
  130. }  
  131.   
  132.   
  133. void QuickSort3(int a[],int l ,int h )  
  134. {  
  135.     int high  = l+1, low = l+1;  
  136.     int po = a[l];  
  137.   
  138.     if( l < h)  
  139.     {  
  140.         while( high <= h)  
  141.         {  
  142.             if( a[high] < po)    //找到慢指针  
  143.             {  
  144.                 if(high != low)  
  145.                 {  
  146.                     a[low] ^=a[high];  
  147.                     a[high] ^=a[low];  
  148.                     a[low] ^=a[high];  
  149.                 }  
  150.                 low++;    
  151.             }  
  152.             high++;  
  153.         }  
  154.   
  155.         if(low-1 != l)  
  156.         {  
  157.             a[low-1] ^=a[l];  
  158.             a[l] ^=a[low-1];  
  159.             a[low-1] ^=a[l];  
  160.         }  
  161.   
  162.         low--;  
  163.         QuickSort3(a,l,low - 1);  
  164.         QuickSort3(a,low+1 ,h);  
  165.       
  166.       
  167.     }  
  168. }  
  169.   
  170.   
  171.   
  172. int randArr(int * pint , int size)  
  173. {  
  174.     int i = 0;  
  175.     if(!pint)   return 0;  
  176.     srand((unsigned int)time(NULL));  
  177.   
  178.     for( i = 0 ; i<size; i++)  
  179.     {  
  180.             pint[i] = rand() % 100 ;              
  181.             if( rand() % 10 == 1 && rand() % 10 == 1 && rand() % 10 == 1 &&pint[i] % 10 == 2)  
  182.                 pint[i] *= -1;  
  183.     }  
  184.     return 1;  
  185. }  

快速排序的三种写法的效率比较

原文：http://www.cnblogs.com/bb3q/p/4498746.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！