《图解数据结构算法》排序总结笔记

总记

排序指根据一定的规则，将所给的若干数据有序化处理，使其更方便算法处理的操作。它在各种各样的场景中出场率都很高，本文介绍两个非常常用的排序算法：归并排序和快速排序，它们都和分治思想有联系。

归并排序

要想把两个已经排序了的数组合并是很简单的，只需要使用双指针逐位比较即可；把一个数组切片油炸为一个个单独的元素，然后逐个两两合并为更大的数组，再对更大的数组两两合并，最终就可以将其排序成为有序的数组。

public void SortArr(int[] arr, int left, int right) {
    // 首先上场的选手是归并排序
    if (left >= right) return; // 左右指针挨在一起，这个子数组为空或必定有序（终止）
    int mid = (left + right) / 2;
    SortArr(arr, left, mid);
    SortArr(arr, mid + 1, right);
    // 分别排序两个分数组
    int[] mergedArr = new int[right - left + 1];
    int indexL = left;
    int indexR = mid + 1;
    int mergedIndex = 0;
    while (mergedIndex < mergedArr.Length) {
        if (indexL < mid + 1 && indexR < right + 1) {
            if (arr[indexL] <= arr[indexR]) {
                mergedArr[mergedIndex] = arr[indexL++];
            }
            else {
                mergedArr[mergedIndex] = arr[indexR++];
            }
        }
        else {
            if (indexL > mid) {
                mergedArr[mergedIndex] = arr[indexR++];
            }
            else {
                mergedArr[mergedIndex] = arr[indexL++];
            }
        }
        mergedIndex++;
    }
    for (int i = left; i <= right; i++) {
        arr[i] = mergedArr[i - left];
    }
    // 然后合并它们
}

快速排序

如果可以在数组中设置一个哨兵，让哨兵左边的元素都比它小/大，右边的都比它大/小，那么我们继续对哨兵的左右两个子数组这样操作，操作到子数组只是一个单元素，我们也就完成了对整个数组的排序。

public void SortArr(int[] arr, int left, int right) {
    // 有请快速排序选手登场
    if (left >= right) { return; } // 数组只有一个元素或者没有，那么不需继续递归
    int indexL = left;
    int indexR = right;
    int sentry = arr[left];
    int swap;
    while (indexL < indexR) {
        while (indexL < indexR && arr[indexR] >= sentry) { indexR--; }
        while (indexL < indexR && arr[indexL] <= sentry) { indexL++; }
        swap = arr[indexL]; arr[indexL] = arr[indexR]; arr[indexR] = swap;
        // 两个指针靠近，顺便保证自己身后没有比哨兵大/小的元素
    }
    // 把哨兵搬到两个指针的位置，这样保证了哨兵两边元素都比它大/小
    swap = arr[left]; arr[left] = arr[indexL]; arr[indexL] = swap;
    // 对数组进行哨兵划分
    SortArr(arr, left, indexL - 1);
    SortArr(arr, indexL + 1, right);
    // 然后继续对子数组做哨兵划分（哨兵两边的数组，不包括它本身），分治
}
/*
两个问题：
1.为什么比较指针和哨兵要用>=或<=，而不用>或<？
2.为什么左指针右移和右指针左移顺序不能互换？
解：1.如果不忽略相等情况，那么就可能L和R数值都等于哨兵，恭喜你，交换后再交换，StackOverflow，
实际上，与哨兵相等的元素无论在子数组的哪边都不影响结果，所以直接忽略没啥问题。
2.快速排序必须保证最后哨兵左边的元素小于等于之，在两个指针靠近的时候，左指针的左边都可以满足这个条件；
但是，当两个指针相撞的时候就不好说了；如果我们在循环中让左指针先走，有如下情况会发生：
左指针撞在一个大于哨兵的数上，结果右指针撞上了左指针，这个大数被交换到了哨兵左边，导致排序错误。
如果我们让右指针先走，就可以避免这个问题：左指针要么撞上更大的数，做交换，要么撞上右指针，右指针会停下来肯定是因为这个数比哨兵小，所以被交换到哨兵左边的数仍然小于哨兵，条件满足。
*/

总结

上述两个排序的核心思想都是分治，将大问题拆成简单的子问题求解。

理解上述两个排序的工作原理对我们进一步理解分治思想很有帮助。