使用Java实现快速排序
时间: 2023-11-05 20:14:23 浏览: 38
快速排序是一种排序算法,它的基本思想是通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,直到整个序列有序。下面是使用Java实现快速排序的代码:
```java
public class QuickSort {
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
sort(arr, left, pivot - 1);
sort(arr, pivot + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
在这段代码中,sort方法接收一个数组、起始索引和结束索引作为参数。如果起始索引小于结束索引,则进行以下操作:
1. 选择数组最后一个元素作为基准值pivot。
2. 遍历数组,将小于基准值的元素放到左边,大于基准值的元素放到右边。
3. 将基准值放到分界点,左边的元素都小于基准值,右边的元素都大于基准值。
4. 对左边的子数组和右边的子数组分别进行递归排序。
partition方法是实现上述操作的核心代码。它接收一个数组、起始索引和结束索引作为参数,返回分界点的索引。具体实现如下:
1. 选择数组最后一个元素作为基准值pivot。
2. 初始化i为起始索引-1。
3. 遍历数组,如果当前元素小于基准值,则将i加1,并交换i和当前元素的位置。
4. 遍历结束后,将基准值放到分界点,即i+1的位置。
5. 返回分界点的索引。
最后,swap方法用于交换数组中两个元素的位置。
使用示例:
```java
int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
QuickSort.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
```