用Java实现递归与分治法实现快速排序算法,输入一串以英文字符逗号隔开的数字,按升序排列法实现快速排序算法。
时间: 2024-09-26 18:18:36 浏览: 51
在Java中,我们可以使用递归和分治策略来实现快速排序算法。快速排序是一种常用的排序算法,其基本思想是选取一个基准元素,将数组分为两个部分,一部分的所有元素都小于基准,另一部分所有元素都大于基准,然后对这两部分再分别进行快速排序。
以下是Java中使用递归实现快速排序的一个简化版本,假设输入的是字符串形式的数字列表:
```java
public class QuickSort {
public static void quickSort(String[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 选择第一个元素作为基准
String pivot = arr[0];
int left = 0, right = arr.length - 1;
while (left < right) {
// 分别找到比基准小和大的下一个元素
while (left < right && compare(arr[left], pivot) <= 0) {
left++;
}
arr[left] = pivot; // 将基准放到正确的位置
while (left < right && compare(arr[right], pivot) >= 0) {
right--;
}
arr[right] = arr[right]; // 将右边找到的小于基准的元素移到左边
}
arr[left] = pivot; // 最终将基准放在正确的位置
// 递归处理左右两部分
quickSort(Arrays.copyOfRange(arr, 0, left));
quickSort(Arrays.copyOfRange(arr, left + 1, arr.length));
}
private static int compare(String a, String b) {
try {
// 尝试将字符串转换为整数并比较
int numA = Integer.parseInt(a);
int numB = Integer.parseInt(b);
return numA - numB;
} catch (NumberFormatException e) {
throw new IllegalArgumentException("Invalid number in the input: " + a);
}
}
}
// 示例用法
public static void main(String[] args) {
String numbersInput = "5,3,8,6,9,1";
String[] numbers = numbersInput.split(",");
quickSort(numbers);
for (String num : numbers) {
System.out.print(num + ", ");
}
}
```
运行上述代码,你会得到一个按升序排列的数字列表。
阅读全文