归并排序
归并排序(Merge Sort)是建立在归并操作上的一种有效且稳定的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。基本思路是将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。由约翰·冯·诺伊曼在1945年提出。
算法描述
1、首先把长度为n的输入序列分成两个长度为n/2的子序列。
2、再对这两个子序列分别采用归并排序。
3、最后将两个排序好的子序列合并成一个最终的排序序列。
动图演示
代码实现
Java
1 | package com.test; |
排序结果:[1, 5, 6, 8, 9, 15, 20, 23, 32, 45]
JavaScript
1 | function mergeSort(arr,left,right) { |
(10) [1, 5, 6, 8, 9, 15, 20, 23, 32, 45]