生成一组无序关键字，用C语言输出快速排序过程中消耗的额外空间

Question

生成一组无序关键字，用C语言输出快速排序过程中消耗的额外空间

Answer 1

解答如下

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define   N 200000
#define MAX 1000 
int t[N];
int count=0; 
int Ysort(int arr[],int n)//检测排序完成 
{
    int i=0;
    while(i<n-1)
    {
        if(arr[i]>arr[i+1])
            return 78;
        i++;
    }
    return 89;
}
void prin(int t[],int begin,int end)
{
    while(begin<=end)
        printf(" %d ",t[begin++]);
    printf("\n");
}
void QuickSort(int t[],int Begin,int End)//快速排序 
{
    if(Begin>=End) return;
        count+=End-Begin;
    int Left=Begin,Right=End;
    int tem=t[Begin];
    while(Begin<End)
    {
        while(Begin<End&&t[End]>=tem)
        {
            End--;
        }
        t[Begin]=t[End];
        while(Begin<End&&t[Begin]<=tem)
        {
            Begin++;
        }
        t[End]=t[Begin];
    }
    t[Begin]=tem;

    QuickSort(t,Left,Begin-1);
    QuickSort(t,Begin+1,Right);
}
int main()
{
    int i;
    int n=N;
    int max=MAX;
    printf("Size:%d\n",n);
    printf("Max :%d\n",max);
    for( i = 0; i < N; i++)
    {
        t[i] = rand()%MAX;
    }
    printf("%c  \n",Ysort(t,n));
    int begintime,endtime;
    begintime=clock();
    QuickSort(t,0,n-1);
    endtime = clock();
    printf("\n\nSort Running Time：%dms\n", endtime-begintime);
    printf("This is QuickSort.\n"); 
    
    printf("%c  \n",Ysort(t,n));
    
    printf("消耗内存：%.3lf MB\n",(double)sizeof(int)*count/1048576);
    return 0;
}