归并排序与快速排序的比较

public class MergeSort {
    /**
     * 双指针移动，直到指针移动到mid或者high
     * @param a
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            //这里假如说是小于号的话，就不是稳定排序了
            //如果是小于等于号的话，就是稳定排序了
            if (a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            a[k2 + low] = temp[k2];
        }
    }

    public static void mergeSort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSort(a, low, mid);
            // 右边
            mergeSort(a, mid + 1, high);
            // 左右归并
            merge(a, low, mid, high);
            System.out.println(Arrays.toString(a));
        }

    }

    public static void main(String[] args) {
        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        mergeSort(a, 0, a.length - 1);
        System.out.println("排序结果：" + Arrays.toString(a));
    }
}

归并排序，利用的是分治思想，还有递归的思想 。采用先分后合并的思想。
时间复杂度分析：
对n个元素进行排序。分解为先对n/2，在对n/2个元素排序，最后合并的问题。
T（n） =2 T(n/2) + 2n
= 2(2T(n/4)+n)+2n= (2^k)*T(n/(2k))+2*kn
当T(n/(2^k))=T(1)
k= log2n
带入得，T(n) = Cn+nLog2n
因为最后一次是n/2和n/2的一个合并，两次加起来，循环共n次。把两个子数组，合并到临时数组，再还原到原数组中。从他的算法看，时间复杂度肯定是O(nlogn)。然后是不是稳定排序呢？当相等的两个元素分别在不同的子数组中，可以让在前面先放入temp数组中。
当然由于归并排序不是原地排序，他利用了一个临时数组，所以对于空间比较紧缺的，就用的少了。

快速排序

public class QuickSortTest {
//双指针移动，不过，和归并排序不同的是，从一头一尾开始，假设第一个是分区点。x=a[i],两个指针
//分别向中间移动。
//他来回移动数据，为什么不会覆盖掉一些数据
//因为先扣掉第一个位置。然后后面的交换，不断向前面的坑里填。左右交替比较交换。
//到最后i和j相等之后，用扣掉的元素替换掉重复的元素
    public static void quick_sort(int a[], int leftBorder, int rightBorder)
    {
        if (leftBorder < rightBorder)
        {
            int i,j,x;

            i = leftBorder;
            j = rightBorder;
            x = a[i];
            while (i < j)
            {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quick_sort(a, leftBorder, i-1); /* 递归调用 */
            quick_sort(a, i+1, r); /* 递归调用 */
        }
    }

    public static void main(String[] args){
        int[] array = {1,2,4,3};
        QuickSortTest.quick_sort(array,0,array.length-1);
        for(int i=0;i<array.length;i++){
            System.out.println(array[i]);
        }
    }
}

和归并排序相反的是，先处理大问题，分成3个小问题。然后左右两个小问题，继续递归，分解，直至小问题的长度=1.

//伪代码：
quick_sort(int[] a,l,r){
  if(l>r) return
q= patition(a,l,r)
quick_sort(a,l,q-1)
quick_sort(a,q+1,r)
}

其实也是利用的分治思想。只不过，分成3部分。一个基准值，一部分是小于基准值，一部分是大于基准值。把小于基准值的放在左边，大于基准值的放在右边。
实际上是通过左右指针交替运动，实现小于基准值的放左边，大于基准值的放右边。
还有一种思路就是：
小于基准值的从左边界开始放，往右延展，大于基准值的从右边界开始，往左延展。
不过，我这种是逐个插入，而且会用到临时数组，空间复杂度变了。
所以快排巧妙就巧妙在这个左右指针交替运动，原地排序上。
大概思路就是，在左右指针不碰撞的循环下，内嵌循环，寻找自己的坑，数据复制给前一个空位。交替找坑的一个操作。
最后左右指针碰撞，把基准值放在碰撞的地方。
如图所示：

image.png

总结

相同点：
两种算法都采用了分治和递归的思想。而且重要的步骤都采用了双指针移动的方法。
不同点：
时间复杂度，
1 归并排序，时间复杂度是O(nlogn),一次合并的时间是，最好的情况已经排序好了，但是还是要n/2次，比较操作，还有n次赋值操作。一次递归是O(n),然后整个归并的是一颗二叉树，树深度是log2n，所以总的时间复杂度是O(nlogn).
2 快速排序,时间复杂度比较复杂，因为这个和他的基准数选取有关，假如说基准数刚好是中间值，对半分的话，就是O(nlogn).假如基准数是最小的或者最大的， 那就变成O(n^2).
最好情况
在最好的情况下，每次我们进行一次分区，我们会把一个序列刚好分为几近相等的两个子序列，这个情况也我们每次递归调用的是时候也就刚好处理一半大小的子序列。这看起来其实就是一个完全二叉树，树的深度为 O(logn)，所以我们需要做 O(logn) 次嵌套调用。但是在同一层次结构的两个程序调用中，不会处理为原来数列的相同部分。因此，程序调用的每一层次结构总共全部需要 O(n) 的时间。所以这个算法在最好情况下的时间复杂度为 O(nlogn)。

最坏情况
事实上，我们总不能保证上面的理想情况。试想一下，假设每次分区后都出现子序列的长度一个为0和 1 一个为 n-1，那真是糟糕透顶。这一定会导致我们的表达式变成：
T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)
这和插入排序和选择排序的关系式真是如出一辙，所以我们的最坏情况是 O(n²)。
比方说，开始序列是1,2,3,4.
选第一个是基准数，那么，第一次递归是4个元素的比较操作，第二次递归是3个元素比较操作。共n-1次递归。假如对半分的话， 只要logn次递归。
递归深度增加。

所以我们需要选择好的基准数

1 固定基准数
上面的那种算法，就是一种固定基准数的方式。如果输入的序列是随机的，处理时间还相对比较能接受。但如果数组已经有序，用上面的方式显然非常不好，因为每次划分都只能使待排序序列长度减一。这真是糟糕透了，快排沦为冒泡排序，时间复杂度为 O(n²)。因此，使用第一个元素作为基准数是非常糟糕的，我们应该立即放弃这种想法。
2 随机基准数

这是一种相对安全的策略。由于基准数的位置是随机的，那么产生的分割也不会总是出现劣质的分割。但在数组所有数字完全相等的时候，仍然会是最坏情况。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n）。所以随机化快速排序可以对于绝大多数输入数据达到 O(nlogn) 的期望时间复杂度。
3 三数取中
我们最佳的划分是将待排序的序列氛围等长的子序列，最佳的状态我们可以使用序列中间的值，也就是第 n/2 个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为基准元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基准元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约 5% 的比较次数。

空间复杂度。

归并排序的是O(n),递归每次都要用临时数组，同一层的递归，加起来的临时数组长度和原数组长度相同。
快速排序是原地排序，是O(1)。

稳定性

归并排序可以是稳定排序，也可以是不稳定排序，具体看前面的代码。
快速排序，由于来回交换数据，假如原先相等的两个数，分别在划分的两个自区间中。那么调换之后，就不会保持原来的顺序，所以是不稳定的排序。