[转载]排序算法 快速排序l两种算法和堆排序

baacloud免费翻墙vpn注册使用

[转载]排序算法 快速排序l两种算法和堆排序(原创) – 北冥茶花开 – 博客园.

快排算法有两种 一种是算法导论里的改进的快排算法
另一种是清华那本数据结构中的古典快排算法。这里我们会看到他们在运行时间上的不同,而且古典快排竟然优于改进的快排
。呵呵 好了不多说  上代码吧  。

#include<stdio.h>
 #include<stdlib.h>
 #include<time.h>               //时间计数头文件
 
 
 int  left(int i)
 {
         return 2*i;
 }
 
 int right(int i)
 {
         return 2*i+1;
 }
 
 
 void MAX_HEAPIFY(int arr[],int i,int heapsize) //调堆根函数,这名字自己YY的,基本原理就是让不合理的角色合理化,
 {                                                //能力小的往下降,能力大的做老大。
         int l,r;
         int largest;
         int temp;
         l= left(i);
         r=right(i);
         if(l<=heapsize&&arr[l]>arr[i])                  //左孩子比较大那么暂记录左孩子 选他做准太子。
                 largest=l;
         else
                 largest=i;
         if(r<=heapsize&&arr[r]>arr[largest])        //右孩子更有实力,选他做准太子
                 largest=r;
         if(largest!=i)                                 //当权者arr【i】不是实力最大,则交换二者
         {
                 temp  =arr[largest];
                 arr[largest]=arr[i];
                 arr[i]   =temp;
         MAX_HEAPIFY(arr,largest,heapsize);          //给以前的当权者找个归路
         }
 
 }
 
 
 void BUILD_MAX_HEAP(int arr[],int heapsize)             //建堆
 {
         int contrasize=int (heapsize/2);                  //数组建堆是下标为n/2+1,...,n 是叶子节点。
         for(int i=contrasize;i>=1;i--)
                 MAX_HEAPIFY(arr,i,heapsize);
 
 }
 
 void HEAP_SORT(int arr[],int heapsize)                //堆排序算法
 {
         clock_t start=clock();                             //计时开始时钟变量
         double duration;                                    //程序消耗时钟个数。
         int temp;
         int equalsize=heapsize;
         BUILD_MAX_HEAP(arr,heapsize);                      //首建堆,但是实际上为了初始化。仔细体味能感觉到
                 for(int i=heapsize;i>=2;i--)
                 {
                         temp  =arr[i];
                         arr[i]=arr[1];
             arr[1]=temp;
                         equalsize=equalsize-1;
             MAX_HEAPIFY(arr,1,equalsize);
                 }
                  printf("排序后的结果是:\n");
      for(int i=1;i<=heapsize;i++)
                  printf(" %d ",arr[i]);
      clock_t finish=clock();
          duration=(double)(finish-start)/CLOCKS_PER_SEC;
          printf("堆排序的耗费时间为: %f\n",duration);
 }
 
 /*上面是堆排序,下面是快速排序的两个的版本*/
 
 
 void exchange(int arr[],int i,int j)                  //交换数组里的两个元素,为了后面方便我故意挪出来的。
 {                                                     //也算是减少内聚低耦合吧 自己都觉得自己太自恋了。
         int temp;
         temp  =arr[i];
         arr[i]=arr[j];
         arr[j]=temp;
         return ;
 }
 
 int partition(int arr[],int p,int r)                   //这是改进版的 就是圣经上的那个快排选分段标记的函数
 {
      int contra=arr[r];
          int i,j;
          i=p-1;
          for( j=p;j<=r-1;j++)                    //核心代码 这个实际上下面的是区别是这个固定一头,后面的小于标准
          {                                       //则往这边靠,正是这个原因导致他不如古典的快排耗时短,后面运行结果将验证
                  if(arr[j]<=contra)
                  {
                          i=i+1;
                          exchange(arr,i,j);
                  }
          }
          exchange(arr,i+1,r);
          return i+1;
 }
 
 int quicksort(int arr[],int p,int r)                //快排函数主体  没什么好说的 
 {
         int q;
         if(p < r)
         {
                 q=partition(arr,p,r);
                 quicksort(arr,p,q-1);
                 quicksort(arr,q+1,r);
 
         }
         
         return 0;
 }
 
 
 /* 上面是改进后快速排序算法,下面这个是快速排序的最早版本  实际上清华的那本什么数据结构上就这个*/
 
 int hoarepartition(int arr[],int p,int r)                       //这是古典的快排
 {
   int contra=arr[p];
   int i=p;
   int j=r;
   while(true)
   {
           for(;arr[j]>contra;j--);                               //注意哦 有个小分号看见没?
           for(;arr[i]<contra;i++);                              //选择contra的左大与右小交换 这个是快排的核心两头动
                   if(i<j)
                         exchange( arr, i, j);
                   else
                           return j;
 
   }
 
 }
 
 
 int hoarequicksort(int arr[],int p,int r)               //快排主体没什么好说的 呵呵
 {
         int q;
         if(p < r)
         {
                 q=hoarepartition(arr,p,r);
                 quicksort(arr,p,q-1);
                 quicksort(arr,q+1,r);
 
         }
         
         return 0;
 }
 
 
 int initarr(int arr1[],int arr2[],int arrcol)        //这个函数自己构思的 主要是为了便于后面对数组排序时
 {                                                      //前一次排序算法对数组的影响不会殃及下一次别的算法对数组调用。
    for(int i=1;i<=arrcol;i++)
         {
                 arr1[i]=arr2[i];
         }
    printf("排序前的数组为:\n");
    for(int i=1;i<=arrcol;i++)
            printf(" %d ",arr1[i]);
    printf("\n");
    return 0;
 }
 
 int _tmain(int argc, _TCHAR* argv[])                      //主函数没什么好说的 呵呵 
 {
         time_t timer;
         int number;
         int choice;
         clock_t start,finish;
         double duration;
         srand((unsigned) time(&timer));
         printf("请输入你想排序的的随机数个数:");
         scanf("%d",&number);
         int *arraytest=new int[number+1];                       //这个地方是为了克服VC的局限,不能申明
         arraytest[0]=0;                                         //未定义大小的数组,所以采用指针的形式先申明在转换数组
         printf("待排序数组为:\n");
         for(int i=1;i<=number;i++)
         {
                 arraytest[i]=rand()%1000;                          //记得上次Cydelovy 大神给我说过随机生成,这次我就自己YY啦
                 printf(" %d ",arraytest[i]);
         }
         printf("\n");
     int *arraycpy=new int[number+1];
 
         for(int i=0;i<=number;i++)
         {
                 arraycpy[i]=arraytest[i];                         //保存数组副本。便于适合不用排序方法不影响时间。
         }
     printf("请输入您的操作 输入CTRL+c则推出:\n");
         printf("1  堆排序         2 古典快速排序        3 改进的快速排序\n");
         while(scanf("%d",&choice)!=EOF)
         {
        switch(choice)
            {
            case 1:
                       initarr(arraytest,arraycpy,number);           //你永远不知道第几次进入这个case,进入前数组是什么样
                       HEAP_SORT(arraytest,number);                  //那你就有义务进行数组同一,对,不是统一。
                           break;
            case 2:                                              //下面同了啊 不讲了啊 
                       initarr(arraytest,arraycpy,number);
               start=clock();
                   hoarequicksort(arraytest,1,number);
                           printf("排序后的结果是:\n");
               for(int i=1;i<=number;i++)
                       printf(" %d ",arraytest[i]);
                           finish=clock();
                   duration=(double)(finish-start)/CLOCKS_PER_SEC;
                   printf("\n古典快速排序的耗费时间为: %f\n",duration);
                           break;
            case 3:
                       initarr(arraytest,arraycpy,number);
               start=clock();
                           hoarequicksort(arraytest,1,number);
                           printf("排序后的结果是:\n");
               for(int i=1;i<=number;i++)
                       printf(" %d ",arraytest[i]);
                           finish=clock();
                   duration=(double)(finish-start)/CLOCKS_PER_SEC;
                   printf("\n改进的快速排序的耗费时间为: %f\n",duration);
                           break;
            default:
                       printf("\n输入错误 ");
                           break;
            }
 
 
 
 
         }
         return 0;
 }
赞(0) 打赏
分享到: 更多 (0)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏