小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我们手写排序算法。既然排序算法如此重要,就让我们一起去夯实基础,切切实实得掌握它吧。

前言

先讲两个重要的概念。

1.所谓稳定排序就是指数组中相等的元素在排序过后前后顺序不变。

2.排序算法的平均复杂度是有下限的,为nlog(n)。所以大家不要再想着能发明什么牛逼的算法可以达到线性增长的。至于这个定理的证明,比较复杂,我会在下篇文章中专门讲述。

冒泡算法

运动前总要热身,防止拉伤,深入研究排序算法前,先给大家介绍一个最常见,算法思想最简单最粗暴的排序算法——冒泡排序。

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

def bubble_sort(original_array):
    L = len(original_array)

    for i in range(1, L):
        for j in range(0, L - i):
            if original_array[j] > original_array[j+1]:
                original_array[j], original_array[j+1] = original_array[j+1], original_array[j]

冒泡排序.gif

对该算法进行复杂性分析。我首先取了100个数组,数组规模从1到1000个元素均匀递增,数组中每个数的大小在(1,10000),得到下图。横坐标是排序的数组规模大小,纵坐标是排序所用时间,单位为秒。以后的图纵横坐标都是如此。

bubble_figure_1.png

能够看出来,随着数组元素规模越来越大,所耗费时间呈现螺旋式上升的趋势。不过波动较大,我们也看不太清楚它是个怎么样的曲线。为此我扩大了样本规模,请看下图。

bubble_figure_2.png

从这张图中我们可以很清晰明了的看出,这是个二次曲线。这也符合实际情况,冒泡排序的算法复杂度是数组规模的平方。

冒泡排序可以说是最经典的,最稳定的一个算法,上算法课的同学们一定会接触它。因为它似乎是一把打开算法大门的钥匙,有了它,我们开始知道何为算法。但是,在实际应用中,我们并不用它。

插入排序

大家都有一个经验,打扑克的时候,我们都喜欢按大小顺序来摆放扑克牌,其实我们每次打一把扑克都在进行一次插入排序。

显而易见,扑克牌在我们手中,我们将牌插来插去非常简单。可是这种操作在计算机内存空间中就相当费时。可以去想象,每当我们插入一个数据,比它大的数据元素将整体往后挪动以来达到给它空出内存空间的目的。(python中没有指针,暂时不考虑链表,这也是python的劣势之一)由此我们可以得出一个结论,插入排序适用于数据量较少,而且当大部分数据是有序的情况下。

当数据大部分有序的情况下,复杂度近似于O(n),这非常了不起了。

图片发自简书App

图片发自简书App

直接(简单)插入排序.gif

def insert_sort(original_array):
    L = len(original_array)
    for i in range(1, L):
        for x in range(i-1, -1, -1):
            if original_array[x] > original_array[x+1]:
                original_array[x], original_array[x+1] = original_array[x+1],original_array[x]

insert_figure.png

如图,表现在二次曲线周围上下波动。

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

该排序算法也是个很有纪念意义的算法,它首次突破了当时排序算法复杂度的下线O(n2)。

希尔排序.gif

def shell_sort(original_array):
    L=len(original_array)
    gap = (int)(L/2)
    while(gap>=1):
        for i in range(gap, L):
            for x in range(i-gap, -1, -gap):
                if original_array[x]>original_array[x+gap]:
                    original_array[x], original_array[x+gap] = original_array[x+gap], original_array[x]
        gap = (int)(gap/2)

shell_figure.png

shell_figure2.png

为了是大家相信,我连续跑了两次,显而易见,它并不像上面两个算法一样如此优美得符合二次曲线。其实它在N上的常系数是1.3。

简单选择排序

简单选择排序在本章描述的算法中是最慢,即使在最好的情况下(数组已经完全有序)他的时间复杂度依然需要二次方时间。可以说,它是个“很笨”的算法,从每一次遍历迭代中都不会学到什么。

(简单)选择排序.gif

def select_sort(original_array):
    L = len(original_array)
    for i in range(0, len(original_array)):
        minimum = original_array[i]
        for x in range(i+1, L):
            if original_array[x] < minimum:
                original_array[x], minimum = minimum, original_array[x]
        original_array[i] = minimum

select_figure.png

对于该算法不再阐述过多细节,因为没有什么好说的。

堆排序

现在我们看看堆排序,这个算法展示了如何高效地应用选择排序背后隐藏的原理。

世界杯将要来临,我们都知道世界杯有小组赛,淘汰赛。小组赛需要和小组内每个队伍比一场,而淘汰赛则是输了就回家。我想没有什么比这两种赛制更形象得来表述简单选择排序和堆排序的区别了。

当进入世界杯淘汰赛(32支队伍),每一只队伍都必须连续赢得六场比赛才可以进军决赛。而很巧的是,log(32)=5,这让我们联想到了什么?

没错,就是二叉树。

该算法由1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明。

步骤有三步。

图片发自简书App

图片发自简书App

1.以原始数组为基础,建立最大堆(每个根节点上的值都不小于其左右子节点上的值)

2.经过第一步之后,该二叉树的根节点已经是为该数组的最大值了。将该根节点与二叉树末端子节点置换,然后将置换的该子节点从该二叉树中删除,这样最大值拍到了最后。

3.得到已经删除最末端子节点的二叉树,重复步骤2,直至二叉树仅仅剩下根节点,也就是最小值。

需要注意的是,数组是从0开始索引,因此该算法实现时容易在索引上出错

堆排序.gif

def adjust_max_heap(original_array, L, i):
    left  = 2*i + 1
    right = 2*i + 2
    largest = i
    if (left<L) and (original_array[left]>original_array[largest]):
        largest = left
    if (right<L) and (original_array[right]>original_array[largest]):
        largest = right
    if (largest!=i):
        original_array[i], original_array[largest] = original_array[largest], original_array[i]
        adjust_max_heap(original_array, L, largest)

def build_max_heap(original_array):
    L= len(original_array)
    for x in range((int)((L-2)/2), -1, -1):
        adjust_max_heap(original_array, L, x)

#堆排序
def heap_sort(original_array):
    flag = 1
    build_max_heap(original_array)
    L = len(original_array)
    for i in range(L-1, -1, -1):
        flag = flag + 1
        original_array[0], original_array[i] = original_array[i], original_array[0]
        adjust_max_heap(original_array, i, 0)
        i = i - 1

heap_figure.png

可以看出来,速度非常快,而且几乎是线性的。当然,它不是线性的,它是O(nlogn)。

快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序.gif

def quick_sort(original_array, start, end):
    if start < end:
        i,j,pivot = start, end, original_array[start]
        while(i<j):
            while(i<j) and (original_array[j] >= pivot):
                j = j - 1
            if(i<j):
                original_array[i] = original_array[j]
                i = i + 1
            while(i<j) and (original_array[i]<pivot):
                i = i + 1
            if(i<j):
                original_array[j] = original_array[i]
                j = j - 1
        original_array[i] = pivot
        quick_sort(original_array, start, i-1)
        quick_sort(original_array, i+1, end)

quick_figure.png

在最坏情况下,其时间复杂度退化成二次方,但在平均情况下,其效果和堆排序一样好。

基数排序

给大家介绍一种比较巧妙的排序。看图便知其思路,独辟蹊径。

基数排序.gif

def radix_sort_nums(L):
    maxNum = L[0]
    for x in L:
        if maxNum < x:
            maxNum = x
    times = 0
    while (maxNum > 0):
        maxNum = (int)(maxNum/10)
        times = times+1
    return times
def get_num_pos(num,pos):
    return ((int)(num/(10**(pos-1))))%10

def radix_sort(L):
    count = 10*[None]       
    bucket = len(L)*[None]  
    for pos in range(1,radix_sort_nums(L)+1):
        for x in range(0,10):
            count[x] = 0
        for x in range(0,len(L)):
            j = get_num_pos(int(L[x]),pos)
            count[j] = count[j]+1
        for x in range(1,10):
            count[x] = count[x] + count[x-1]
        for x in range(len(L)-1,-1,-1):
            j = get_num_pos(L[x],pos)
            bucket[count[j]-1] = L[x]
            count[j] = count[j]-1
        for x in range(0,len(L)):
            L[x] = bucket[x]

radix_figure.png

归并排序

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

归并排序.gif

def mergearray(L,first,mid,last,temp):
    i,j,k = first,mid+1,0
    while (i <= mid) and (j <= last):
        if L[i] <= L[j]:
            temp[k] = L[i]
            i = i+1
            k = k+1
        else:
            temp[k] = L[j]
            j = j+1
            k = k+1
    while (i <= mid):
        temp[k] = L[i]
        i = i+1
        k = k+1
    while (j <= last):
        temp[k] = L[j]
        j = j+1
        k = k+1
    for x in range(0,k):
        L[first+x] = temp[x]
def merge_sort(L,first,last,temp):
    if first < last:
        mid = (int)((first + last) / 2)
        merge_sort(L,first,mid,temp)
        merge_sort(L,mid+1,last,temp)
        mergearray(L,first,mid,last,temp)
def merge_sort_array(L):
    temp = len(L)*[None]
    merge_sort(L,0,len(L)-1,temp)

merge_figure.png

总结

图片发自简书App

图片发自简书App

从算法复杂性分析的图得知,当数据量较大时,快速排序、堆排序、归并排序、基数排序的速度都很快。其中快速排序无疑是速度最快的,当然它存在一个问题,当迭代次数再次扩大许多时,它的递归便存在问题,这涉及到快速排序的深度优化,以后会给大家讲解。

而当数据量较小,尤其是原始数组大部分情况下本来就是有序的情况下,插入排序是最佳选择。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

大整数乘法

                                                                                ...

24450
来自专栏海天一树

Codeforces 976E 题解报告

http://codeforces.com/contest/976/problem/E

13330
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

38390
来自专栏跟着阿笨一起玩NET

UML类图几种关系的总结

本文转载:http://blog.csdn.net/tianhai110/article/details/6339565

9210
来自专栏编程直播室

读书笔记:《算法图解》第三章 递归

17550
来自专栏算法channel

机器学习|快速排序思想求topk

01 — Topk by quicksort 问题是求出数据集中,按照某个规则定义的元素大小,取前k个元素。 为了简化起见,直接求数值型数组的前k个最大元素。...

59780
来自专栏进击的程序猿

进击算法:字符串匹配的 BM 算法

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

34630
来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

26890
来自专栏ACM小冰成长之路

51Nod-1645-中位数变换

ACM模版 描述 ? 题解 这个题很明显是找规律的问题,直接暴力肯定会超时……虽然我也是暴力也两发才反应过来……平时做题总是抱着侥幸心理,比赛时却总是胆小如鼠…...

23270
来自专栏C语言及其他语言

[每日一题]偶数求和

题目描述 有一个长度为n(n<=100)的数列,该数列定义为从2开始的递增有序偶数(公差为2的等差数列),现在要求你按照顺序每m个数求出一个平均值,如果最后不足...

30850

扫码关注云+社区

领取腾讯云代金券