java实现快速排序(附完整源码)
时间: 2023-07-07 11:45:50 浏览: 99
java实现快速排序
下面是Java实现快速排序的完整源码:
```java
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 5, 3, 8, 4, 2, 7, 1, 6 };
System.out.println("Original array: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left + 1, j = right;
while (i <= j) {
if (arr[i] > pivot && arr[j] < pivot) {
swap(arr, i, j);
}
if (arr[i] <= pivot) {
i++;
}
if (arr[j] >= pivot) {
j--;
}
}
swap(arr, left, j);
quickSort(arr, left, j - 1);
quickSort(arr, j + 1, right);
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
代码中使用了快速排序的经典实现方法:选取一个枢轴元素pivot,将数组分成左右两部分,使得左半部分的所有元素都比pivot小,右半部分的所有元素都比pivot大。然后,对左右两部分分别递归进行快速排序。
程序首先定义了一个quickSort方法,接受一个数组和左右边界索引作为参数。然后,程序选取左边界元素作为pivot,使用两个指针i和j分别从左右两端开始遍历数组,交换不符合条件的元素位置。最后,将pivot和j所指向的元素交换位置,完成一次划分。
接下来,程序对左右两部分分别递归调用quickSort方法,直到左右边界相遇或交错。
最后,程序定义了一个swap方法,用于交换数组中两个元素的位置。
以上是Java实现快速排序的完整源码,希望能对你有所帮助。
阅读全文