快排-Java面试指南

当前位置:　首页>> 技术小册>> Java面试指南

快速排序是一种常用的排序算法，它利用分治思想将一个大的数组分成两个子数组来递归地进行排序。下面是一个使用Java实现的快速排序算法的示例代码：

java
Copy code
public class QuickSort {

public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 7, 6, 8, 1, 4};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
在这个示例代码中，我们定义了一个快速排序的静态方法quickSort，它接受一个整数数组arr以及左右两个端点left和right。

我们还定义了一个辅助方法partition来对数组进行划分操作。在quickSort方法中，我们首先进行递归退出条件的判断，即如果左端点大于等于右端点，说明当前子数组已经有序，可以直接返回。

然后我们利用partition方法对数组进行划分操作，并递归地对左右两个子数组进行排序。在partition方法中，我们选择数组的第一个元素作为枢轴元素（pivot），并维护两个指针left和right，分别从左右两端向中间扫描数组。

我们通过不断交换左右两端的元素，将小于枢轴元素的元素放在左边，大于枢轴元素的元素放在右边，最终得到划分后枢轴元素的位置，并返回该位置作为下一次递归的分界点。

运行上述代码，可以得到排序后的数组结果：1 2 3 4 5 6 7 8 9。