数据结构与算法之美-归并排序

作者: 魏鹏飞 | 来源:发表于2019-10-04 15:57 被阅读0次

排序算法-堆排序
数据结构与算法--归并排序
算法与数据结构路线图
2018-06-30
数据结构与算法
数据结构与算法之美-28讲堆和堆排序
归并排序
一步一步学习数据结构和算法(二) O(nlogn) 的排序算法
排序算法6：快速排序
all

Merge Sort - 归并排序

核心：归并排序是采用分治法的一个非常典型的应用。

归并排序的分析

归并排序的思想就是先递归分解数组，再合并数组。

归并排序分解图

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取后相应指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

合并过程

先写出归并排序递推公式

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

时间复杂度

最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定

Python代码实现


"""
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

最好时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定
"""

class Sort(object):

    def mergeSort(self, alist):
        n = len(alist)

        if n <= 1:
            return alist

        mid = n // 2
        # 二分分解
        leftList = self.mergeSort(alist[:mid])
        rightList = self.mergeSort(alist[mid:])

        # 合并
        return self._merge(leftList, rightList)


    def _merge(self, leftList, rightList):
        """
        合并操作，将两个有序列表leftList和rightList合并成一个大的有序列表
        """
        l = r = 0
        tempList = []
        while l < len(leftList) and r < len(rightList):
            if leftList[l] <= rightList[r]:
                tempList.append(leftList[l])
                l += 1
            else:
                tempList.append(rightList[r])
                r += 1
            
        tempList += leftList[l:]
        tempList += rightList[r:]
        return tempList

if __name__ == "__main__":
    alist = [6, 5, 3, 1, 4, 7, 2, 4]
    print(alist)
    mergeSort = Sort()
    sortAlist = mergeSort.mergeSort(alist)
    print(sortAlist)

# 结果
[6, 5, 3, 1, 4, 7, 2, 4]
[1, 2, 3, 4, 4, 5, 6, 7]

Java代码实现

import java.util.Arrays;

public class MergeSort{

    private static void mergeSort(int[] alist, int l, int r){
        if(l == r) {
            return;
        }

        int mid = (r - l) / 2 + l;

        mergeSort(alist, l, mid);
        mergeSort(alist, mid + 1, r);

        merge(alist, l, mid, r);
    }

    private static void merge(int[] alist, int l, int mid, int r){
        int[] tempList = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if (alist[i] <= alist[j]) {
                tempList[k++] = alist[i++];
            } else {
                tempList[k++] = alist[j++];
            }
        }
        while (i <= mid) {
            tempList[k++] = alist[i++];
        }
        while (j <= r) {
            tempList[k++] = alist[j++];
        }

        //把排好序的部分复制回原数组
        for (int a : tempList) {
            alist[l++] = a;
        }

    }

    public static void main(String[] args) {
        int[] alist = {100, 5, 3, 9, 8, 7, 2, 4, 15};
        mergeSort(alist, 0, alist.length - 1);
        System.out.println(Arrays.toString(alist));
    }
}

# 结果
[2, 3, 4, 5, 7, 8, 9, 15, 100]

C++代码实现

#include <iostream>

using namespace std;

void merge(int alist[], int l, int mid, int r){
    int n = r - l + 1;
    int* tempList = new int[n];

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if (alist[i] <= alist[j]) {
            tempList[k++] = alist[i++];
        } else {
            tempList[k++] = alist[j++];
        }
    }

    while (i <= mid) {
        tempList[k++] = alist[i++];
    }

    while (j <= r) {
        tempList[k++] = alist[j++];
    }

    // 把已排序的数组复制回原数组
    for (int i = 0; i < n; i++) {
        alist[l++] = tempList[i];
    }

    delete[] tempList;

}
 
void mergeSort(int alist[], int l, int r){
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;

    // 分解
    mergeSort(alist, l, mid);
    mergeSort(alist, mid + 1, r);

    // 合并
    merge(alist, l, mid, r);
}
 
int main(){
    int alist[] = {100, 5, 3, 9, 8, 7, 2, 4, 15};
    int size = 9;
    mergeSort(alist, 0, size - 1);

    for (int i = 0; i < size; i++) {
        std::cout << alist[i] << " ";
    }

    return 0;
}

# 结果
2 3 4 5 7 8 9 15 100

Go代码实现

package main

import "fmt"

// 定义一个类
type MergeSort struct {

}

// 提供两个对外的接口
// 本质上就是对外提供两个公有方法
func (m * MergeSort)Sort(alist []int) []int {
    n := len(alist)

    if n <= 1 {
        return alist
    }
    
    mid := n / 2
    leftList := m.Sort(alist[:mid])
    rightList := m.Sort(alist[mid:])
    return m.merge(leftList, rightList)
}

func (m *MergeSort)merge(leftList []int, rightList []int) []int {
    // 合并操作，将两个有序列表leftList和rightList合并成一个大的有序列表
    l := 0
    r := 0
    // tempList := make([]int, 0)
    var tempList []int
    for l < len(leftList) && r < len(rightList) {
        if leftList[l] <= rightList[r] {
            tempList = append(tempList, leftList[l])
            l++
        } else {
            tempList = append(tempList, rightList[r])
            r++
        }
    }
        
    tempList = append(tempList, leftList[l:]...)
    tempList = append(tempList, rightList[r:]...)
    return tempList
}

func main() {
    a := []int{1, 5}
    b := []int{3, 4}
    c := append(a, b...)
    fmt.Println(c)

    alist := []int{6, 5, 3, 1, 4, 7, 2, 4}
    sort := MergeSort{}
    fmt.Println(sort.Sort(alist))
}

// 结果
[1 5 3 4]
[1 2 3 4 4 5 6 7]