排序算法-归并排序

Merge Sort

时间复杂度O(nlogn)

最好情况O(nlogn)

最坏情况O(nlogn)

空间复杂度O(n)

Out-place

---

归并排序利用了分治法的思想，先将数组划分为两两一组的数对，对数对进行排序，放到原来数组的位置，再把数对合并成4个数的小数组，进行排序...以此类推

由于从上一步合并而来的数组前半部分和后半部分都是有序的，所以我们需要两个指针移动选取两个数组中最小的元素，赋给新开辟的数据结构，再将有序的数据结构赋给原数组。

所以空间复杂度为O(n)

 

---

 Java:

import java.util.Arrays;

public class MergeSort {
    public static void MergeSort(int[] a){
        int [] tem = new int[a.length];
        MergeSort(a,0,a.length-1,tem);

    }

    public static void MergeSort(int[] a,int left,int right,int[] tem){
        if(left=a[j]){
                tem[t++] = a[j++];
            }else {
                tem[t++] = a[i++];
            }
        }
        while (i<=mid){
            tem[t++] = a[i++];
        }
        while (j<=right){
            tem[t++] = a[j++];
        }
        t = 0;
        while (left<=right){
            a[left++] = tem[t++];
        }
    }
}

Python: 

def MergeSort(num_list,left,right,tem):
    if left=num_list[j]:
            tem[t] = num_list[j]
            t += 1
            j += 1
        else:
            tem[t] = num_list[i]
            t += 1
            i += 1
    while i<=mid:
        tem[t] = num_list[i]
        t += 1
        i += 1
    while j<=right:
        tem[t] = num_list[j]
        t += 1
        j += 1
    t = 0
    while left<=right:
        num_list[left] = tem[t]
        left += 1
        t += 1

def main():
    num_list = [10, 9, 56, 19, 28, 37, 34]
    num_list2 = [5,4,3,1,2]
    tem = [0]*len(num_list)
    MergeSort(num_list,0,len(num_list)-1,tem)
    print(num_list)


if __name__ == "__main__":
    main()