一个让我恰不消的问题：数据量太大时（如50000），归并排序算法造成系统崩溃问题、、
求解决方案。直接看归并排序函数我就全部复制过来了。
程序代码：#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
////////直接插入排序
int insertsort(int a[],int n){
int i,j;
int b=0; //交换次数
for(i=0;i<n;i++){
j=i+1;
if (a[j]>a[i])
{
int t=a[j];
while(i>=0&&t>a[i])//特别注意此处是t,别写a[j]
{
a[i+1]=a[i];
i--;
b++;
}
a[i+1]=t;
b++;
}
i=j-1;
}
return b;
}
/////////////希尔排序
int shellsort(int a[],int n){
int b=0,m=n;
while(m>=1)
{
m/=2;
{
int i,j;
for (i=m;i<n;i++)
{
int t=a[i];
j=i-m;
if (t>a[j])
{
while(j>=0&&a[j]<t)
{
a[j+m]=a[j];
j-=m;
b++;
}
a[j+m]=t;
b++;
}
}
}
}
return b;
}
////////////////冒泡排序
int bubblesort(int a[],int n){
int b=0;
int i,j;
for (i=n;i>0;i--)
{
int is=1;
for (j=0;j<i;j++)
if(a[j]<a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
is=0;
b++;
}
b++;
if(is) break;
}
return b;
}
/////////////////////快速排序
int quicksort(int a[],int left,int right){
static int bq;
int i=left,j=right;
int t=a[i];
while(i<j){
while((a[j]<t)&&(i<j)){
bq++;
j--;
}
if(j>i){
a[i]=a[j];
i++;
bq++;
}
while((a[i]>=t)&&(i<j)){
bq++;
i++;
}
if(i<j){
a[j]=a[i];
j--;
bq++;
}
}
a[i]=t;
if(left<i-1) quicksort(a,left,i-1);
if(right>i+1) quicksort(a,i+1,right);
return bq;
}
//////////////////直接选择排序
int selectsort(int a[],int n){
int t,b=0;
int i,j,k;
for (i=0;i<n;i++)
{
k=i;
for (j=i+1;j<n;j++){
if(a[j]>a[k]) k=j;
b++;
}
if(k!=i){
t=a[i];
a[i]=a[k];
a[k]=t;
}
b++;
}
return b;
}
///////////////////堆排序
void heapadjust(int a[],int i,int n,int *bh){
int child;
int t;
for (t=a[i];2*i+1<n;i=child)
{
(*bh)++;
child=2*i+1;
if(child<n-1&&a[child+1]<a[child])
child++;
if(t>a[child]) a[i]=a[child];
else break;
a[child]=t;
}
}
int heapsort(int a[],int n){
int i;
int bh=0;
for(i=n/2-1;i>=0;i--)
heapadjust(a,i,n,&bh);
for(i=n-1;i>0;i--){
int t=a[0];
a[0]=a[i];
a[i]=t;
bh++;
heapadjust(a,0,i,&bh);
}
return bh;
}
///////////////////归并排序...稳定
void merge(int a[],int left,int mid,int right,int *bm){
int *s=new int [right+1];
int i=left;
int j=mid+1;
int k=left;
while(i<=mid&&j<=right){
if(a[i]>=a[j]) s[k++]=a[i++];
else s[k++]=a[j++];
(*bm)++;
}
while(i<=mid) {s[k++]=a[i++];(*bm)++;}
while(j<=right) {s[k++]=a[j++];(*bm)++;}
for(i=left;i<=right;i++) {a[i]=s[i];(*bm)++;}
}
int mergesort(int a[],int left,int right){
static int bm=0;
if(left<right)
{
int mid=(left+right)/2;
bm++;
mergesort(a,left,mid);
bm++;
mergesort(a,mid+1,right);
bm++;
merge(a,left,mid,right,&bm);
}
return bm;
}
///////////////////基数排序...稳定
int radixsort(int a[],int n,int radixmax){
int b=0;
int i,j,k=0,m=1;
int (*t)[10]=new int [n][10];
int tr;
int order[10]={0};
while(m<=n){
for (i=0;i<n;i++){
tr=((a[i]/m)%10);
t[order[tr]][tr]=a[i];
order[tr]++;
b++;
}
for (i=0;i<10;i++){
if(order[i]!=0)
for (j=0;j<order[i];j++){
a[k]=t[j][i];
k++;
b++;
}
order[i]=0;
}
m*=10;
k=0;
}
return b;
}
///////////////////从最右向左打印
void output(int a[],int n){
int i=n;
while(i--) printf("%d ",a[i]);
putchar(10);
}
////////////////操作函数
void operate(int a[],int n){
int *r=new int [n];
int i;
double start,end;
int degree;
char ch;
printf("请选择排序算法: ");
scanf("%c",&ch);
switch(ch){
case '1':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=insertsort(r,n);
end=clock()/1000.0;
printf("直接插入排序所用时间:\t%lf s\n",end-start);
printf("直接插入排序交换次数:\t%d\n\n",degree);
break;
case '2':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=shellsort(r,n);
end=clock()/1000.0;
printf("希尔排序所用时间:\t%lf s\n",end-start);
printf("希尔排序交换次数:\t%d\n\n",degree);
break;
case '3':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=bubblesort(r,n);
end=clock()/1000.0;
printf("冒泡排序所用时间:\t%lf s\n",end-start);
printf("冒泡排序交换次数:\t%d\n\n",degree);
start=time(NULL);
break;
case '4':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=quicksort(r,0,n-1);
end=clock()/1000.0;
printf("快速排序所用时间:\t%lf s\n",end-start);
printf("快速排序交换次数:\t%d\n\n",degree);
break;
case '5':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=selectsort(r,n);
end=clock()/1000.0;
printf("直接选择排序所用时间:\t%lf s\n",end-start);
printf("直接选择排序交换次数:\t%d\n\n",degree);
break;
case '6':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=heapsort(r,n);
end=clock()/1000.0;
printf("堆排序所用时间: %lf s\n",end-start);
printf("堆排序交换次数: %d\n\n",degree);
break;
case '7':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=mergesort(r,0,n-1);
end=clock()/1000.0;
printf("归并排序所用时间:\t%lf s\n",end-start);
printf("归并排序交换次数:\t%d\n\n",degree);
break;
case '8':
for (i=0;i<n;i++) r[i]=a[i];
start=clock()/1000.0;
degree=radixsort(r,n,10);
end=clock()/1000.0;
printf("基数排序所用时间:\t%lf s\n",end-start);
printf("基数排序交换次数:\t%d\n\n",degree);
break;
case '9':
return;
default:
printf("输入错误，请选择正确的操作！\n");
break;
}
getchar();
// output(r,n);
operate(a,n);
}
int main(){
printf("请输入要排序的个数:\t");
int n,i;
scanf("%d",&n);
getchar();
int *a=new int [n];
srand((unsigned int)time(NULL));
for(i=0;i<n;i++) a[i]=rand()%n+1;
printf("** 排序算法比较 **\n");
printf("====================================\n");
printf("== 1 --- 直接插入排序 ==\n");//插入排序
printf("== 2 --- 希尔排序 ==\n");
printf("== ==\n");
printf("== 3 --- 冒泡排序 ==\n");//交换排序
printf("== 4 --- 快速排序 ==\n");
printf("== ==\n");
printf("== 5 --- 直接选择排序 ==\n");//选择排序
printf("== 6 --- 堆排序 ==\n");
printf("== ==\n");
printf("== 7 --- 归并排序 ==\n");
printf("== ==\n");
printf("== 8 --- 基数排序 ==\n");//分配式排序
printf("== ==\n");
printf("== 9 --- 退出程序 ==\n");
printf("====================================\n");
// output(a,n);
operate(a,n);
return 0;
}
