西北马二最代码
2017-09-19 15:14:24
排序算法总结之归并排序
原创链接:https://segmentfault.com/a/1190000010413296#articleHeader25
1、归并排序概念:
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的迭代;
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
2、算法步骤:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
重复步骤 3 直到某一指针达到序列尾;
将另一序列剩下的所有元素直接复制到合并序列尾。
3、JavaScript代码实现归并排序
function mergeSort(arr) { // 采用自上而下的递归方法 var len = arr.length; if(len < 2) { 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] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }
4、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] <= right[0]: result.append(left.pop(0)); else: result.append(right.pop(0)); while left: result.append(left.pop(0)); while right: result.append(right.pop(0)); return result
5、GO代码实现归并排序
func mergeSort(arr []int) []int { length := len(arr) if length < 2 { 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] <= right[0] { result = append(result, left[0]) left = left[1:] } 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 }
评论
最近浏览
西北马二最代码 LV15
2017年10月12日