njitiecHeart 2023-03-02 08:59 采纳率: 100%

# C语言数据结构的排序问题

``````#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
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
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;
}

``````
• 写回答

#### 5条回答默认 最新

• 白驹_过隙 算法领域新星创作者 2023-03-02 15:51
关注
``````
#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
void iterative_quicksort(int arr[], int low, int high) {
if (low < high)
{
int *stack = (int*)malloc(sizeof(int) * (high - low + 1));
int pointer = -1;
stack[++pointer] = low;
stack[++pointer] = high;

float ex = 0;
int left, right = 0;

while (pointer != -1)
{
right = stack[pointer--];
left = stack[pointer--];
int i = left - 1;
float pivot = arr[right];
for (int j = left; j < right; ++j)
{
if (arr[j] < pivot)
{
i++;
ex = arr[i];
arr[i] = arr[j];
arr[j] = ex;
}
}
arr[right] = arr[i + 1];
arr[i + 1] = pivot;

if (left < i)
{
stack[++pointer] = left;
stack[++pointer] = i;
}

if (i + 2 < right)
{
stack[++pointer] = i + 2;
stack[++pointer] = right;
}
}
free(stack);
}

}

//    Recursive quicksort
//    TODO!! Implement this function
void recursive_quicksort(int arr[], int low, int high) {
int left=low;int right=high;
if (left >= right)
return;

int pivot = arr[left];
int i = left, j = right;

while (i < j)
{
while (i < j && arr[j] >= pivot)
j--;
arr[i] = arr[j];

while (i < j && arr[i] < pivot)
i++;
arr[j] = arr[i];
}
arr[i] = pivot;

recursive_quicksort(arr, left, i-1);
recursive_quicksort(arr, i+1, right);

}

//    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
int find_mode_counting_sort(int *A, int len) {
int n=0;
int *arr_B = (int *)malloc(len*sizeof(int));
int *arrc = (int *)malloc(9999*sizeof(int));
for(int i=0;i<9999;i++)
{
arrc[i]=0;
}

for(int i=0;i<len;i++)
{
arrc[A[i]]+=1;
}
for(int i=1;i<9999;i++)
for(int j=0;j<arrc[i];j++)
arr_B[n++]=i;

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);

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;
}

``````
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论 编辑记录

• 系统已结题 3月10日
• 已采纳回答 3月2日
• 创建了问题 3月2日

#### 悬赏问题

• ¥15 nslt的可用模型，或者其他可以进行推理的现有模型
• ¥15 arduino上连sim900a实现连接mqtt服务器