归并排序

归并排序的时间复杂度事O(nlogn)，是稳定排序

//算法思想：将数组一分为二，先将左边排序，再将右边排序，最后合并两边即变成有序的了
//然后左右两边的数组执行同样的操作即可
func mergeSort(nums []int) []int {
    //递归终止条件
    //一直分 最后长度等于1的时候 这时候只有一个数
    if len(nums)==1 {
        return nums
    }
    mid := len(nums)/2
    //左边排序
    left := mergeSort(nums[:mid])
    //右边排序
    right := mergeSort(nums[mid:])
    //合并
    result := merge(left, right)
    return result
}

//合并两段数据 将两个数组的数据合并到一个数组中 变成有序
func merge(left, right []int) (result []int) {
    //使用两个指针 分别指向两个数组 
    l, r := 0, 0
    //两个指针不能越界即可
    for l < len(left) && r < len(right) {
    	//移动指针，数值小的加入到结果中
        if left[l] > right[r] {
            result = append(result, right[r])
            r++
        }else {
            result = append(result, left[l])
            l++
        }
    }
    //最后如果还有元素多余，加入到结果中
    result = append(result, left[l:]...)
    result = append(result, right[r:]...)
    return 
}

CPP 实现

//算法思想：将数组一分为二，先将左边排序，再将右边排序，最后合并两边即变成有序的了
//然后左右两边的数组执行同样的操作即可
class Solution {
public:
    // 用一个新的数组接收有序的值
    vector<int> tmp;
    vector<int> sortArray(vector<int>& nums) {
        if(nums.size() == 0) return nums;
        // 设置长度，初始化为0
        tmp.resize(nums.size(), 0);
        // 归并排序
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void mergeSort(vector<int>& nums, int left, int right) {
        // 长度小于等于1 说明只有一个元素，有序
        if (left >= right) return;
		// 将数组一分为二，先将左边排序，再将右边排序
        int mid = left + right >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
		// 用一个新的数组接收有序的值
        int k = 0, i = left, j = mid + 1;
        // 合并两个 有序数组   一个是 [left, mid]  一个是 [mid + 1, right]
        // 之所以是有序的，是因为是递归，所以两个排序，四个排序，八个排序(合并)
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) tmp[k ++] = nums[i ++];
            else tmp[k ++] = nums[j ++];
        }
        // 将剩余的元素加入到tmp中
        while (i <= mid) tmp[k ++] = nums[i ++];
        while (j <= right) tmp[k ++] = nums[j ++];
		// 最后将 tmp保存的内容 复制到 nums数组
        for (i = left, j = 0; i <= right; i ++, j ++ ) nums[i] = tmp[j];
    }

};