归并排序
归并排序(Merge Sort)是建立在归并操作上的一种有效且稳定的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。基本思路是将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。由约翰·冯·诺伊曼在1945年提出。
参考链接
算法描述
1、首先把长度为n的输入序列分成两个长度为n/2的子序列。
2、再对这两个子序列分别采用归并排序。
3、最后将两个排序好的子序列合并成一个最终的排序序列。
动图演示
代码实现
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| package com.test;
import java.util.Arrays;
public class MergeSort { private static int[] tmp;
public static void main(String[] args) { int[] arr = {23, 20, 32, 5, 45, 6, 8, 9, 15, 1}; tmp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1); System.out.println("排序结果:" + Arrays.toString(arr)); }
public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } }
public static void merge(int[] arr, int left, int mid, int right) { int i = left; int j = mid + 1; for (int k = left; k <= right; k++) { tmp[k] = arr[k]; }
for (int k = left; k <= right; k++) { if (i > mid) { arr[k] = tmp[j++]; } else if (j > right) { arr[k] = tmp[i++]; } else if (tmp[j] < tmp[i]) { arr[k] = tmp[j++]; } else { arr[k] = tmp[i++]; } } } }
|
排序结果:[1, 5, 6, 8, 9, 15, 20, 23, 32, 45]
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| function mergeSort(arr,left,right) { if (left < right) { var mid = Math.floor((left + right) / 2); mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } }
function merge(arr,left,mid,right) { var i = left; var j = mid + 1; for (var k = left; k <= right; k++) { tmp[k] = arr[k]; }
for (var k = left; k <= right; k++) { if (i > mid) { arr[k] = tmp[j++]; } else if (j > right) { arr[k] = tmp[i++]; } else if (tmp[j] < tmp[i]) { arr[k] = tmp[j++]; } else { arr[k] = tmp[i++]; } } }
var arr = [23,20,32,5,45,6,8,9,15,1]; var tmp = new Array(arr.length); mergeSort(arr,0,arr.length-1); console.log(arr);
|
(10) [1, 5, 6, 8, 9, 15, 20, 23, 32, 45]