5-算法-归并排序

淩亂°似流年 2022-09-04 15:52 174阅读 0赞

### 文章目录 ###

*  归并排序
 *   *  2. 算法步骤
     *  3. 动图演示
     *  4. JavaScript 代码实现
     *  5. Python 代码实现
     *  6. Go 代码实现
     *  7. Java 代码实现
     *  8. PHP 代码实现
 *  十大排序算法
 *   *  关于时间复杂度
     *  各个算法的实现

# 归并排序 #

归并排序（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. 动图演示 ##

![动图演示][d277c95df59e3867695f9af14fdad3b3.gif]

## 4. JavaScript 代码实现 ##

## 5. 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

## 6. 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
    }

## 7. 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;
        }
    
    }

## 8. PHP 代码实现 ##

# 十大排序算法 #

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

![img][]

## 关于时间复杂度 ##

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

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

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

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

关于稳定性

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

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

名词解释：

*  n：数据规模
 *  k："桶"的个数
 *  In-place：占用常数内存，不占用额外内存
 *  Out-place：占用额外内存
 *  稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

## 各个算法的实现 ##

[1-冒泡排序][1-]

[2-选择排序][2-]

[3-算法-插入排序][3-_-]

[4-算法-希尔排序][4-_-]

[5-算法-归并排序][5-_-]

[6-算法-归并排序][6-_-]

[7-算法-堆排序][7-_-]

[8-算法-计数排序][8-_-]

[9-算法-桶排序][9-_-]

[10-基数排序][10-]

[d277c95df59e3867695f9af14fdad3b3.gif]: /images/20220829/306766a5c5ad48859c04897df74dba37.png
[img]: /images/20220829/86e61b8647294f4baa454f84c2ccc088.png
[1-]: https://blog.csdn.net/sexyluna/article/details/119711977
[2-]: https://blog.csdn.net/sexyluna/article/details/119711999
[3-_-]: https://blog.csdn.net/sexyluna/article/details/119712005
[4-_-]: https://blog.csdn.net/sexyluna/article/details/119712017
[5-_-]: https://blog.csdn.net/sexyluna/article/details/119712030
[6-_-]: https://blog.csdn.net/sexyluna/article/details/119712042
[7-_-]: https://blog.csdn.net/sexyluna/article/details/119712058
[8-_-]: https://blog.csdn.net/sexyluna/article/details/119712062
[9-_-]: https://blog.csdn.net/sexyluna/article/details/119712072
[10-]: https://blog.csdn.net/sexyluna/article/details/119712108