程序员必知的十大基础实用算法之-归并排序

广告位

归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divi…

归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序原理,先上图,如果是奇数个数据

程序员必知的十大基础实用算法之-归并排序


算法步骤

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

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

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

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

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

程序员必知的十大基础实用算法之-归并排序


归并操作

归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

如 设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11;

逆序数为14;


用途

  1. 排序

(速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列,应用见2011年普及复赛第3题“瑞士轮”的标程)

2.求逆序对数

具体思路是,在归并的过程中计算每个小区间的逆序对数,进而计算出大区间的逆序对数(也可以用树状数组来求解)


示例代码

Go语言

func mergeSort(r []int) []int {
length := len(r)
if length <= 1 {
return r
}
num := length / 2
left := mergeSort(r[:num])
right := mergeSort(r[num:])
return merge(left, right)
}
func merge(left, right []int) (result []int) {
l, r := 0, 0
for l < len(left) && r < len(right) {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}

Java语言

package MergeSort;
public class MergeSort {
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };

int mid = l + (h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组

int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}
public static void main(String[] args) {
int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] newNums = mergeSort(nums, 0, nums.length - 1);
for (int x : newNums) {
System.out.println(x);
}
}
}

C#语言

public static void Sort(int[] a, int f, int e)
{
if (f < e)
{
int mid = (f + e) / 2;
Sort(a, f, mid);
Sort(a, mid + 1, e);
MergeMethid(a, f, mid, e);
}
}
private static void MergeMethid(int[] a, int f, int mid, int e)
{
int[] t = new int[e - f + 1];
int m = f, n = mid + 1, k = 0;
while(n <= e && m <= mid)
{
if (a[m] > a[n]) t[k++] = a[n++];
else t[k++] = a[m++];
}
while (n < e + 1) t[k++] = a[n++];
while (m < mid + 1) t[k++] = a[m++];
for (k = 0, m = f; m < e + 1; k++, m++) a[m] = t[k];
}

Python语言

def MergeSort(lists):
if len(lists) <= 1:
return lists
num = int( len(lists) / 2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
return Merge(left, right)
def Merge(left,right):
r, l=0, 0
result=[] while l<len(left) and r<len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += list(left[l:])
result += list(right[r:])
return result
print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])

C语言

#include <stdlib.h>
#include <stdio.h>

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i] > sourceArr[j])
tempArr[k++] = sourceArr[j++];
else
tempArr[k++] = sourceArr[i++];
}
while(i != midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j != endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex; i<=endIndex; i++)
sourceArr[i] = tempArr[i];
}

//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
int midIndex;
if(startIndex < endIndex)
{
midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}

int main(int argc, char * argv[])
{
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf("n");
return 0;
}

JavaScript语言

function merge(left, right){
var result=[];
while(left.length>0 && right.length>0){
if(left[0]<right[0]){
/*shift()方法用于把数组的第一个元素从其中删除,并返回第一个元素的值。*/
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
function mergeSort(items){
if(items.length == 1){
return items;
}
var middle = Math.floor(items.length/2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

天使的淚滴

关于作者: 天使的淚滴

为您推荐

广告位

发表评论