java语言实现快排
时间: 2024-09-12 17:07:43 浏览: 17
快速排序(Quick Sort)是一种高效的排序算法,其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,直到整个序列有序。以下是使用 Java 实现快速排序的基本步骤:
1. **选择基准值** (Pivot): 通常选取数组的第一个元素作为基准值。
2. **分区操作** (Partitioning): 将数组分为两个区域,左边的所有元素都小于等于基准值,右边的所有元素都大于基准值。可以使用双指针法,一个指针从左开始,另一个从右开始,找到第一个大于基准值的数放到左边,找到第一个小于等于基准值的数放到右边,交换这两个位置的数。
3. **递归排序** (Recursion): 对左右两个区域分别递归地应用上述过程,直到每个区域只剩下一个元素或为空。
4. **合并结果** (Combining Results): 当所有递归调用完成后,数组就被排序了。
以下是一个简单的 Java 快速排序示例:
```java
public class QuickSort {
public 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 int partition(int[] arr, int low, int high) {
// 选择第一个元素作为基准
int pivotValue = arr[low];
while (low < high) {
// 找到第一个大于基准的元素并将其移到左边
while (low < high && arr[high] >= pivotValue) {
high--;
}
arr[low] = arr[high];
// 找到第一个小于等于基准的元素并将其移到右边
while (low < high && arr[low] <= pivotValue) {
low++;
}
arr[high] = arr[low];
}
// 将基准值放在最终的位置
arr[low] = pivotValue;
return low;
}
// 测试函数
public static void main(String[] args) {
int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```