更多精彩内容,欢迎关注:

视频号
视频号

抖音
抖音

快手
快手

微博
微博

简述归并排序算法的基本思路

文档

简述归并排序算法的基本思路

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
推荐度:
导读归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是归并排序算法:

归并排序(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. 算法步骤

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

设定两个指针,最初位置分别为两个已经排序序列的起始位置;

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

重复步骤 3 直到某一指针达到序列尾;

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

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 resultGo 实例 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++

迭代版:

实例 template // 整數或浮點數皆可使用,若要使用物件(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(vector &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    vector LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);    vector RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);    int idxLeft = 0, idxRight = 0;    LeftSubArray.insert(LeftSubArray.end(), numeric_limits::max());    RightSubArray.insert(RightSubArray.end(), numeric_limits::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(vector &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 List sort(List lst) {    if (lst.Count <= 1)        return lst;    int mid = lst.Count / 2;    List left = new List();  // 定义左侧List    List right = new List(); // 定义右侧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 List merge(List left, List right) {    List temp = new List();    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

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

以下是热心网友对归并排序算法的补充,仅供参考:

热心网友提供的补充1:

分而治之

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

合并相邻有序子序列

再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/8.
 */
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left以上为归并排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括: 

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释:

n:数据规模

k:"桶"的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同

文档

简述归并排序算法的基本思路

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
推荐度:
为你推荐
资讯专栏
热门视频
相关推荐
希尔排序怎么排 直接选择排序 基数排序流程图 python冒泡排序算法 桶排序c语言 计数排序菜鸟教程 堆排序算法规则 描写兰花的诗句古诗 快速排序算法java 带有动物的古诗 关于踏青的唯美诗句 关于描写燕子的诗句 归并排序算法python思想 希尔排序实现 直接选择排序稳定吗 基数排序算法代码 java冒泡排序代码 桶排序算法java 计数排序c 数据结构堆排序例题 含有燕子的诗句 踏青的诗词名句 两句关于动物的诗句 快速排序c语言 关于兰花的诗句古诗 堆排序法排序怎么排 计数排序算法c++实现 桶式排序 关于放风筝的古诗 冒泡排序python 基数排序怎么排 选择排序法 希尔排序 归并排序python 描写燕子的古诗绝句 踏青诗句最出名诗句 描写夏天的诗句简单 关于写小动物的诗 java快速排序 关于兰花的诗句两句
Top