程序员面试必备之排序算法汇总(下)

希望小小詹同学学习同时能便于他人~


本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。上篇已经介绍了前三种~给出原文链接如下:程序员面试必备之排序算法汇总(上)

四、归并排序

1.介绍

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

2.步骤

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

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

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

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

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

3.python实现

#encoding=utf-8
def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) // 2    #python3  //区别/
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)
array = [49, 38, 65, 97, 76, 13, 27, 49]
list1 = merge_sort(array)
print(list1)

4.视觉效果展示

五、堆排序

1.介绍

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

2.步骤(略)

3.python实现

#encoding=utf-8
#沿左,右子节点较大者依次往下调整
def heapify( array, i, n ):
    j = i * 2 + 1
    while j < n:
        if j + 1 < n and array[j] < array[j + 1]:
            j += 1
        if array[i] > array[j]:
            break
        array[i], array[j] = array[j], array[i]
        i = j
        j = i * 2 + 1
#创建堆
def build_heap( array ):
    size = len( array )
    for i in range( size // 2 - 1, -1, -1 ):
        heapify( array, i, size )
#大顶堆排序
def heap_sort( array ):
    size = len( array )
    build_heap( array )
    #交换堆顶与最后一个结点,再调整堆
    for i in range( size - 1, 0, -1 ):
        array[0], array[i] = array[i], array[0]
        heapify( array, 0, i )
a = [ -3, 1, 3, 0, 9, 7 ]
heap_sort( a )
print( a )

4.视觉效果展示

六、选择排序

1.介绍

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

2.步骤(略)

3.python实现

#encoding=utf-8
def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists
a = [ -3, 1, 3, 0, 9, 7 ]
select_sort( a )
print( a )

4.视觉效果展示

七、冒泡排序

1.介绍

冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.步骤

(1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。

(2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

(3)针对所有的元素重复以上的步骤,除了最后一个。

(4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

3.python实现

#encoding=utf-8
def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists
a = [ -3, 1, 3, 0, 9, 7 ]
bubble_sort( a )
print( a )

4.视觉效果展示

原文发布于微信公众号 - 小小詹同学(xiaoxiaozhantongxue)

原文发表时间:2018-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

python分布式爬虫搜索引擎实战-1-正则表达式

正则表达式 比如: 一天前中提取出1 特殊字符: ^:代表以该字符为开头。如^b就是b为开头。 .: 代表任意一个字符。如^b.就是b开头后面一个字母任意...

38213
来自专栏小樱的经验随笔

【Java学习笔记之十六】浅谈Java中的继承与多态

1、  什么是继承,继承的特点? 子类继承父类的特征和行为,使得子类具有父类的各种属性和方法。或子类从父类继承方法,使得子类具有父类相同的行为。 特点:在继承关...

2617
来自专栏微信公众号:Java团长

Java基础11 对象引用

我们之前一直在使用“对象”这个概念,但没有探讨对象在内存中的具体存储方式。这方面的讨论将引出“对象引用”(object reference)这一重要概念。

832
来自专栏派森公园

Scala中的闭包

除此之外,Scala还支持引用其他地方定义的变量:(x: Int) => x + more,这个函数将more也作为入参,不过这个参数是哪里来的?从这个函数的角...

561
来自专栏塔奇克马敲代码

第 14 章 重载运算与类型转换

2326
来自专栏PHP在线

欢迎来到phpdaily

1.Null类型,表示空对象指针,使用typeof检测会返回object。 如果定义的变量在将来用于保存对象,最好将该变量初始化为NUll.可以体现null作为...

3277
来自专栏Android开发指南

5:面向对象总结

36912
来自专栏WindCoder

Java漫谈-数组

在Java语言中,数组是对象(An object is a class instance or an array.),而且是动态创建的。

1591
来自专栏顶级程序员

一文读懂Python可迭代对象、迭代器和生成器

序列可以迭代的原因:iter 函数。解释器需要迭代对象 x 时,会自动调用 iter(x)。内置的 iter 函数有以下作用:

1233
来自专栏用户2442861的专栏

java中的内部类总结

http://www.cnblogs.com/nerxious/archive/2013/01/24/2875649.html

903

扫码关注云+社区

领取腾讯云代金券