归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(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) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
-
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列; -
设定两个指针,最初位置分别为两个已经排序序列的起始位置; -
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置; -
重复步骤 3 直到某一指针达到序列尾; -
将另一序列剩下的所有元素直接复制到合并序列尾。
动图演示
代码实现
JavaScript
实例
function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if(len 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] 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)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] 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 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] 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 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] 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 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 for (seg = 1; seg for (start = 0; start while (start1 while (start1 while (start2 if (a != arr) {
int i;
for (i = 0; i
递归版:
实例
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 while (start1 while (start2 for (k = start; k
C++
迭代版:
实例
template // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(for (int seg = 1; seg for (int start = 0; start while (start1 while (start1 while (start2 if (a != arr) {
for (int i = 0; i
递归版:
实例
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 if (LeftSubArray[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 return lst;
int mid = lst.Count / 2;
List left = new List(); // 定义左侧List
List right = new List(); // 定义右侧List
// 以下兩個循環把 lst 分為左右兩個 List
for (int i = 0; i for (int j = mid; j 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] else {
temp.Add(right[0]);
right.RemoveAt(0);
}
}
if (left.Count > 0) {
for (int i = 0; i if (right.Count > 0) {
for (int i = 0; i return temp;
}
Ruby
实例
def merge list
return list if list.size # Merge
lambda { |left, right|
final = []
until left.empty? or right.empty?
final if left.first else right.shift end
end
final + left + right
}.call merge(list[0...pivot]), merge(list[pivot..-1])
end
以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !