Mikel
[转载]排序算法 快速排序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;
}
