数据结构-快速排序和归并排序
问题遇到的现象和发生背景
问题相关代码，请勿粘贴截图 #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define M 1000
//直接插入排序
void insertsort(int *array,int n)
{
int temp;
int i,j;
for(i=1;i<n;i++)
{
temp=array[i];
for(j=i-1;j>=0&&temp<array[j];j--)
{
array[j+1]=array[j];
}
array[j+1]=temp;
}
}
//希尔排序
void shellsort(int *array,int n, int delta)
{ int i,j,temp;
for(i=delta; i<n; i++)
{ temp=array[i];
for(j=i-delta;j>=0&&temp<array[j];j-=delta)
array[j+delta]=array[j]; // 记录后移, 查找插入位置
array[j+delta]=temp; // 插入
}
}
void shell(int *array, int n)
{
int k;
int d[]={20,15,10,5,3,1};//增量集合
for(k=0; k<6; k++) shellsort(array, n,d[k]);
}
//冒泡排序
void Bubblesort(int array[],int n)
{
int temp,i,j;
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(array[j-1]>array[j])
{
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
}
//简单选择排序
void Selectsort(int array[],int n)
{
int min,temp,i,j;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(array[j]<array[min])
{
min=j;
}
}
temp=array[i];
array[i]=array[min];
array[min]=temp;
}
}
//快速排序
void quicksort(int array[],int start , int end)
{ int i , j; int mid;
if (start>=end) return;
i=start;j=end;mid=array[i];
while (i<j)
{ while (i<j && array[j]>mid) j--;
if (i<j) {array[i]=array[j]; i++; }
while (i<j && array[i]<=mid) i++;
if (i<j) {array[j]=array[i]; j--; } } //一次划分得到基准值的正确位置
array[i]=mid;
quicksort(array,start,i-1); //递归调用左子区间
quicksort(array,i+1,end); }//递归调用右子区间
//大根堆进行调整
void adjustHeap(int param1, int j, int inNums[])
{
int k;
int temp=inNums[param1];
for (k=param1*2+1;k<j;k=k*2+1)
{
//如果右边值大于左边值，指向右边
if (k+1<j && inNums[k]< inNums[k+1])
{
k++;
}
//如果子节点大于父节点，将子节点值赋给父节点,并以新的子节点作为父节点（不用进行交换）
if (inNums[k]>temp)
{
inNums[param1]=inNums[k];
param1=k;
}
else
break;
}
//put the value in the final position
inNums[param1]=temp;
}
//堆排序主要算法
void HeapSort(int inNums[],int nums)
{
int i,j;
//1.构建大顶堆
for (i=nums/2-1;i>=0;i--)
{
//put the value in the final position
adjustHeap(i,nums,inNums);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (j=nums-1;j>0;j--)
{
//堆顶元素和末尾元素进行交换
int temp=inNums[0];
inNums[0]=inNums[j];
inNums[j]=temp;
adjustHeap(0,j,inNums);//重新对堆进行调整
}
}
//归并排序
void Merge(int source[],int temp[], int start, int mid, int end)
{
int i = start, j=mid+1, k = start;
while(i!=mid+1 && j!=end+1)
{
if(source[i] > source[j])
temp[k++] = source[j++];
else
temp[k++] = source[i++];
}
while(i != mid+1)
temp[k++] = source[i++];
while(j != end+1)
temp[k++] = source[j++];
for(i=start; i<=end; i++)
source[i] = temp[i];
}
//内部使用递归
void MergeSort(int source[], int temp[], int start, int end)
{
int mid;
if(start < end)
{
mid = (start + end) / 2;
MergeSort(source,temp,start,mid);
MergeSort(source,temp,mid+1,end);
Merge(source,temp,start,mid,end);
}
}
void fun(int *a,int *b,int n)
{
int i;
for(i=0;i<n;i++)b[i]=a[i];
}
LARGE_INTEGER nFreq;
LARGE_INTEGER nBeginTime;
LARGE_INTEGER nEndTime;
void timestart()
{
QueryPerformanceCounter(&nBeginTime);//高精度计时器的值
}
void timestop()
{
double t;//间隔时间
QueryPerformanceCounter(&nEndTime);//高精度计时器的值
t=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;
printf("\t%0.10f seconds\n", t);
}
void WriteNumbers(char *filename,int *a,int n)//写文件
{
FILE *fp;
int i;
if((fp = fopen(filename, "wb")) == NULL)
{
printf("Can not write data file!\n");
exit(0);
}
for(i=0;i<n;i++)
fprintf(fp, "%6d", a[i]);
fclose(fp);
}
void main()
{
int a[M];int x,i;
int b[M],c[M];
srand((int)time(NULL));
for(i=0;i<M;i++)//初始化数组
{
x=rand()%M+1;
a[i]=x;
}
QueryPerformanceFrequency(&nFreq);//机器内部定时器的时钟频率
fun(a,b,M);
timestart();
insertsort(b,M);
printf("直插排序\t");
timestop();
WriteNumbers("insert.txt",b,M);
fun(a,b,M);
timestart();
shell(b,M);
printf("\n希尔排序\t");
timestop();
WriteNumbers("shell.txt",b,M);
fun(a,b,M);
timestart();
Bubblesort(b,M);
printf("\n冒泡排序\t");
timestop();
WriteNumbers("Bubble.txt",b,M);
fun(a,b,M);
timestart();
Selectsort(b,M);
printf("\n简单选择排序\t");
timestop();
WriteNumbers("Select.txt",b,M);
//有问题
fun(a,b,M);
timestart();
int n,array[1000];
quicksort(array,0,n);
printf("\n快速排序\t");
timestop();
WriteNumbers("quick.txt",b,M);
fun(a,b,M);
timestart();
HeapSort(b,M);
printf("\n堆排序\t\t");
timestop();
WriteNumbers("Heap.txt",b,M);
//有问题
fun(a,b,M);
timestart();
int source[1000];
MergeSort(source,source,b,M);
printf("\n归并排序\t");
timestop();
WriteNumbers("Merge.txt",b,M);
getch();
}
运行结果及报错内容
主函数那里对快速排序和归并排序的调用可怎么调用？搞了半天总是报错
快速排序倒是可以运行，但是文件里的那些数都是乱的，根本没有排好
