排序算法--排序算法汇总(二)
end_1,begin_2,end_2;
begin_1=p;
end_1=q;
begin_2=q+1;
end_2=r;
j=0;
while(begin_1<=end_1&&begin_2<=end_2){
if(a[begin_1]<=a[begin_2]){
ptr[j]=a[begin_1];
begin_1++;
}
else{
ptr[j]=a[begin_2];
begin_2++;
}
j++;
}
while(begin_1<=end_1)
ptr[j++]=a[begin_1++];
while(begin_2<=end_2)
ptr[j++]=a[begin_2++];
for(i=0;i
a[p+i]=ptr[i];
free(ptr);
}
void MergeSort(int a[],int first,int last){
int mid;
if(first
mid=(first+last)/2;
MergeSort(a,first,mid);
MergeSort(a,mid+1,last);
Merge(a,first,mid,last);
}
}
//8、基数排序(LSD)
int MaxBit(int a[],int n){
int i;
int d=1;
int p=10;
for(i=0;i
while(a[i]>=p){
p*=10;
++d;
}
return d;
}
void RadixSort(int a[],int n){
int i,j,k;
int radix=1;
int d=MaxBit(a,n);
int *ptr=(int*)malloc(n*sizeof(int));
int *count=(int*)malloc(10*sizeof(int));
for(i=1;i<=d;i++){
for(j=0;j<10;j++)
count[j]=0;
for(j=0;j
k=(a[j]/radix)%10;
count[k]++;
}
for(j=1;j<10;j++)
count[j]=count[j-1]+count[j];
for(j=n-1;j>=0;j--){
k=(a[j]/radix)%10;
count[k]--;
ptr[count[k]]=a[j];
}
for(j=0;j
a[j]=ptr[j];
radix*=10;
}
free(ptr);
free(count);
}
int main(void){
int i;
int index;
clock_t first,second;
for(i=0;i
Array[i]=rand()%N;
/*printf("原始数据为：\n");
for(i=0;i
printf("%d\t",Array[i]);
printf("\n");*/
while(1){
for(i=0;i
Temp[i]=Array[i];
printf("请输入排序方法：\n");
printf("1---冒泡排序\n");
printf("2---简单插入排序\n");
printf("3---希尔排序\n");
printf("4---简单选择排序\n");
printf("5---堆排序\n");
printf("6---快速排序\n");
printf("7---归并排序\n");
printf("8---基数排序\n");
scanf("%d",&index);
if(index<1||index>8) break;
first=clock();
switch(index){
case 1: BubbleSort(Temp,N);
break;
case 2: SimpleInsertSort(Temp,N);
break;
case 3: ShellSort(Temp,N,10);
break;
case 4: SimpleSelectSort(Temp,N);
break;
case 5: HeapSort(Temp,N);
break;
case 6: QuickSort(Temp,0,N-1);
break;
case 7: MergeSort(Temp,0,N-1);
break;
default: RadixSort(Temp,N);
}
second=clock();
/*printf("排序后数据为：\n");
for(i=0;i
printf("%d\t",Temp[i]);*/
printf("排序用时：%f秒\n\n",(double)(second-first)/CLOCKS_PER_SEC);
}
return 0;
}