首页java quick_随手编程---快速排序(QuickSort)-Java实现

java quick_随手编程---快速排序(QuickSort)-Java实现

时间: 2023-07-11 22:06:44 浏览: 142

快速排序（QuickSort）是一种高效的排序算法，它的平均时间复杂度为O(nlogn)。它是通过将待排序数组分成两部分，其中一部分的所有元素都比另一部分的所有元素小，然后对这两部分分别进行递归排序，最终将整个数组排序。以下是Java实现的快速排序代码： ```java public class QuickSort { public static void quickSort(int[] arr, int start, int end) { if (start < end) { int pivot = partition(arr, start, end); quickSort(arr, start, pivot - 1); quickSort(arr, pivot + 1, end); } } private static int partition(int[] arr, int start, int end) { int pivot = arr[end]; int i = start - 1; for (int j = start; j < end; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, end); 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[] arr = {5, 3, 8, 4, 2, 7, 1, 10}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + " "); } } } ``` 在这个实现中，我们使用了递归来进行快速排序。首先，我们将数组分成两部分，然后对这两部分分别进行递归排序。在partition函数中，我们选择了数组的最后一个元素作为枢轴（pivot），并通过比较其他元素和枢轴的大小进行交换，将比枢轴小的元素放在枢轴的左边，比枢轴大的元素放在枢轴的右边。最后，我们将枢轴放在数组的正确位置上，并返回该位置。在这个实现中，我们使用了swap函数来交换数组中的元素。我们也可以使用Java自带的Arrays.sort()函数来进行快速排序，它的实现也是基于快速排序算法。

阅读全文