大家帮小弟我看一下，为什么搞来搞去快速排序的效率没有归并排序的高
大家帮我看一下，为什么搞来搞去快速排序的效率没有归并排序的高？
我的归并和快速两种排序方法都是非递归的，好多人以及教材上都说快排是最快的，可为什么我亲自测试后，快速排序怎么都没有归并快，甚至非递归快速排序没有递归的快速排序快还，我想尽一切办法优化了，在处理一亿大的随机数组，归并十几秒，快速排序非递归竟然要130多秒
------解决思路----------------------
你做100万次长度为100的QInsertSort()和真正的QuickSort()试试！
用 L->p[i] 的方式存取成员每次都要重新计算地址，你的 swap 要计算9次地址，还不如用中间变量交换呢。
MergeSort()是二分递归的，QuickSort()却是半递归/半非递归的，怎么比啊。
我的归并和快速两种排序方法都是非递归的，好多人以及教材上都说快排是最快的，可为什么我亲自测试后，快速排序怎么都没有归并快，甚至非递归快速排序没有递归的快速排序快还，我想尽一切办法优化了，在处理一亿大的随机数组，归并十几秒，快速排序非递归竟然要130多秒
#include<iostream>
using namespace std;
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#include "memory.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 67891235//排序数组的个数
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
typedef struct sqList
{
ElemType *p;
int length;
}SqList,*SL;
int M=0;//全局变量用来做随机数种子
int r1()//随机数生成函数
{
int a,b;
srand(M);
a=rand();
M=M+1;
srand(M);
b=rand();
return a*b;
}
void InitSqlist(SL &L,int len)//建立数组
{
L=(SL)malloc(sizeof(SqList));
L->p=(ElemType *)malloc((MAXSIZE+1)*sizeof(ElemType));
L->length=len;
srand(20);
for(int i=1;i<=len;i++)
{
L->p[i]=r1();///len-i;///rand()%len+1;注释里边是几种给数组赋值的办法，分别对应平均，最差
}
}
void swap(SL L,int i,int j)//因为快速排序要大量的交换，故采用位运算提高效率
{
L->p[i]=(L->p[i])^(L->p[j]);
L->p[j]=(L->p[i])^(L->p[j]);
L->p[i]=(L->p[i])^(L->p[j]);
}
void QInsertSort(SL L,int low,int high)//快速排序时用的小数组插入排序函数
{
int i,j;
for(i=low+1;i<=high;i++)
{
if(L->p[i]<L->p[i-1])
{
L->p[0]=L->p[i];
for(j=i-1;L->p[j]>L->p[0]&&j>=low;j--)
{
L->p[j+1]=L->p[j];
}
L->p[j+1]=L->p[0];
}
}
}
void MSort(ElemType *a,ElemType *b,int s,int m,int e)//归并算法用的归并函数
{
int j,k;
j=m+1;
for(k=s;s<=m&&j<=e;k++)
{
if(a[s]<a[j])
{
b[k]=a[s++];
}
else
{
b[k]=a[j++];
}
}
if(s==(m+1))
{
while(j!=(e+1))
{
b[k++]=a[j++];
}
}
else
{
while(s!=(m+1))
{
b[k++]=a[s++];
}
}
}
void MergeSort(ElemType *a,ElemType *b,int s,int e)//递归的归并算法
{
if(s!=e)
{
ElemType p[MAXSIZE+1];
int m=(s+e)/2;
MergeSort(a,p,s,m);
MergeSort(a,p,m+1,e);
MSort(p,b,s,m,e);
}
else
{
b[e]=a[s];
}
}
void NoMergeSort(ElemType *&a,int s,int e)//非递归的归并算法
{
int i,j,k;
if(s==e)
{
return;
}
int INCRE=1;
ElemType *q;
ElemType *p=(ElemType *)malloc((MAXSIZE+1)*sizeof(ElemType));
p[MAXSIZE]=a[MAXSIZE];
while(INCRE<(e-s+1))
{
INCRE*=2;
for(i=INCRE;i<e;i+=INCRE)
{
MSort(a,p,i-INCRE+1,i-INCRE/2,i);
}
if((i-e)<(INCRE/2))
{
MSort(a,p,i-INCRE+1,i-INCRE/2,e);
}
else
{
for(k=(i-INCRE+1);k<=e;k++)
p[k]=a[k];
//while(!memcpy(p+i-INCRE+1,a+i-INCRE+1,(e-i+INCRE)*sizeof(ElemType)));这句虽说简洁华丽，可效率不高
}
q=a;
a=p;
p=q;
}
}
void MSORT(SL L)//归并排序封装起来
{
//MergeSort(L->p,L->p,1,L->length);
NoMergeSort(L->p,1,L->length);
}
int getp(SL L,int low,int high)//求快速排序的轴值pivot函数
{
ElemType temp,pivotkey;
temp=0;
int i,j,k,step,m,n;
m=(low+high)/2;
if(L->p[low]>L->p[m])//三数取中
swap(L,low,m);
if(L->p[m]>L->p[high])
swap(L,m,high);
if(L->p[low]<L->p[m])
swap(L,low,m);
L->p[0]=L->p[low];
pivotkey=L->p[0];
while(low<high)
{
while(high>low&&L->p[high]>=pivotkey)
high--;
L->p[low]=L->p[high];
while(high>low&&L->p[low]<=pivotkey)
low++;
L->p[high]=L->p[low];
}
L->p[low]=pivotkey;
return low;
}
void QuickSort(SL &L,int low,int high)//快排递归
{
int pivot;
if((high-low+1)>100)
{
while(low<high)
{
pivot=getp(L,low,high);
QuickSort(L,low,pivot-1);
low=pivot+1;
}
}
else
{
QInsertSort(L,low,high);//QShellSort(L,low,high);
}
}
void NoQuickSort(SL &L,int low,int high)//快排非递归
{
int pivot,p,i;
int c;
int Stack[10000],top=0;
pivot=getp(L,low,high);
c=pivot+1;
for(i=c+1;i<=high;i++)//让最大值到最高位
{
if(L->p[i]>L->p[c])
{
c=i;
}
}
if(c!=high)//为了提高效率swap函数采用异或运算，故必须判断c与high是否重合，否则二者相同异或其中一个变成0
swap(L,c,high);
Stack[top++]=high;
Stack[top++]=pivot;
pivot=high;
for(;;)
{
if((pivot-low)>100)
{
pivot=getp(L,low,pivot-1);
Stack[top++]=pivot;
}
else
{
QInsertSort(L,low,pivot-1);
low=pivot+1;
if(top==1) break;
pivot=Stack[top-2];
top--;
}
}
}
void QSort(SL L)//快排封装起来
{
QuickSort(L,1,L->length); //NoQuickSort(L,1,L->length);
}
int main()
{
SL P,L;
int i,j=0;
clock_t start,finish;
M=0;
InitSqlist(P,MAXSIZE);
start=clock();
MSORT(P);
finish=clock();
printf("本次计算耗时%13.8f\n",(double)(finish-start)/CLOCKS_PER_SEC);
M=0;//计算完一次后随机数种子置0
InitSqlist(P,MAXSIZE);
start=clock();
QSort(P);
finish=clock();
printf("本次计算耗时%13.8f\n",(double)(finish-start)/CLOCKS_PER_SEC);
return 0;
}
------解决思路----------------------
你做100万次长度为100的QInsertSort()和真正的QuickSort()试试！
用 L->p[i] 的方式存取成员每次都要重新计算地址，你的 swap 要计算9次地址，还不如用中间变量交换呢。
MergeSort()是二分递归的，QuickSort()却是半递归/半非递归的，怎么比啊。