用C语言编写使用快速排序的随机化版本对输入的n个整数,按照从小到大的顺序排序。第一行输入一个整数n(0<n<=100000)。 第二行输入n个整数。输出排序后的n个整数,每个整数之间以一个空格分隔。注意:最后一个整数后面没有空格。
时间: 2024-03-09 20:48:32 浏览: 34
以下是使用快速排序的随机化版本对输入的n个整数进行排序的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
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[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
int randomPartition(int arr[], int low, int high) {
srand(time(NULL));
int random = low + rand() % (high - low);
swap(&arr[random], &arr[high]);
return partition(arr, low, high);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = randomPartition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
quickSort(arr, 0, n - 1);
for (int i = 0; i < n - 1; i++) {
printf("%d ", arr[i]);
}
printf("%d", arr[n - 1]);
return 0;
}
```
在这个代码中,`swap`函数用于交换两个整数的值,`partition`函数用于对数组进行分区操作,`randomPartition`函数用于随机选择分区点,`quickSort`函数用于递归地进行快速排序。在`main`函数中,首先读入输入的整数,然后读入n个整数。接着调用`quickSort`函数对数组进行排序,最后输出排序后的整数。