Python学习(三) 八大排序算法的实现(下)

本文Python实现了插入排序、基数排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序的后面四种。 上篇:Python学习(三) 八大排序算法的实现(上)

1.快速排序

描述 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 1.先从数列中取出一个数作为基准数。 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 3.重复上述过程

代码实现

def quick_sort(lists):
    if lists == []:
        return []
    else:
        divide = lists[0]
        lesser = quick_sort([x for x in lists[1:] if x<divide])
       #链表推导式,返回值是由for或if子句之后的表达式得到的元素组成的链表
        bigger = quick_sort([x for x in lists[1:] if x>=divide])
        return lesser + [divide] + bigger
if __name__=="__main__":
    lists = [19,-3,2,10,45,-34,17]
    print quick_sort(lists)

2.直接选择排序

描述 基本思想:第1趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;第2趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。 代码实现

def select_order(lists):
    length = len(lists)
    for i in range(0,length):
        min = i
        for j in range(i+1,length):
            if lists[min] > lists[j]:
                min = j
        lists[min],lists[i] = lists[i],lists[min]
    return lists
if __name__ == '__main__':
    lists = [12,13,15,9,16,14]            
    print select_order(lists) 

3.堆排序

描述 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。 利用了大顶堆堆顶元素最大的特点,不断取出最大元素,并调整使剩下的元素还是大顶堆,依次取出最大元素就是排好序的列表。 代码实现

def build_heap(lists):
    count = len(lists)
    for i in range(count//2-1,-1,-1):        
        adjust_heap(lists,i,count)

def adjust_heap(lists,i,n):
    j = i*2 +1
    while j < n:
        if j+1 < n and lists[j]<lists[j+1]:
            j +=1
        if lists[i] > lists[j]:
            break
        lists[i],lists[j] = lists[j],lists[i]
        i = j 
        j = i*2 + 1
#大顶堆排序
def heap_sort( lists ):
    count = len( lists )
    build_heap( lists )
    #交换堆顶与最后一个结点,再调整堆
    for i in range( count - 1, 0, -1 ):
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap( lists, 0, i )
    return lists
lists = [-3, 1, 3, 0, 9, 7]
print heap_sort(lists)

4.归并排序

描述 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序具体工作原理如下(假设序列共有n个元素): 1. 将序列每相邻两个数字进行归并操作,形成个序列,排序后每个序列包含两个元素 2. 将上述序列再次归并,形成个序列,每个序列包含四个元素 3. 重复步骤2,直到所有元素排序完毕

代码实现

def merge_sort(lists):
    if len(lists)<=1:
        return lists
    left = merge_sort(lists[:len(lists)/2])
    right = merge_sort(lists[len(lists)/2:len(lists)])
    result = []
    while len(left) > 0 and len(right)> 0:
        if( left[0] > right[0]):  
            result.append(right.pop(0))  
        else:
            result.append(left.pop(0))  
    if(len(left)>0):
        result.extend(merge_sort(left))  
    else:
        result.extend(merge_sort(right))  
    return result  
def main():  
    lists = [2,11,55,33,32,64,18]  
    print merge_sort(lists)   
if __name__=="__main__":  
    main()  

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

十种常见排序算法

十种常见排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择...

581
来自专栏mathor

十大经典排序算法(动图演示)

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 ...

2283
来自专栏我是东东强

常见算法之排序

各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准...

872
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

1838
来自专栏Python爬虫与数据挖掘

浅谈Python内置对象类型——数字篇(附py2和py3的区别之一)

Python是一门面向对象的编程设计语言,程序中每一样东西都可以视为一个对象。Python内置对象可以分为简单类型和容器类型,简单类型主要是数值...

862
来自专栏青玉伏案

算法导论之插入排序和归并排序

  作为一名前线的码农不时地看一下算法和数据结构还是很有必要的,虽然《算法导论》这本书很难啃,但还是有必要啃一下的。算法这东西和某种编程语言关系不大,在大学的课...

2107
来自专栏Python

推导式详解

推导式的套路 除列表推导式和生成器表达式之外,其实还有字典推导式、集合推导式等等。 下面是一个以列表推导式为例的推导式详细格式,同样适用于其他推导式。 vari...

1899
来自专栏CDA数据分析师

算法和数据结构—— 查找和排序

本文为简书作者郑永欣原创,CDA数据分析师已获得授权 查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单,不外乎顺序查找、二分查找、哈希表查找和二叉排...

2006
来自专栏架构师小秘圈

秒懂排序算法

作者:郭耀华,来自:cnblogs.com/guoyaohua 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳...

3635
来自专栏Java 源码分析

八大排序算法

​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。 冒泡排序...

3713

扫码关注云+社区