递归与分治法实现快速排序算法,输入一串以英文字符逗号隔开的数字,按升序排列法实现快速排序算法。用c语言写出这段代码
时间: 2024-09-19 14:12:59 浏览: 56
递归与分治策略是快速排序算法的核心思想。首先,我们将字符串分割成整数数组,然后通过选择一个基准值(这里通常是第一个元素),将数组分为两部分:一部分所有元素都小于基准,另一部分所有元素都大于等于基准。接着对这两部分再分别进行同样的操作,直到每个子序列只剩下一个元素,此时整个数组就排好序了。
以下是使用C语言实现快速排序算法并处理逗号分隔的输入字符串的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 分割函数,返回分割后的两个数组指针
int* partition(char str[], int low, int high) {
char pivot = str[low];
while (low < high) {
while (str[high] > pivot && high > low) high--;
if (high >= low)
str[low++] = str[high];
while (low < high && str[low] <= pivot) low++;
if (low < high)
str[high--] = str[low];
}
str[low] = pivot;
return &str[low];
}
// 快速排序函数
void quicksort(char str[], int low, int high) {
if (low < high) {
int pi = partition(str, low, high);
quicksort(str, low, pi - 1); // 对左半部分递归排序
quicksort(str, pi + 1, high); // 对右半部分递归排序
}
}
// 处理字符串并将数字排序
void sort_string(char input[]) {
char *numbers[] = strtok(input, ",");
int n = sizeof(numbers) / sizeof(numbers[0]);
for (int i = 0; i < n; i++) {
numbers[i] = atoi(numbers[i]); // 转换为整数
}
quicksort(numbers, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d", numbers[i]);
if (i != n - 1) printf(","); // 输出逗号分隔
}
printf("\n");
}
int main() {
char input[100];
printf("请输入一串以英文字符逗号隔开的数字:");
fgets(input, sizeof(input), stdin);
sort_string(input);
return 0;
}
```
阅读全文