C语言快速排序输入n(1<=n<=100),输入n个整数,按升序排序规则,输出以首个元素作为基准元素的第一次分区处理结果(占一行,元素用一个空格隔开),利用递归方法实现快速排序后的升序序列(占一行,元素用一个空格隔开)。
时间: 2024-09-26 21:09:41 浏览: 36
在C语言中,快速排序是一种高效的排序算法,通过分治策略实现。对于输入的n个整数,快速排序的基本步骤是选择一个基准值(这里通常选择第一个元素),然后将数组分为两个部分,一部分的所有元素都小于基准,另一部分所有元素都大于或等于基准。这是通过一趟划分操作完成的。
以下是`partition`函数的实现,它返回基准值的索引,将数组划分为两部分:
```c
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 将第一个元素作为基准
int i = low, j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j]; // 小于基准的移到左侧
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i]; // 大于基准的移到右侧
}
}
arr[i] = pivot; // 将基准放在正确的位置
return i;
}
```
接着,我们有`quick_sort`函数,它是递归实现的,用于对整个数组进行排序:
```c
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 分区并得到基准索引
quick_sort(arr, low, pi - 1); // 对左侧部分递归排序
quick_sort(arr, pi + 1, high); // 对右侧部分递归排序
}
}
```
为了输出首次分区处理结果和最终排序结果,可以在主函数中添加适当的打印:
```c
int main() {
int n, i;
printf("Enter number of elements (1 <= n <= 100): ");
scanf("%d", &n);
int arr[n];
printf("Enter %d numbers in ascending order:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, n - 1);
// 输出首趟分区结果
printf("First partition result (ascending): ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 输出排序后结果
printf("Sorted sequence (ascending): ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
运行上面的程序,它会接受输入的数字,进行快速排序,并展示首次分区结果及排序后的顺序。
阅读全文