快速排序 Java实现

快速排序是一种常用的排序算法，也是一种原地排序算法。下面是快速排序的Java实现：

public class QuickSort {
    public void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            // 将数组分区，并获取分区点的索引
            int pivotIndex = partition(arr, start, end);
            // 对分区点左边的子数组进行快速排序
            quickSort(arr, start, pivotIndex - 1);
            // 对分区点右边的子数组进行快速排序
            quickSort(arr, pivotIndex + 1, end);
        }
    }

    private int partition(int[] arr, int start, int end) {
        // 选择最后一个元素作为分区点
        int pivot = arr[end];
        int i = start;
        for (int j = start; j < end; j++) {
            if (arr[j] < pivot) {
                // 将比分区点小的元素交换到左边
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        // 将分区点放到正确的位置上
        int temp = arr[i];
        arr[i] = arr[end];
        arr[end] = temp;
        return i;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 9, 1, 3};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

以上代码中，quickSort方法实现了快速排序算法，partition方法用来将数组分成两个部分，并返回分区点的索引。在quickSort方法中，我们首先选择一个分区点（通常选择最后一个元素），然后遍历数组，将小于分区点的元素交换到左边，大于分区点的元素交换到右边。最后，将分区点放到正确的位置上，这样数组就被分成了两个部分。然后，对两个部分分别进行递归调用quickSort方法，直到子数组的长度为1或0，此时排序完成