归并排序

介绍

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之、

操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6,5,8,1,7,3,9,4}

初始状态：6,5,8,1,7,3,9,4

第一次归并后：{5,6},{1,8},{7,3},{4,9}

第二次归并后：{1,5,6,8}，{3,4,7,9}

第三次归并后：{1,3,4,5,6,7,8,9}

原理

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

JAVA代码

public class Merge {

    public void MergeSort(int[] arr){
        MergeSort(arr,0,arr.length-1);
    }

    public void MergeSort(int[] arr,int left,int right){
        if(left < right){
            int mid=(left+right)/2;

            //利用递归将数组分成数块
            // 左边归并排序
            MergeSort(arr,left,mid);
            //右边归并排序
            MergeSort(arr,mid+1,right);

            //创建一个临时数组用于储存值,此时相当于二叉树的后序遍历
            int[] tmp=new int[right-left+1];
            //左序列指针
            int i=left;
            //右序列指针
            int j=mid+1;
            //临时数组指针
            int t=0;
            //进行排序,排序后的值放入tmp[]中
            while (i<=mid&&j<=right){
                if (arr[i]<arr[j]) {
                    tmp[t++]=arr[i++];
                } else {
                    tmp[t++] =arr[j++];
                }
            }
            //将左序列剩下的值放入tmp中
            while (i<=mid) {
                tmp[t++]=arr[i++];
            }
            //将右序列剩下的值放入tmp中
            while (j<=right) {
                tmp[t++]=arr[j++];
            }
            //将tmp中的值放回arr中,此刻该序列已成功排序
            for (int tmpi:tmp) {
                arr[left++]=tmpi;
            }
        }
    }
}

性能分析

归并排序比较占用内存，但却是一种效率高且稳定的算法。

改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)

TimSort可以说是归并排序的终极优化版本，主要思想就是检测序列中的天然有序子段（若检测到严格降序子段则翻转序列为升序子段）。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n)，具有很强的自适应性。

注：文献 [1] 是一种改进的原地归并算法，空间复杂度为O(1)。在表格里的改进归并排序只是引入其预先判断的这一步，这样便可使传统归并排序时间复杂度降至O(n)。

快速排序

介绍

快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

操作

如　设有数列{6,5,8,1,7,3,9,4}

第一次排序 前:6,5,8,1,7,3,9,4, 排序后:4,5,3,1,6,8,9,7, 中间值是:6

第二次左序列 排序前:4,5,3,1,排序后:1,3,4,5,中间值是:3

第二次右序列 排序前:8,9,7,排序后:7,8,9,中间值是:8

第三次次排序前:4,5,排序后:4,5,中间值是:4

最后结果 1,3,4,5,6,7,8,9

原理

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 [1]

一趟快速排序的算法是:

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； [1]

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； [1]

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换； [1]

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换； [1]

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）

JAVA代码

public class Quick {
    public int[] quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
        return arr;
    }
    /**
     * 快速排序
     * @param arr 数组
     * @param left 左长度值
     * @param right 右长度
     */
    public void quickSort(int[] arr,int left,int right){
        //如果L>=R结束改序列排序
        if (left>=right){return;}
        //创建一个随机数A指针
        int A=(int)(Math.random()*(right-left))+left;
        //将A指向的数与序列最后面做交换
        swap(arr,A,right);
        int head=left;
        int end=right;
        /*
        左指针往前走,如果左指针指向的值大于中间值,
        就由右指针往左走,直到右指针指向的值小于中间值.
        交换两指针所指向的值
        以此类推循环,直到左右指针碰头
         */
        while (head!=end){
            if (arr[head]<=arr[right]){
                head++;
            }else if(arr[end]>=arr[right]){
                end--;
            }else {
                swap(arr,head,end);
            }
        }
        //将中间变量与左右指针碰头的值做交换
        swap(arr,head,right);

        //递归左序列
        quickSort(arr,left,head-1);
        //递归右序列
        quickSort(arr,head+1,right);
    }

    /**
     * 交换数组中的两个数字
     * @param arr
     * @param L
     * @param R
     */
    public void swap(int[] arr,int L,int R){
        int C;
        C=arr[L];
        arr[L]=arr[R];
        arr[R]=C;
    }

}

性能分析

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

可以证明，快速排序的平均时间复杂度是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。

从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n))。