1.5 归并排序

2024-06-29 学习笔记 知识学习 0 0 6 0

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

2. 算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

  4. 重复步骤 3 直到某一指针达到序列尾；

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示

代码实现

JavaScript

实例

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

Python

实例

def mergeSort(arr):
    import math
    if(len(arr)2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

Go

实例

func mergeSort(arr []int) []int {
        length := len(arr)
        if length 2 {
                return arr
        }
        middle := length / 2
        left := arr[0:middle]
        right := arr[middle:]
        return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
        var result []int
        for len(left) != 0 && len(right) != 0 {
                if left[0] = right[0] {
                        result = append(result, left[0])
                        left = left[1:]
                } else {
                        result = append(result, right[0])
                        right = right[1:]
                }
        }

        for len(left) != 0 {
                result = append(result, left[0])
                left = left[1:]
        }

        for len(right) != 0 {
                result = append(result, right[0])
                right = right[1:]
        }

        return result
}

Java

实例

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

PHP

实例

function mergeSort($arr)
{
    $len = count($arr);
    if ($len 2) {
        return $arr;
    }
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right)
{
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left))
        $result[] = array_shift($left);

    while (count($right))
        $result[] = array_shift($right);

    return $result;
}

C

实例

int min(int x, int y) {
    return x y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg len; seg += seg) {
        for (start = 0; start len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 end1 && start2 end2)
                b[k++] = a[start1] a[start2] ? a[start1++] : a[start2++];
            while (start1 end1)
                b[k++] = a[start1++];
            while (start2 end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

递归版：

实例

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 end1 && start2 end2)
        reg[k++] = arr[start1] arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 end1)
        reg[k++] = arr[start1++];
    while (start2 end2)
        reg[k++] = arr[start2++];
    for (k = start; k end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

C++

迭代版：

实例

templatetypename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg len; seg += seg) {
        for (int start = 0; start len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 end1 && start2 end2)
                b[k++] = a[start1] a[start2] ? a[start1++] : a[start2++];
            while (start1 end1)
                b[k++] = a[start1++];
            while (start2 end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

递归版：

实例

void Merge(vectorint> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vectorint> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vectorint> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limitsint>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limitsint>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i end; i++) {
        if (LeftSubArray[idxLeft] RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vectorint> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

C#

实例

public static Listint> sort(Listint> lst) {
    if (lst.Count 1)
        return lst;
    int mid = lst.Count / 2;
    Listint> left = new Listint>();  // 定义左侧List
    Listint> right = new Listint>(); // 定义右侧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);
}
///


/// 合併兩個已經排好序的List
///
/// 左側List
/// 右側List
///
static Listint> merge(Listint> left, Listint> right) {
    Listint> temp = new Listint>();
    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;
}

Ruby

实例

def merge list
  return list if list.size 2

  pivot = list.size / 2

  # Merge
  lambda { |left, right|
    final = []
    until left.empty? or right.empty?
      final if left.first right.first; left.shift else right.shift end
    end
    final + left + right
  }.call merge(list[0...pivot]), merge(list[pivot..-1])
end

参考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/5.mergeSort.md

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
分享 收藏 点赞(0)
  1. 免费下载或者VIP会员资源能否直接商用？
    本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
  2. 提示下载完但解压或打开不了？
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。 若排除这种情况，可在对应资源底部留言，或联络我们。
  3. 找不到素材资源介绍文章里的示例图片？
    对于会员专享、整站源码、程序插件、网站模板、网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。
  4. 付款后无法显示下载地址或者无法查看内容？
    如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理
  5. 购买该资源后，可以退款吗？
    源码素材属于虚拟商品，具有可复制性，可传播性，一旦授予，不接受任何形式的退款、换货要求。请您在购买获取之前确认好 是您所需要的资源

评论(0)

提示：请文明发言

上一篇
1.6 快速排序
下一篇
1.4 希尔排序

相关文章

学习笔记 知识学习

本节引言： 本章给大家带来的是Android中的Menu(菜单)，而在Andro...
0 0 2
学习笔记 知识学习

本节引言： 又是一个深坑，初学者慎入...本节将从普通的单线程下载 -> 普通多...
0 0 4