排序算法 - 快速排序

有时候发现越写代码越麻木了，很多代码都copy，不深究。
难道就这样甘愿当一辈子码农？

所以最近又拾起了看书的习惯了，先看看算法吧。

冒泡那些就不说了，这里主要描述一下快速排序。

快速排序简单说就是选一个基数作比较，小的在左边，大的在右边，然后两边在按照相同的办法进行排序。

这是一种分治法，大事化小，小事再化小。当最后分解为三个数/两个数的时候，左右一分就排序完成了。
对于递归的算法，最重要的就是需要找到每个部分的相同点。
就比如快速排序，相同的地方就是，每部分都要选择基数，然后按照基数左右排序。

下面附上代码：

public static void sort(int[] data, int left, int right) {
    if(left > right)
        return;
    int tmp = data[left];                // 选择最左边数作为基数
    int l = left, r = right;             // 两边的下标
    while(l < r) {                       // 替换一轮：先替换左边，再替换右边（如果你选择最右边为基数，可以先替换右边再替换左边）
        while(l < r && tmp < data[r])    // 从右边找小于基数的下标
            r--;
        if(l < r) {
            data[l] = data[r];           // 替换左边
            l++;                         // 肯定小于基数了，所以下标移动一下，可以尝试去掉结果一样
        }
        while(l < r && tmp > data[l])    // 从左边找大于基数的下标
            l++;
        if(l < r) {
            data[r] = data[l];           // 替换右边
            r--;                         // 肯定大于基数了，所以下标移动一下，可以尝试去掉结果一样
        }
    }
    data[l] = tmp;                       // 基数
 
    // 分别排序两边
    sort(data, left, l - 1);             // 排序左边
    sort(data, l + 1, right);            // 排序右边
}

参考文章：http://blog.csdn.net/morewindows/article/details/6684558

20220614批注
没事可以刷刷算法：https://leetcode.cn/