1-快速排序

算法思想

1. 选定分界数

1. 用于将整个区间划分为两个子区间

2. 划分区间

1. 使得右半区间中的数均 >= 分界数，左半区间中的数均 <= 分界数

3. 递归处理左右两半区域

注意事项

1. 分界数一般选取中间数，即第 m 个数
2. 分界数归于左半区间

算法细节

递归

• 结束条件：区间中仅有一个元素

记忆口诀

1. 先移动，再判断
2. 若小于，才交换

算法模板

public static void qSort(int[] q, int l, int r) {  
    if (l >= r) return;  
    int k = q[l + r >> 1];// 选取分界数
    int i = l - 1;
    int j = r + 1;
  
    // 划分区间  
    while (i < j) {
	    // i 找到第一个 >= 分界数的数（a）
        // j 找到第一个 <= 分界数的数（b）
	    // 这样才能达成划分区间的目标
	    
	    // i 为什么要找 >= 分界数的数，而不是 > 分界数的数呢
	    // 确保 小于分界数的数，可以移动至左半区域
	    // exp, [2， 1]
        do i++; while (q[i] < k);
        do j--; while (q[j] > k);
  
        if (i < j) {  
            int t = q[i];  
            q[i] = q[j];  
            q[j] = t;  
        }  
    }  
  
    // 递归处理划分后的两个区间
    qSort(q, l, j);  
    qSort(q, j + 1, r);  
}