快速排序模板

变量命名及背景

• 数组为 q
• 数组 q 左下标为 l
• 数组 q 右下标为 r
• i，j 分别为数组 q 的左右两个指针，向中间移动

模板默写思路

• 递归返回条件：当只有一个元素：即 l==r，什么都不做直接 return。用 l>=r 也可以，个人习惯问题，此处用 l>=r
• 找到分界值 x ，一般可取的值为：q[l]，q[(l+r)/2]，q[r]，便于解决边界值和方便记忆，x=q[l]
• 初始化 i，j的值，便于解决边界值问题，i=l--，j=r++，定义为数组第一个和最后一个左边的两侧
• i 和 j 向中间走，直到相遇为止，因此，第一个循环限制条件是 while(i<j){...}
• 在第一个while循环的每一次遍历里面，i不断向中间靠近，每走一步，如果元素q[i]小于临界值x则可以继续走，直到不满足这个条件为止。于是可以简写为：while(q[++i]<x)。j同理，只不过从右边往中间，所以简写为：while(q[--j]>x)

• 当i和j都停下来，则检查是否相交，不相交(i<j)就交换 q[i] 和 q[j];

  • 注：这时候如果i和j都停下来，但是不满足 i<j 表示相交了，什么都不要做，因为接下来就是退出循环，进行快排左边和快排右边。也就是此时肯定是相交，同时不满足第一个循环的条件while(i<j){...}，退出循环
• 递归执行排序左边和右边

模板

public class QuickSort785 {

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

    private static void quickSort(int[] q, int l, int r) {
        if (l >= r) {
            return;
        }
        // 第1步，找x，设定i和j，注意定义i，j为两侧
        int x = q[l], i = l - 1, j = r + 1;
        while (i < j) { // 每一次循环，代表i与j暂停，交换后!i和j继续左走和右走
            // 第2步，以x为标准分隔，走左右两边
            while(q[++i] < x){}
            while(q[--j] > x){}
            // 第3步，两个指针还没有相遇，交换，没有交换，（如果i与j相遇了，就不能交换了，交换就出问题!）
            if (i < j) {
                swap(q,i,j);
            }else {
                // 这里代表相遇，相遇则不会有下个循环，本次结束
            }
        }
        // 第4步，递归排左和右
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
    public static void swap(int[] q, int a, int b) {
        int t = q[a];
        q[a] = q[b];
        q[b] = t;
    }
}