用C语言补充代码，能够输出所需结果

Question

实现递归快速排序。快速排序使用配分函数和交换函数。这些已经为您实现了。你的任务是实现函数r ecursive_quicksort().TODO在第48行上，该功能从第49行开始。实现是直接的，您先 已经实现了它，你可以转到find_mode_quicksort（）函数，注释出第一个快速排序调用和取消注释recursive_quicksort（）函数。接下来，实现计数排序。你可以在第96行找到TODO，这个函数从第98行开始。在这里，您将一步一步地找到如何实现该函数。注意，在这里也不需要实现查找模式的逻辑，而只需要实现计数排序部分。一旦你实现了计数s 排序后，您可以进入主函数，取消注释启动第二个时钟的块，调用计数排序函数，停止时钟，并打印结果。计数排序不会改变初始数组，因此首先调用它，然后调用快速排序是安全的。快速排序排序到位，所以它改变了顺序 初始数组本身中的元素的r。一旦实现了计数排序，请再次编译并运行代码。比较执行时间 用两种不同的方法来排序，然后找到模式。最后，实现迭代快速排序。你将在第30行找到TODO，算法从第32行开始。可以“硬编码”一个更小的数字输入数组，并包括适当的打印文件来调试您自己的解决方案。若要打印数组的内容，请不要使用大型数组。

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

//    Swap function to swap two elements of an array
//    Used by pratition
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

//    Partition used by both iterative and recursive quicksort
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[high]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return i + 1;
}

//    Iterative quicksort
//    TODO!!    Implement this function
//            Follow instructions in the comments below
void iterative_quicksort(int arr[], int low, int high) {
    //    Initialize the "stack data structure" to simulate recursive calls
    //    Note the size of the array.
    
    //    Set "top" as -1
    
    //    "Push" low and high to "stack"
    
    //    In a while loop, "Pop" two top values from s"tack" and simulate
    //    call of quicksort. If there are still subarrays to sort, their
    //    low and high values are "pushed to stack".
    //    Ends when "stack is empty"
    
}

//    Recursive quicksort
//    TODO!! Implement this function
void recursive_quicksort(int arr[], int low, int high) {
    
}

//    For library quicksort
int compare(const void *a,const void *b) {
    int x = *(int *)(a);
    int y = *(int *)(b);
    return x-y;
}

/*    Finds mode by first sorting the array with quicksort 
    NOTE!!!    Quicksort changes the original array,
            so only one quicksort function can be used at a time.
            The other function calls can be commented out.
            qsort() is the library quicksort
*/
int find_mode_quicksort(int *A, int len) {
    qsort(A,len,sizeof(int),compare);
    //iterative_quicksort(A, 0, len - 1);
    //recursive_quicksort(A, 0, len - 1);

    //    Find mode from the sorted array.
    //    You do not need to change this
    int mode = A[0];
    int freq = 1;
    int temp = 1;
    int i=1;

    while (i < len) {
        if (A[i] != A[i-1]) {
            temp = 1;
        }
        else {
            temp++;
            if (temp > freq) {
                freq = temp;
                mode = A[i];
            }
        }
        i++;
    }
    printf("\nQuicksort: Mode = %d, frequence = %d\n",mode,freq);
    return mode;
}

//    Finds mode by first sorting array with counting sort.
//    TODO!!    Implement the counting sort algorithm in this function
//            Follow the instructions in the comments
int find_mode_counting_sort(int *A, int len) {
    //    Initialize output array B equal in size of array A

    //    Initialize the temporary auxiliary array C. Note it's size

    //    Fill the temporary array C with zeros

    //    Store the count of each element into the temporary array C

    // Store the cumulative counts into array C

    //    Find the indexes of the elements of the original array
    //    and place the elements in the ouput array B

    //    Find mode from array B
    //    You do not need to change anything here
    int mode = arr_B[0];
    int freq = 1;
    int temp = 1;
    int i=1;

    while (i < len) {
        if (arr_B[i] != arr_B[i-1]) {
            temp = 1;
        }
        else {
            temp++;
            if (temp > freq) {
                freq = temp;
                mode = arr_B[i];
            }
        }
        i++;
    }
    printf("\nCounting sort: Mode = %d, frequence = %d\n",mode,freq);
    //    Free memory allocated to array B
    free(arr_B);
    return mode;
}

//    Initialize array with random numbers
//    from 0 to 999
void initialize(int *A, int len) {
    int i;
    for (i=0; i < len; i++) {
        A[i] = rand()%1000;
    }
}

int main(){
    clock_t start,end;
    int mode = 0;

    //    Reserve a large array
    int *array = (int *)malloc(100000000*sizeof(int));

    //    Seed random number generator
    //    Otherwise it produces the same sequence every time
    //    Although, same sequence could be used if you want
    //    to compare efficiency of different quicksort implementations
    int seed = time(NULL);
    srand(seed);

    double totaltime;
    int size, threshold;

    printf("Input array size > ");
    scanf("%d",&size);

    printf("\nSearching for mode... \n");
    initialize(array,size);

    /*    Uncomment this block of code when you have implemented
        the counting sort function
        
    start = clock();
    mode = find_mode_counting_sort(array,size);
    end = clock();
    totaltime = (double)(end-start)/CLOCKS_PER_SEC;
    printf("Mode:%d, Consumed time: %f seconds \n",mode,totaltime);
    */

    start = clock();
    mode = find_mode_quicksort(array,size);
    end = clock();
    totaltime = (double)(end-start)/CLOCKS_PER_SEC;
    printf("Mode:%d, Consumed time: %f seconds \n",mode,totaltime);

    // Free memory allocated to the array
    free(array);

    return 0;
}

Answer 1

递归快排：

int PartQulickSort1(int*a, int left, int right)
{
 
    int mid = GetMid(a, left, right);//取中
    Swap(&a[mid], &a[left]);//将中间的数与最左右的数交换下//swap写的交换函数
    int keyi = left;//得到基数的位置
    while (left < right)
    {
        while (left<right&&a[right] >= a[keyi])//先从右边找到较小的值
        {
            right--;
        }
        while (left<right&&a[left] <= a[keyi])//再从左边找最大的值
        {
            left++;
        }
        Swap(&a[right], &a[left]);//进行交换
    }
    Swap(&a[right], &a[keyi]);//最后将right或者left位置的值与基数交换
    return right;