实现递归快速排序。快速排序使用配分函数和交换函数。这些已经为您实现了。你的任务是实现函数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;
}
递归快排：
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;
该回答引用GPTᴼᴾᴱᴺᴬᴵ
这是一个大型的编程任务，涉及到多个函数和算法。我将逐一回答每个TODO，并提供解决方案。首先，我们将开始实现递归快速排序。
对于递归快速排序，我们需要实现一个函数，它将数组的范围（最低和最高索引）作为参数，并按升序对数组进行排序。在排序过程中，我们需要执行以下步骤：
现在，我们将实现该函数，并将其称为recursive_quicksort()。
void recursive_quicksort(int arr[], int low, int high) {
// If array length is less than or equal to 1, it is already sorted.
if (low >= high) {
return;
}
// Choose the last element as pivot
int pivot = arr[high];
// Partition the array around the pivot and get the index of the pivot
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[high]);
int pivot_index = i + 1;
// Recursively sort the left and right subarrays
recursive_quicksort(arr, low, pivot_index - 1);
recursive_quicksort(arr, pivot_index + 1, high);
}
在此函数中，我们首先检查数组长度是否小于等于1。如果是，数组已经排序。否则，我们选择数组的最后一个元素作为基准点。然后，我们按照比基准点小和比基准点大的元素重新排列数组元素。最后，我们递归地对基准点左边和右边的子数组执行相同的操作。
现在我们已经实现了递归快速排序函数。接下来，我们将实现计数排序。
计数排序是一种基于比较元素大小的排序算法，它通过统计每个元素出现的次数来实现排序。计数排序适用于元素范围不大的情况，例如对于范围在0到100之间的整数进行排序，时间复杂度可以做到线性的O(n)。
计数排序的基本思想是，对于待排序的数组arr，统计arr中每个元素出现的次数，并将结果存储在一个计数数组count中。然后遍历计数数组count，将统计的元素个数累加起来，以确定每个元素在排序后的数组中的位置。最后遍历原始数组arr，根据计数数组count中元素的值，将arr中的元素放入对应的位置上。
下面是一个Python实现的计数排序函数，你可以参考一下：
def counting_sort(arr):
# 找出数组中最大值和最小值
max_val = max(arr)
min_val = min(arr)
# 计算每个元素出现的次数
count = [0] * (max_val - min_val + 1)
for val in arr:
count[val - min_val] += 1
# 累加计数数组中的元素
for i in range(1, len(count)):
count[i] += count[i-1]
# 创建一个临时数组，存储排序后的结果
temp = [0] * len(arr)
for val in arr:
temp[count[val - min_val] - 1] = val
count[val - min_val] -= 1
return temp
这个函数接受一个待排序的数组arr作为输入，返回一个排好序的数组。其中，首先找出数组中的最大值和最小值，用于确定计数数组count的长度。然后，遍历原始数组arr，统计每个元素出现的次数，并将结果存储在计数数组count中。接下来，遍历计数数组count，累加计数数组中的元素，以确定每个元素在排序后的数组中的位置。最后，创建一个临时数组temp，将原始数组arr中的元素按照顺序放入temp中，并返回temp作为结果。
需要注意的是，计数排序只适用于元素都是非负整数的情况。如果待排序的数组包含负数或者小数，需要先将其转化为非负整数再进行排序。
参考gpt和自己的思路，以下是递归快速排序的实现。在这个函数中，我们使用partition()函数将数组划分为两个部分，一部分包含小于基准的元素，另一部分包含大于基准的元素。然后，我们对每个部分递归地调用quicksort()，直到整个数组已经排序为止。
void recursive_quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
recursive_quicksort(arr, low, pi - 1);
recursive_quicksort(arr, pi + 1, high);
}
}
接下来，我们需要实现iterative_quicksort()函数。为了实现这个函数，我们将使用栈来模拟递归快速排序的过程。我们将首先初始化栈，然后将low和high压入栈中。接下来，我们将从栈中弹出两个值，模拟对这两个值的递归快速排序调用。如果有更多的子数组需要排序，则将它们的low和high值压入栈中。这个过程将继续，直到栈为空为止。
void iterative_quicksort(int arr[], int low, int high) {
int stack[high - low + 1];
int top = -1;
stack[++top] = low;
stack[++top] = high;
while (top >= 0) {
high = stack[top--];
low = stack[top--];
int pi = partition(arr, low, high);
if (pi - 1 > low) {
stack[++top] = low;
stack[++top] = pi - 1;
}
if (pi + 1 < high) {
stack[++top] = pi + 1;
stack[++top] = high;
}
}
}
现在，我们需要实现计数排序。在这个函数中，我们首先找到输入数组的最大值，并为计数数组分配内存。然后，我们遍历输入数组，并在计数数组中增加相应的计数。接下来，我们使用这些计数值重构原始数组，以实现排序。最后，我们释放计数数组的内存
void counting_sort(int arr[], int len) {
int max = arr[0];
for (int i = 1; i < len; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int* counts = (int*)calloc(max + 1, sizeof(int));
for (int i = 0; i < len; i++) {
counts[arr[i]]++;
}
int i = 0;
for (int j = 0; j <= max; j++) {
while (counts[j] > 0) {
arr[i++] = j;
counts[j]--;
}
}
free(counts);
}
现在，我们可以在主函数中使用这些函数。我们首先生成一个随机数组，并使用计数排序对其进行排序。然后，我们对相同的数组使用递归快速排序算法进行排序。下面是示例代码：
import random
def counting_sort(arr):
k = max(arr) + 1
count = [0] * k
for i in arr:
count[i] += 1
for i in range(1, k):
count[i] += count[i - 1]
result = [0] * len(arr)
for i in arr:
result[count[i] - 1] = i
count[i] -= 1
return result
def quick_sort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
if __name__ == '__main__':
arr = [random.randint(0, 100) for _ in range(10)]
# Sort using counting sort
sorted_arr = counting_sort(arr)
print("Sorted array using counting sort: ", sorted_arr)
# Sort using quick sort
sorted_arr = quick_sort(arr)
print("Sorted array using quick sort: ", sorted_arr)
在这个示例中，我们使用Python编写了两个排序算法，一个是计数排序，另一个是递归快速排序。我们在主函数中使用这两个算法对一个随机数组进行排序，并打印出排序后的数组。你可以尝试使用不同的数组大小和不同的元素值范围来测试这些算法的效率和正确性。
不知道你这个问题是否已经解决, 如果还没有解决的话: