重温数据结构-归并排序、快速排序

上一篇介绍了常见的3种排序，这3种排序一般只用于理论学习，在实际的工作中不会用到，因为平均时间复杂度比较高都达到了O(n^2)，今天我会介绍下数据结构考试必考和日常工作中也会经常用到的快速排序和归并排序。

归并排序

归并排序的思想是如果要排序一个数组，需要把数组分为两部分，然后对两部分分别排序，再将排好序的两部分合并在一起。归并排序其实是分为两个步骤，先进行待排数据分解再对最小级进行排序，再进行合并。

归并排序其实就是一种分治思想，分治思想一般都是利用递归来解决问题。下面我们来按照归并排序的思路来列下归并排序的递归公式：

递归递推公式：
merge_sort(p,r) = merge(merge_sort(p,q), merge_sort(q+1,r))
终止条件：
p>=r 不用再继续分解

具体的实现代码主要分为3个函数，mergeSort是总的归并排序入口函数；mergeSortC函数是归并递归函数，函数中要设定递归出口，和分治递归和最后的已排序数组合并；merge函数主要是用来对两个已排序数组进行合并，merge函数的合并算法会影像到整个归并算法的稳定性和空间复杂度。具体实现代码如下：

public void mergeSort(int[] nums){
        mergeSortC(nums, 0, nums.length-1);
    }

    private void mergeSortC(int[] nums, int p, int r){
        //递归终止条件
        if(p >= r){
            return;
        }

        //取p到r之间的中间位置q
        int q = (p + r)/2;
        //分治递归
        mergeSortC(nums, p, q);
        mergeSortC(nums, q+1, r);
        //将nums[p...q]和nums[q+1...r]合并为nums[p..r]
        merge(nums, p, q, q+1, r);
    }

    private void merge(int[] nums, int p, int q, int q1, int r){
        //初始化下标
        int i = p, j = q+1, k = 0;
        //创建一个临时排序数组
        int[] temp = new int[r-p];

        while (i<=q && j<=r){
            if(nums[i] <= nums[j]){
                temp[k++] = nums[i++];
            }else{
                temp[k++] = nums[j++];
            }
        }

        //判断哪个子数组中还有剩余数据
        int start = i, end = q;
        if(j <= r){
            start = j;
            end = r;
        }

        //将剩余的数据拷贝到临时数组temp
        while(start <= end){
            temp[k++] = nums[start++];
        }

        //将temp中的数组拷贝到nums[p...r]
        for(i=0; i<r-p; i++){
            nums[p+i] = temp[i];
        }
    }

判断归并排序是否为稳定排序的关键为merge合并算法，合并两个数组的时候是否为稳定算法，如果合并算法是稳定的那么该归并算法就是稳定的。

归并排序的平均时间复杂度为O(logn),但是归并排序的空间复杂度我们可以从实现代码看到在合并两个排序后的数组时需要临时额外申请数组存放合并排序后的数组，临时申请的空间在合并完成后就会随着函数从栈桢中退出而释放内存空间，因为同时只会有一个线程在处理函数所以这个临时空间不会超过待排数组的最大值n，所以空间复杂度为O(n).

快速排序

快速排序算法也是我们日常用的比较多的算法，快排和归并一样也是分治的思路，如果要排序数组下标从p到r之间的一组数组，我们选择p到r之间任意一个数据作为pivot分区点，遍历p到r之间的数据，将小于pivot的都放到左边，将大于pivot的数据都放到右边，将pivot放到中间这样数组p到r被分为了3部分，p到q-1之间都是小于pivot，中间是pivot。后面是q+1到r之间的是大于pivot的数据。

根据递归的思想，可以从递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有数据都有序了。

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件：
p >= r

快速排序和归并排序一样，也主要由3个函数构成，quickSort入口函数；quickSortC函数为快速排序递归算法，递归的出口为待排两个序列之间的间隔区间小于等于0，则退出递归，在排序之前需要先找出分区点pivot，这就需要一个分区函数partition，分区函数需要能够保证返回的pivot左边的数据都是小于pivot的数据，右边的数据都是大于pivot的数据。具体的快速排序的代码如下：

    //快速排序入口函数
    public void quickSort(int[] nums){
        quickSortC(nums, 0, nums.length-1);
    }
    //快速排序递归函数
    private void quickSortC(int[] nums, int p, int r){
        if(p>=r){
            return;
        }
        //对全数组进行分区，并返回pivot坐标
        int q = partition(nums, p, r);
        //对左半部分进行排序
        quickSortC(nums, p, q-1);
        //对右半部分进行排序
        quickSortC(nums, q+1, r);
    }

    public  int partition(int[] nums, int p, int r){
        //取待排序列最后一个元素为pivot中间比较值
        int pivot = nums[r];
        int i = p;
        for(int j=p;j<r;j++){
            if(nums[j]<pivot){
                //小于pivot则交换
                swap(nums, i, j);
                //i右移一位，用于下次交换
                i++;
            }
        }
        swap(nums, i, r);
        return i;
    }

    private void swap(int[] nums, int a, int b){
        int temp;
        temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

总结

归并排序的处理过程是从下到上，先处理子问题，然后再合并，而快速排序正好相反，处理过程是从上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的，时间复杂度为O（nlogn）的排序算法，但他是非原地排序算法，归并排序之所以是非原地排序是因为合并数据的时候无法做到原地执行，需要创建临时空间存放排序数据，快速排序通过利用原地交换数据实现排序。总的来说这两种排序用的场景还是比较多的，具体的实现都是通过递归来实现。