重学数据结构和算法(五)之归并排序、快速排序

最近学习了极客时间的《数据结构与算法之美》很有收获,记录总结一下。
欢迎学习老师的专栏:数据结构与算法之美
代码地址://github.com/peiniwan/Arithmetic

归并排序(Merge Sort)

冒泡排序、插入排序、选择排序这三种排序算法,它们的时间复杂度都是 O(n2),比较高,适合小规模数据的排序。归并排序和快速排序的时间复杂度为 O(nlogn) 。这两种排序算法适合大规模的数据排序

稳定,但是,归并排序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。
这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。

归并排序的原理:分治法

归并排序和快速排序都用到了分治思想,非常巧妙。我们可以借鉴这个思想,来解决非排序的问题,比如:如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素?

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。
分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

分治思想跟我们前面讲的递归思想很像。是的,分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突

如何用递归代码来实现归并排序

写递归代码的技巧就是,分析得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。所以,要想写出归并排序的代码,我们先写出归并排序的递推公式。

递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件:
p >= r 不用再继续分解

merge_sort(p…r) 表示,给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题,merge_sort(p…q) 和 merge_sort(q+1…r),其中下标 q 等于 p 和 r 的中间位置,也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从 p 到 r 之间的数据就也排好序了。

public class MergeSort {
    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(a, left, middle);//左边归并排序,使得左子序列有序
            mergeSort(a, middle + 1, right);//右边归并排序,使得右子序列有序
            merge(a, left, middle, right);//将两个有序子数组合并操作
        }
    }

    private void merge(int[] a, int left, int middle, int right) {//left0,mid0,right1
        //在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        int[] tmpArray = new int[a.length];
        int rightStart = middle + 1;//右序列指针
        int leftStart = left;//左序列指针
        int temp = left;//临时数组指针
        //比较两个小数组相应下标位置的数组大小,小的先放进新数组
        while (left <= middle && rightStart <= right) {
            if (a[left] <= a[rightStart]) {
                //相当于tmpArray[third]=a[left];third++;left++三步合一步
                tmpArray[temp++] = a[left++];
            } else {
                tmpArray[temp++] = a[rightStart++];
            }
        }
        //如果左边还有数据需要拷贝,把左边数组剩下的拷贝到新数组
        while (left <= middle) {
            tmpArray[temp++] = a[left++];
        }
        //如果右边还有数据......
        while (rightStart <= right) {
            tmpArray[temp++] = a[rightStart++];
        }
        //将temp中的元素全部拷贝到原数组中
        while (leftStart <= right) {
            a[leftStart] = tmpArray[leftStart++];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] a = new int[]{9, 7, 6, 5, 4, 3, 2, 1};
        mergeSort.mergeSort(a, 0, a.length - 1);
        for (int n : a) {
            System.out.print(" " + n);
        }
    }
}

快速排序(Quicksort)

快排是一种原地、不稳定的排序算法。
快排利用的也是分治思想。乍看起来,它有点像归并排序,但是思路其实完全不一样。我们待会会讲两者的区别。现在,我们先来看下快排的核心思想。
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。利用分治法可将快速排序的分为三步:

  1. 在数据集之中,选择一个元素作为”基准”(pivot)。
  2. 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

快速排序和归并排序对比
归并排序的处理过程是由下到上的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法,但是它是非原地排序算法。我们前面讲过,归并之所以是非原地排序算法,主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数,可以实现原地排序,解决了归并排序占用太多内存的问题。

代码实现快速排序

public class QuickSort {

    public void quick(int[] a) {
        if (a.length > 0) {
            quickSort(a, 0, a.length - 1);
        }
    }

    /**
     * 快速排序
     * @param a
     * @param low  低位
     * @param high 高位
     */
    private void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int middle = getMiddle(a, low, high);
            //递归排比第一个基数小的数和大的数
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    /**
     *
     * @param a
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] a, int low, int high) {
        int temp = a[low];//基准元素
        while (low < high) {//第二次3,9
            while (low < high && a[high] >= temp) {
                high--;
            }
            a[low] = a[high];//将比基数小的数放到基数前面///用个数字想一下就明白了
            while (low < high && a[low] <= temp) {
                low++;
            }
            a[high] = a[low];//将比基数大的数放到基数后面
        }
        a[low] = temp;//插入到排序后正确的位置,low就是基数应该在的位置
        return low;
    }
}

O(n) 时间复杂度内求无序数组中的第 K 大元素

快排核心思想就是分治和分区,我们可以利用分区的思想,来解答开篇的问题:O(n) 时间复杂度内求无序数组中的第 K 大元素。比如,4, 2, 5, 12, 3 这样一组数据,第 3 大元素就是 4。
我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot,对数组 A[0…n-1] 原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。

如果 p+1=K,那 A[p] 就是要求解的元素;如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间,我们再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理,如果 K<p+1,那我们就在 A[0…p-1] 区间查找。

int kthLargest = leetCode.findKthLargest(new int[]{4, 2, 5, 12, 3}, 3);
//倒数
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0, right = len - 1;
        int pivot = 0;
        while (len - k != (pivot = partition(nums, left, right))) {
        //4所在的问题就是2,那就找到了
        //第k大应该在第K位,找每个数字应该在的位置,正好第0个4就是第K位,就找到了
            if (pivot < len - k) {//在后面
                left = pivot + 1;
                right = len - 1;
            } else {
                left = 0;
                right = pivot - 1;
            }
        }
        return nums[pivot];
    }
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot)
                right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot)
                left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
}

为什么上述解决思路的时间复杂度是 O(n)?
第一次分区查找,我们需要对大小为 n 的数组执行分区操作,需要遍历 n 个元素。第二次分区查找,我们只需要对大小为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。依次类推,分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。
如果我们把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1。这是一个等比数列求和,最后的和等于 2n-1。所以,上述解决思路的时间复杂度就为 O(n)。