1、归并排序的原理

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

归并排序.jpg

 public static void mergeSort(int[] list){
        if(list.length>1){
            int firstHalfLength = list.length/2;
            int[] firstHalf = new int[firstHalfLength];
            System.arraycopy(list,0,firstHalf,0,firstHalfLength);
            //递归找到只含一个元素为止
            mergeSort(firstHalf);
            int[] secondHalf = new int[list.length-firstHaldLength];
            System.arraycopy(list,firstHalfLength,secondHalf,0,secondHalf.length);
            mergeSort(secondHalf);
            //执行排序
            merge(firstHalf,secondHalf,list);
        }
    }

    public static void merge(int[] firstHalf,int[] secondHalf,int[] temp){
        int count1 = 0;
        int count2 = 0;
        int count3 = 0;
        while(count1<firstHalf.length && count2<secondHalf.length){
            if(firstHalf[count1]<secondHalf[count2]){
                temp[count3++] = firstHalf[count1++];
            }else{
                temp[count3++] = secondHalf[count2++];
            }
        }
        while(count1<firstHalf.length){
            temp[count3++] = firstHalf[count1++];
        }
        while(count2<secondHalf.length){
            temp[count3++] = secondHalf[count2++];
        }
    }

上面代码有点不好理解，可以粘到自己的idea里面，debug一下，就明白了。

归并排序的性能分析

1.1、归并排序是稳定的排序算法吗？

在merge()中，将两个有序数组合并成一个有序数组的过程中，如果两个数组有相同的元素，先把第一个数组中的元素放入temp数组中。这样就保证了相同的元素，在合并前后的顺序不变。所以归并排序是一个稳定的排序算法。

1.2、归并排序的时间复杂度是多少？

一个问题分解为两个子问题，每个子问题的规模都是原来的1/2，合并两个子问题时，最多执行n-1次比较和n次赋值。所以时间复杂度可表示为

T(n) = 2T(n/2)+2n-1

由master定理可只，其时间复杂度为O(nlogn)。

1.3、归并排序的空间复杂度是多少？

归并排序，在合并时，需要借助额外的存储空间。尽管每次合并，都需要申请额外的空间，但合并完成以后，临时开辟的空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时空间在使用，所以其空间复杂度是O（n）。

2、快速排序的原理

如果要排序数组中下标从p到r的一组数据，选择任意一个元素作为分区点pivot。遍历数组，比pivot小的元素放左边，大的元素放右边，将pivot放中间。

快排.jpg

快速排序的核心代码在于如何分区，如下图，将最后一个元素作为pivot，定义两个指针i、j，把比pivot小的元素放在i的左边，j用来遍历数组。

快排分区.jpg

public static void quickSort(int[] list,int p,int r){
        if(p>=r){
            return;
        }
        int i = p;
        int j = p;
        int pivot = list[r];
        for(;j<r;j++){
            if(list[i]<pivot){
                int temp = list[i];
                list[i] = list[j];
                list[j] = temp;
                i++;
            }
        }
        int temp = list[r];
        list[r] = list[i];
        list[i] = temp;
        quickSort(list,p,i-1);
        quickSort(list,i+1,r);
    }

因为分区的过程涉及数据交换，如果数组中有两个相同的元素，比如序列6879634，在经过第一次分区之后，两个6的位置就已经互换，所以快速排序并不是一个稳定的算法。

快速排序的性能分析

如果每次分区，都能把数组分成大小相等的两个区间，则快排的时间复杂度也是O（nlogn）。但是如果原数组是有序的，需要进行n次分区操作，每次分区扫描n-1个元素，时间复杂度退化为O（n²）。这里直接给结论，快速排序在大部分情况下的时间复杂度为O（nlogn），只有在极端情况下，才会退化为O（n²）。

3、如何用快排思想在O(n)内查找第K大元素？

我们选择数组区间a[0....n-1]的最后一个元素作为pivot，对数组进行分区a[0....p-1]、a[p]、a[p+1.....n-1]。如果K = p+1，那么a[p]就是要找的元素；如果K < p+1,则要找元素在第一个区间内；如果K>p+1，则在最后的区间内。
第一次分区，遍历了n个元素；第二次分区，遍历n/2个元素；第三次分区，遍历n/4个元素......时间复杂度就是：n+n/2+n/4+.....+1 = 2n-1。