排序算法之归并排序

算法思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法步骤

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
   重复步骤3直到某一指针超出序列尾
4. 将另一序列剩下的所有元素直接复制到合并序列尾

归并排序示例

算法复杂度

• 时间复杂度为O(nlog₂n) 这是该算法中最好、最坏和平均的时间性能。
• 空间复杂度为 O(n)

算法稳定性

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

算法实现

public void mergeSort(int[] arr,int left,int right){
        if(left >= right){
            return;
        }

        int center = (right + left)/2;
        mergeSort(arr,left,center);
        mergeSort(arr,center + 1,right);
        merge(arr,left,right,center);
    }

private void merge(int[] arr,int left,int right,int center){
        int[] tmpArr = new int[right - left + 1]; //存储排序结果
        int tmpIndex = 0;

        int start1 = left;
        int start2 = center + 1;

        while(start1 <= center && start2 <= right){
            if(arr[start1] < arr[start2]){
                tmpArr[tmpIndex++] = arr[start1++];
            }else{
                tmpArr[tmpIndex++] = arr[start2++];
            }
        }

        while(start1 <= center){
            tmpArr[tmpIndex++] = arr[start1++];
        }
        while(start2 <= right){
            tmpArr[tmpIndex++] = arr[start2++];
        }

        tmpIndex = 0;
        while(left <= right){
            arr[left++] = tmpArr[tmpIndex++];
        }
    }

参考文章

1. 八大排序算法
2. 归并排序-百度百科