3、排序都有哪几种方法?请列举。用JAVA实现一个快速排序。
时间: 2024-10-16 16:11:19 浏览: 7
排序算法有很多种,常见的主要有以下几种:
1. 冒泡排序(Bubble Sort)
2. 选择排序(Selection Sort)
3. 插入排序(Insertion Sort)
4. 快速排序(Quick Sort)
5. 归并排序(Merge Sort)
6. 堆排序(Heap Sort)
7. 希尔排序(Shell Sort)
8. 计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort),适用于特定类型的整数。
以下是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 pivot = arr[high]; // 最后一个元素作为基准
int i = low - 1; // 小于基准的元素指针
for (int j = low; j < high; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
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;
}
}
```
在这个例子中,`quickSort()`函数是主排序函数,`partition()`函数负责找到基准并将其放置在正确的位置,`swap()`函数用于交换数组元素。
阅读全文