【排序算法】快速排序

1  前言

今天把排序的几个算法过一下，这节我们看一下快速排序，简单的来说就是先找位置再拆，我们看示例。

2  代码示例

/**
 * 快速排序
 * 快排主要就是先找位置再拆
 */
public static void quickSort(int[] arr, int start, int end) {
    // 递归的出口
    if (start >= end) {
        return;
    }
    // 左右的位置索引
    int leftIndex = start;
    int rightIndex = end;
    // 默认先将左侧的作为标杆，进行位置查找
    int temp = arr[leftIndex];
    // 当左右未相遇时
    while (leftIndex < rightIndex) {
        // 从右边找如果比标杆大于等于的就继续--，直到找到一个小的
        while (arr[rightIndex] >= temp && leftIndex < rightIndex) {
            rightIndex--;
        }
        // 从左边找如果比标杆小于等于的就继续++，直到找到一个大的
        while (arr[leftIndex] <= temp && leftIndex < rightIndex) {
            leftIndex++;
        }
        // 如果左右未相遇，说明左右都各找到一个了，进行两者的交换，然后继续
        if (leftIndex < rightIndex) {
            int z = arr[leftIndex];
            arr[leftIndex] = arr[rightIndex];
            arr[rightIndex] = z;
        }
    }
    /**
     * 将找到的位置和标杆的值进行交换
     */
    arr[start] = arr[leftIndex];
    arr[leftIndex] = temp;
    // 左侧进行递归
    quickSort(arr, start, rightIndex);
    // 右侧进行递归
    quickSort(arr, rightIndex+1, end);
}
public static void main(String[] args) {
    int[] arr = IntStream.generate(() -> ThreadLocalRandom.current().nextInt(10000)).limit(10000).toArray();
    System.out.println("排序前：" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(",")));
    quickSort(arr, 0, arr.length - 1);
    System.out.println("排序后：" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(",")));
}

3  小结

有写的不对的地方，欢迎指正哈。