输入n个数,用任意算法对其进行排序并按从小到大顺序输出
时间: 2024-09-15 14:03:45 浏览: 19
要对一组数值进行排序,有许多不同的算法可以选择,包括插入排序、选择排序、冒泡排序、快速排序、归并排序等。这里我会介绍一种经典的排序算法——快速排序,它的平均时间复杂度较低,适合处理大规模数据。
**快速排序(Quick Sort)步骤**:
1. **选择基准值**:通常选择第一个元素或最后一个元素作为基准值 (pivot)。
2. **划分**:比较数组中的每个元素与基准值,小于基准值的放在其左边,大于基准值的放在其右边。
3. **递归**:对左右两个子数组重复上述过程,直到所有元素都有序。
4. **合并**:最终得到的两个有序子数组合并成一个有序数组。
以下是使用Java实现快速排序的基本代码:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 分区操作
int pivotIndex = partition(arr, low, high);
// 对子数组递归调用
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivotValue = arr[high]; // 基准值
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivotValue) {
i++; // 将小于的元素移到左侧
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // 将基准值放到正确的位置
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试示例
public static void main(String[] args) {
int[] numbers = {9, 7, 5, 11, 12, 2, 14, 3, 10};
quickSort(numbers, 0, numbers.length - 1);
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
```
运行这个程序,你会看到输入数组按照从小到大的顺序被打印出来。