快速排序

快速排序 是随机选中其中一个元素，进行元素筛选 一遍一遍将小于这个元素的放在左边，把大于元素的放在右边

之后两边再分别随机选择出来一个而元素继续上述操作

• 选出对比元素，可以固定可以随机 可能会影响效率
• 小的放在左边，大的放在右边
• 持续递归
• 拼接返回

动态图

理解实例

简易方便理解版本的快排

利用集合来演示快排

这个效率不会很好，但是很适合我们来理解快速排序的思路

    public static ArrayList<Integer> quickSort(ArrayList<Integer> arr) {
        if (arr == null || arr.size() <= 1) {
            return arr;
        }
        int leader = arr.get(0);
        //存放左右的结果
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        for (int i = 1; i < arr.size(); i++) {
            //根据左右条件添加
            if (arr.get(i) <= leader) {
                left.add(arr.get(i));
            } else {
                right.add(arr.get(i));
            }
        }
        //递归
        ArrayList<Integer> leftResult = quickSort(left);
        ArrayList<Integer> rightResult = quickSort(right);
        //    合并
        ArrayList<Integer> result = new ArrayList<>();
        result.addAll(leftResult);
        result.add(leader);
        result.addAll(rightResult);
        return result;
    }

标准版本

标准版的思路和简易版本有一定区别

这里是有两个指针一个指向前面 一个指向后面。根据选出的值来从右往左找小于这个数的值移动，之后从左边找大于值的数移动到右边，每一次交换两个数分别放在左右两边，直到左右指针相遇 就将这个数值放在相遇点，直到有序为止。

图解

重复这个过程一直到有序为止，

我们只需要编写一个定位方法，第一次就按照上图来讲low位置的左右两边交换好

之后只需要出去中位，左右递归就可以排序好数列了，至此百万数字秒级排序的快速排序思路完成

代码实现

package com.hyc.algorithm.sort;

import java.util.ArrayList;

/**
 * @projectName: DataStructure
 * @package: com.hyc.algorithm.sort
 * @className: QuickSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/4/3 23:30
 * @version: 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        //ArrayList<Integer> arr = new ArrayList<>();
        //arr.add(3);
        //arr.add(1);
        //arr.add(9);
        //arr.add(2);
        //arr.add(6);
        //arr.add(8);
        //arr.add(7);
        //arr.add(5);
        //System.out.println(quickSort(arr));
        //int[] arr = {3, 1, 9, 2, 6, 8, 7, 5};
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        quickSort(test);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
    }


    //简易版本
    public static ArrayList<Integer> quickSort(ArrayList<Integer> arr) {
        if (arr == null || arr.size() <= 1) {
            return arr;
        }
        int leader = arr.get(0);
        //存放左右的结果
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) <= leader) {
                left.add(arr.get(i));
            } else {
                right.add(arr.get(i));
            }
        }
        //递归
        ArrayList<Integer> leftResult = quickSort(left);
        ArrayList<Integer> rightResult = quickSort(right);
        //    合并
        ArrayList<Integer> result = new ArrayList<>();
        result.addAll(leftResult);
        result.add(leader);
        result.addAll(rightResult);
        return result;
    }


    //标准版快速排序
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        //已经交换过一次 中间值的为止不会变化了
        int partPoint = partition(arr, low, high);
        //递归左边
        quickSort(arr, low, partPoint - 1);
        //递归右边
        quickSort(arr, partPoint + 1, high);
    }

    //进行一次左右换位
    public static int partition(int[] arr, int low, int high) {
        int leader = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= leader) {
                //从右边寻找第一个小于leader的数字
                high--;
            }
            //    交换值
            arr[low] = arr[high];

            while (low < high && arr[low] <= leader) {
                //从左边找到第一个大于leader的数字
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = leader;
        return low;
    }
}

效率版

思路和标准版一致

//速度优化之后的快速排序
public static void optimizeQuickSort(int[] arr, int low, int high) {
    int l = low;
    int r = high;
    int pivot = arr[l + r / 2];
    int temp = 0;
    while (l < r) {
        while (arr[l] < pivot) {
            l += 1;
        }
        while (arr[r] > pivot) {
            r -= 1;
        }
        if (l >= r) {
            break;
        }

        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        if (arr[l] == pivot) {
            r -= 1;
        }
        if (arr[r] == pivot) {
            l += 1;
        }
    }
    //防止栈溢出
    if (l == r) {
        l += 1;
        r -= 1;
    }

    //防止栈溢出，当low指针0 r = 0 的时候就不许要排序递归左边了，
    if (low < r) {
        quickSort(arr, low, r);
    }
    //当 高位大于 左边指针的时候 就需要向右边递归了
    if (high > l) {
        quickSort(arr, l, high);
    }
}