关于#排序算法#的问题，如何用c++解决？

Question

题目是：用大小分别为1000 2000 3000 4000 5000 6000 7000 8000 9000和10000的10个数组的排列来统计归并排序算法和快速排序算法的时间复杂性。
我尝试使用随机数生成10个数组中的数据，但是每次排列结束都会时间超限。

Answer 1

试试我这个呢,从结果看还是快排快些

你可以按照自己的需求修改测试程序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int arr1[1000];
int arr2[2000];
int arr3[3000];
int arr4[4000];
int arr5[5000];
int arr6[6000];
int arr7[7000];
int arr8[8000];
int arr9[9000];
int arr10[10000];

int brr[10000];

void init()
{
    srand((unsigned int)time(NULL));
    
    for(int i=0; i<1000; i++)
    {
        arr1[i] = rand()%100000;
    }
    for(int i=0; i<2000; i++)
    {
        arr1[i] = rand()%100000;
    }
    for(int i=0; i<1000; i++)
    {
        arr2[i] = rand()%100000;
    }
    for(int i=0; i<3000; i++)
    {
        arr3[i] = rand()%100000;
    }
    for(int i=0; i<1000; i++)
    {
        arr1[i] = rand()%100000;
    }
    for(int i=0; i<4000; i++)
    {
        arr4[i] = rand()%100000;
    }
    for(int i=0; i<5000; i++)
    {
        arr5[i] = rand()%100000;
    }
    for(int i=0; i<6000; i++)
    {
        arr6[i] = rand()%100000;
    }
    for(int i=0; i<7000; i++)
    {
        arr7[i] = rand()%100000;
    }
    for(int i=0; i<8000; i++)
    {
        arr8[i] = rand()%100000;
    }
    for(int i=0; i<9000; i++)
    {
        arr9[i] = rand()%100000;
    }
    for(int i=0; i<10000; i++)
    {
        arr10[i] = rand()%100000;
    }
}

void quickSort(int *number, int first, int last) {
    int i, j, pivot;
    int temp;
    if (first<last) {
        pivot = first;
        i = first;
        j = last;
        while (i<j) {
            while (number[i] <= number[pivot] && i<last)
                i++;
            while (number[j]>number[pivot])
                j--;
            if (i<j) {
                temp = number[i];
                number[i] = number[j];
                number[j] = temp;
            }
        }
        temp = number[pivot];
        number[pivot] = number[j];
        number[j] = temp;
        quickSort(number, first, j - 1);
        quickSort(number, j + 1, last);
    }
}

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}
void testMerge()
{
    MergeSort(arr1, brr, 0, 1000);
    MergeSort(arr2, brr, 0, 2000);
    MergeSort(arr3, brr, 0, 3000);
    MergeSort(arr4, brr, 0, 4000);
    MergeSort(arr5, brr, 0, 5000);
    MergeSort(arr6, brr, 0, 6000);
    MergeSort(arr7, brr, 0, 7000);
    MergeSort(arr8, brr, 0, 8000);
    MergeSort(arr9, brr, 0, 9000);
    MergeSort(arr10, brr, 0, 10000);
}
void testQsort()
{
    quickSort(arr1,0,1000);
    quickSort(arr2,0,2000);
    quickSort(arr3,0,3000);
    quickSort(arr4,0,4000);
    quickSort(arr5,0,5000);
    quickSort(arr6,0,6000);
    quickSort(arr7,0,7000);
    quickSort(arr8,0,8000);
    quickSort(arr9,0,9000);
    quickSort(arr10,0,10000);
}

void print()
{
    printf("\n\narr1:\n");
    for(int i=0;i<1000;i++)
        printf("arr1[%d]:%d ",i,arr1[i]);

    printf("\n\narr2:\n");
    for(int i=0;i<2000;i++)
        printf("arr2[%d]:%d ",i,arr2[i]);
        
    printf("\n\narr3:\n");
    for(int i=0;i<3000;i++)
        printf("arr3[%d]:%d ",i,arr3[i]);
        
    printf("\n\narr4:\n");    
    for(int i=0;i<4000;i++)
        printf("arr4[%d]:%d ",i,arr4[i]);
        
    printf("\n\narr5:\n");    
    for(int i=0;i<5000;i++)
        printf("arr5[%d]:%d ",i,arr5[i]);
        
    printf("\n\narr6:\n");    
    for(int i=0;i<6000;i++)
        printf("arr6%d]:%d ",i,arr6[i]);
        
    printf("\n\narr7:\n");    
    for(int i=0;i<7000;i++)
        printf("arr7[%d]:%d ",i,arr7[i]);
        
    printf("\n\narr8:\n");    
    for(int i=0;i<8000;i++)
        printf("arr8[%d]:%d ",i,arr8[i]);
        
    printf("\n\narr9:\n");    
    for(int i=0;i<9000;i++)
        printf("arr9[%d]:%d ",i,arr9[i]);
        
    printf("\n\narr10:\n");
    for(int i=0;i<10000;i++)
        printf("arr10[%d]:%d ",i,arr10[i]);
    
}

int main(void) 
{ 
    init();
    
    /*归并排序时间记录*/
    
    clock_t begin, end;
    double time_cost;
    // 开始记录
    begin = clock();
    /*这里输入待测试程序段*/
    testMerge();
    // 结束记录
    end = clock();
    time_cost = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("testMerge cost : %lf s\n", CLOCKS_PER_SEC, time_cost);
    
    
     init();

    /*快速排序时间记录*/
    
    clock_t begin1, end1;
    double time_cost1;
    // 开始记录
    begin1 = clock();
    /*这里输入待测试程序段*/
    testQsort();
    // 结束记录
    end1 = clock();
    time_cost1 = (double)(end1 - begin1) / CLOCKS_PER_SEC;
    printf("testQsort cost : %lf s\n", CLOCKS_PER_SEC, time_cost1);
    
    print();

    return 0;
}