排序算法二

讲两种nlogn时间复杂度的排序算法，一个归并排序，一个快速排序。这两种算法都采用了分治的思想，将大问题转换为很多个小问题来处理，所以实现上一般采用递归的编程技巧。

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。假设要排序的是一个数组，先要将大数组不断嵌套的从中间位置划分为子数组，直到不能划分为止，也就是子数组只有一个元素，然后再合并子数组，合并的过程中，需要两个子数组之和大小的额外临时数组来存储合并后排序好的数组，这个额外临时数组大小最大需要大数组的大小这么大，所以归并排序不是原地排序算法，空间复杂度为O(n)。

根据上面描述的思想，对一个长度为n的数组进行排序需要的时间为T(n)=2T(n/2)+n=2(2T(n/4)+n/2)+n=4T(n/4)+2n=4(2T(n/8)+n/4)+2n=8T(n/8)+3n…=2^kT(n/2^k)+kn，这里将子数组划分到只有一个元素为止，n/2＾k=1，得出需要k=log2^n次操作，此时T(n)=nC+nlog2^n，排序过程与原始数组的有序程度无关，所以时间复杂度为nlogn。由于排序的过程中并没有交换元素，合并两个子数组当遇到相同的元素时时，可以选择每次都将第一个子数组的元素优先放到临时数组中，就可以保证相同元素在排序完后前后顺序没有更改了，所以归并排序是稳定的排序算法。

快速排序的处理过程是由上到下的，先从数组中找一个元素作为分区点，一般找数组的最后一个元素作为分区点，将数组中其余元素比它小的放该分区点的左边，比它大的元素放在分区点的右边，这样下来分区点左边的元素都比它小，分区点右边的元素都比它大，也就是说，该分区点已经放在了数组中排好序的位置了，然后再处理分区点左边和右边的两个子数组，还是同样的方法，直到子数组只有一个元素。

这里排序的过程有一些技巧在里面，如果不考虑空间消耗的话，可以遍历整个数组，将数组中比分区点大的元素放在一个子数组里，将数组中比分区点小的元素放在另外一个子数组里，然后将两个子数组和分区点合并放回原数组，这样原数组就排好序了，但是这样就需要额外的n的临时空间大小，空间复杂度就是O(n)了。

但我们可以用别的办法来实现原地排序，需要两个游标i和j，初始化时都指向数组的第一位，分区点为数组的最后一个元素，将j处的元素与分区点的元素做对比，如果j的元素比分区点的值小，就将i和j处的元素做交换，并将i和j都后移一位，如果j的元素没有比分区点的值小，就只将j后移一位，继续将j处的元素与分区点的值做对比，以此类推，直到j到达分区点的位置，这样下来i左边的元素都比分区点小，i和j之间的元素都比分区点大，但现在分区点还在数组最末尾，也就是最后j到达的位置，要将分区点移到中心位置，只要将i和j处的元素进行交换就行了，这样分区点就排到了需要排好序的正确位置了，后面再对分区点左右两边的子数组再递归做同样的处理就行了，在这个排序过程中，只需要进行比较交换操作，空间复杂度就是O(1)了，这相比归并排序就是优势。上面这个排序的过程其实和选择排序有点类似，i之前的元素是已排序区，i和j之间的元素为未排序区，每次都是从未排序区取一个比分区点小的元素，把它放在已排序区的末尾，这样理解起来是不是就容易多了？

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = nums[right];
    int i = left, j = right - 1;
    while (true) {
        while (i < right && nums[i] < pivot) {
            ++i;
        }
        while (j >= left && nums[j] > pivot) {
            --j;
        }
        if (i >= j) {
            break;
        }
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[right]);
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

但由于在快排的过程中，需要进行元素交换操作，和选择排序一样，这种排序也不是稳定的排序算法，比如要被交换的元素（原本是重复元素里面的第一个元素）被交换到另外一个相同元素之后，这样相同元素的前后顺序就被打乱了，所以使用快速排序要注意使用的场景，如果对稳定排序有要求，就不好用了。

最后一个要说的是快速排序的时间复杂度，在数组完全有序的情况下，分区点就为数组最后一个元素，第一轮排序需要遍历n-1次才能找到分区点，分区点只有左边一个子数组，右边没有值了，对子数组进行第二轮排序，需要遍历n-2次才能找到分区点，分区点也是该子数组最后一位，以此类推，总共需要遍历n-1+n-2+n-3+…1=n*(n-1)/2，算下来时间复杂度到了O(n^2)，当然这是极端情况，也是最坏时间复杂度，相当于退化为选择排序了，每次都要遍历完剩下的元素才能找到分区点真正的位置，类似于选择排序每次都要遍历完未排序区所有的元素才能找到最小值或最大值。

但是，如果每次找到的分区点都是将数组分为相等的两个子数组，和归并排序一样，再对两个子数组进行分区排序，这样分区需要的时间为T(n)=2*T(n/2)+n，算下来时间复杂度就是nlogn了，当然这是分区极其均匀的情况，所以这也跟选取的分区点有关，我们一般选取数组中最后一个元素作为分区点，但如果选取有序数组中中间一个元素作为分区点，那就是这种极其均匀的分为左右两个子数组的情况了，这里推理比较复杂，最终的结论就是，快速排序在大部分情况下都可以做到nlogn，只有在极端的情况下才会退化为n^2。

最后再总结一下，归并排序和快速排序都采用了分治的思想来解决排序的问题，将大问题转化为小问题进行处理，归并排序是由下到上，先划分子问题到不能再划分的地步，再进行合并操作，而快速排序是先分区排序，将分区点放在最终排好序的位置，然后对分区点两边的子数组再进行分区排序处理，所以快排是由上到下进行处理的。归并排序和原始数组的有序程度无关，时间复杂度都是nlogn，但是空间复杂度为O(n)，而快速排序大部分情况下的时间复杂度可以做到nlogn，但也有极端情况退化为n^2，另外归并排序是稳定的排序算法，但快排不是，只是快排可以原地排序，空间复杂度最优的情况下空间复杂度为：O(logn)；每一次都平分数组的情况。最差的情况下空间复杂度为：O(n)；退化为冒泡排序的情况。首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；，所以实际使用过程中，还是快排用的比较广泛。