H5W3
当前位置:H5W3 > 其他技术问题 > 正文

【算法】归并排序

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

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

  1. 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  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) 的时间复杂度。代价是需要额外的内存空间。

算法步骤
  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示

归并排序介绍

代码实现
JavaScript

实例

function mergeSort(arr) {  // 采用自上而下的递归方法
var len = arr.length;
if(len
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]
Go

 

实例

 

func mergeSort(arr []int) []int {
length := len(arr)
if length
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  0 && right.length > 0) {
if (left[0]  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  0 && count($right) > 0) {
if ($left[0]
C

 

实例

 

int min(int x, int y) {
return x

递归版:

 

实例

 

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
C++

 

迭代版:

 

实例

 

template // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(

递归版:

实例

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  &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  left = new List();  // 定义左侧List
List right = new List(); // 定义右侧List
// 以下兩個循環把 lst 分為左右兩個 List
for (int i = 0; i
/// 合併兩個已經排好序的List
///
/// 左側List
/// 右側List
/// 
static List merge(List left, List right) {
List temp = new List();
while (left.Count > 0 && right.Count > 0) {
if (left[0]  0) {
for (int i = 0; i  0) {
for (int i = 0; i
Ruby

实例

def merge list
return list if list.size

本文地址:H5W3 » 【算法】归并排序

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址