美文网首页
排序算法总结(二)

排序算法总结(二)

作者: 九日照林 | 来源:发表于2018-02-26 19:10 被阅读7次

归并排序

归并排序用的是分而治之的方法。也就是把列表从中间分成两个子列表,子列表又各自分为两个子列表……这样直到最后子列表中只有一个元素为止。然后再依次合并子列表。图示如下。

排序算法分而治之

合并的过程用到的两个子序列都是已经排好序的。各自遍历两个子列表的当前元素i和j,比较i和j,每次都选出比较小的数,分配到初始新列表的位置,注意要查看如果其中一个子序列遍历完了,直接把另外一个子序列添加到新列表剩余位置即可。

依次填入较小的序列
伪代码
merge_sort(nums)
    if low>=high
        return
    middle=(low+high)//2
    merge_sort(low, middle)
    merge_sort(middle, high)
    merge(nums, low, middle,high)

merge()
for i from low to high
    tmp[i]=nums[i]
    i=low
    j=middle+1
    k=low
    while i<=middle and j<=high:
        if tmp[i]<=tmp[j]:
            nums[k]=tmp[i]
            k++
            i++
        if tmp[i]>tmp[j]:
            nums[k]=tmp[j]
            k++
            j++
    while i<middle:
        nums[k]=tmp[i]
            k++
            i++
    while j<high:
        nums[k]=tmp[j]
            k++
            j++
end

代码如下:

def merge(a, b):
    c=[]
    i=j=0
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            c.append(a[i])
            i+=1
        else:
            c.append(b[j])
            j+=1
    if j==len(b):
        for g in a[i:]:         
            c.append(g)

    else:
        for g in b[j:]:         
            c.append(g)
    #最终返回的是这个合并了的列表
    return c
def merge_sort(nums):
    #如果最后只剩下一个元素就返回这个元素
    if len(nums)<=1:
        return nums
    middle=len(nums)/2
    left=nums[:middle]
    right=nums[middle:]
    left=merge_sort(left)
    right=merge_sort(right)
    return merge(left, right)

相关文章

  • iOS算法总结-堆排序

    iOS算法总结-堆排序 iOS算法总结-堆排序

  • iOS算法总结-冒泡排序

    iOS算法总结-冒泡排序 iOS算法总结-冒泡排序

  • 算法学习(1)-排序算法

    八大排序算法九大排序算法再总结[经典排序算法][集锦][直观学习排序算法] 视觉直观感受若干常用排序算法 快速排序...

  • 面试常问的排序算法

    排序算法总结 排序是算法问题中的经典问题。为什么要总结排序算法呢?你懂的 : (假设所有的排序都是要求最终结果为:...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 排序算法

    一、排序算法总结 排序算法题目 排序算法快速排序堆排序归并排序 应用最小K个数(TopK问题)215.数组中的第K...

  • 一文搞定十大经典排序算法(Java实现)

    本文总结十大经典排序算法及变形,并提供Java实现。参考文章:十大经典排序算法总结(Java语言实现)快速排序算法...

  • Swift的十大经典排序算法总结

    Swift的十大经典排序算法总结 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排...

  • 算法-排序算法总结

    排序类型总结 1 排序算法基础实现 2 排序算法应用 2.1 基础排序 2.2 计数排序应用 2.3 快排应用 2...

  • 常用非比较类排序算法

    前言 本篇完全转载于常用排序算法总结(二)。 其中有部分代码进行了更改,更改成java语言。 非对比类排序算法 非...

网友评论

      本文标题:排序算法总结(二)

      本文链接:https://www.haomeiwen.com/subject/pntuxftx.html