快速排序算法 java

提问区
,
1

以下是Java中的快速排序算法的示例实现：

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 2, 5, 1, 7, 6, 3, 8, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
    
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }
    
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];  // 以数组第一个元素作为基准
        int i = low + 1;  // 从左向右搜索大于基准的元素
        int j = high;  // 从右向左搜索小于基准的元素
        
        while (true) {
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (j >= i && arr[j] > pivot) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
        }
        
        swap(arr, low, j);  // 将基准元素放到正确的位置
        return j;  // 返回基准元素的下标
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

这段代码演示了如何使用快速排序算法对一个整数数组进行排序。快速排序的基本思想是选择一个基准元素，通过一系列交换操作，将小于基准的数放到左边，大于基准的数放到右边，然后递归地对左右两部分进行排序。最终得到一个有序数组。

在示例代码中，quickSort方法是递归函数，用于执行快速排序。partition方法用于找到基准元素的正确位置，并返回该位置的下标。swap方法用于交换数组中两个元素的位置。

需要注意的是，快速排序算法在最坏情况下的时间复杂度为 O(n^2)，但在平均情况下的时间复杂度为 O(nlogn)。为了提高性能，可以采用随机选择基准元素的方式来避免最坏情况的发生。