Algorithms - Merging Sort

印象

图1 使用合并排序为一列数字进行排序的过程

思想

归并排序是典型的分治算法，它不断地将某个数组分为两个部分，分别对左子数组与右子数组进行排序，然后将两个数组合并为新的有序数组。

分析

稳定: 是
时间复杂度:
- 最优时间: O(nlog(n))
- 最坏时间: O(nlog(n))
- 平均时间: O(nlog(n))

实例代码

public static List<int> sort(List<int> lst) {

    if (lst.Count <= 1)

        return lst;

    int mid = lst.Count / 2;

    List<int> left = new List<int>();  // 定义左侧List

    List<int> right = new List<int>(); // 定义右侧List

    // 以下兩個循環把 lst 分為左右兩個 List

    for (int i = 0; i < mid; i++)

        left.Add(lst[i]);

    for (int j = mid; j < lst.Count; j++)

        right.Add(lst[j]);

    left = sort(left);

    right = sort(right);

    return merge(left, right);

}

/// <summary>

/// 合併兩個已經排好序的List

/// </summary>

/// <param name="left">左側List</param>

/// <param name="right">右側List</param>

/// <returns></returns>

static List<int> merge(List<int> left, List<int> right) {

    List<int> temp = new List<int>();

    while (left.Count > 0 && right.Count > 0) {

        if (left[0] <= right[0]) {

            temp.Add(left[0]);

            left.RemoveAt(0);

        } else {

            temp.Add(right[0]);

            right.RemoveAt(0);

        }

    }

    if (left.Count > 0) {

        for (int i = 0; i < left.Count; i++)

            temp.Add(left[i]);

    }

    if (right.Count > 0) {

        for (int i = 0; i < right.Count; i++)

            temp.Add(right[i]);

    }

    return temp;

}

参考

Wikipedia - Merge sort

巴特西

Algorithms - Merging Sort

印象

思想

分析

实例代码

推荐

参考

最新文章

热门文章