则称所运用的排序方法是牢固的,则称所利用的排序方法是安静的

2. 调整和裁减不供给的沟通

原先的代码中pivot_key这么些记录总是再随地的调换中,其实那是没供给的,完全能够将它暂存在有个别一时变量中,如下所示:

def partition(self, low, high):

        lis = self.r

        m = low + int((high-low)/2)
        if lis[low] > lis[high]:
            self.swap(low, high)
        if lis[m] > lis[high]:
            self.swap(high, m)
        if lis[m] > lis[low]:
            self.swap(m, low)

        pivot_key = lis[low]
        # temp暂存pivot_key的值
        temp = pivot_key
        while low < high:
            while low < high and lis[high] >= pivot_key:
                high -= 1
            # 直接替换,而不交换了
            lis[low] = lis[high]
            while low < high and lis[low] <= pivot_key:
                low += 1
            lis[high] = lis[low]
            lis[low] = temp
        return low

五、Hill排序

Hill排序(Shell
Sort)是插入排序的改进版本,其核激情想是将原数据集结分割成几何个头系列,然后再对子种类分别张开直接插入排序,使子种类基本有序,最终再对一切记录进行三回直接插入排序。

此间最重要的是跳跃和细分的计谋,也正是我们要怎么划分数据,间隔多大的主题素材。平时将离开有些“增量”的记录组成多少个子连串,那样本事确认保障在子体系内分别开展直接插入排序后拿走的结果是主旨有序并不是某些有序。上边包车型客车例证中通过:increment
= int(increment/3)+1来规定“增量”的值。

Hill排序的小时复杂度为:O(n^(3/2))

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 希尔排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def shell_sort(self):
        """希尔排序"""
        lis = self.r
        length = len(lis)
        increment = len(lis)
        while increment > 1:
            increment = int(increment/3)+1
            for i in range(increment+1, length):
                if lis[i] < lis[i - increment]:
                    temp = lis[i]
                    j = i - increment
                    while j >= 0 and temp < lis[j]:
                        lis[j+increment] = lis[j]
                        j -= increment
                    lis[j+increment] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22])
    sqlist.shell_sort()
    print(sqlist)

 

三、简单选拔排序

差相当少采用排序(simple selection sort):时间复杂度O(n^2)
由此n-i次首要字之内的可比,从n-i+1个记录中选出第一字十分的小的笔录,并和第i(1<=i<=n)个记录进行沟通。

通俗的说就是,对未有到位排序的持有因素,彻头彻尾比三遍,记录下纤维的不得了成分的下标,也正是该因素的任务。再把该因素调换来前段时间遍历的最前面。其功用之处在于,每一轮中相比了无数次,但只沟通一回。由此固然它的光阴复杂度也是O(n^2),但比冒泡算法依旧要好一点。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 简单选择排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def select_sort(self):
        """
        简单选择排序,时间复杂度O(n^2)
        """
        lis = self.r
        length = len(self.r)
        for i in range(length):
            minimum = i
            for j in range(i+1, length):
                if lis[minimum] > lis[j]:
                    minimum = j
            if i != minimum:
                self.swap(i, minimum)

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
    sqlist.select_sort()
    print(sqlist)

一、排序的基本概念和归类

所谓排序,就是使一串记录,根据内部的某部或少数重大字的分寸,递增或递减的排列起来的操作。排序算法,正是怎么着使得记录依据需求排列的秘诀。

排序的平安:
通过某种排序后,假设四个记录序号同等,且相互在原冬天记录中的前后相继秩序依旧保持不改变,则称所运用的排序方法是平稳的,反之是不安宁的。

内排序和向外排水序
内排序:排序进程中,待排序的全部记录整个坐落内部存款和储蓄器中
外排序:排序进度中,使用到了外界存款和储蓄。
普通研讨的都以内排序。

潜移暗化内排序算法品质的多个因素

  • 岁月复杂度:即时间品质,高作用的排序算法应该是负有尽只怕少的第一字相比较次数和记录的运动次数
  • 空间复杂度:主借使实践算法所供给的帮扶空间,越少越好。
  • 算法复杂性。首倘若指代码的复杂。

依靠排序进度中凭仗的入眼操作,可把内排序分为:

  • 插入排序
  • 换来排序
  • 选择排序
  • 归并排序

遵照算法复杂度可分为两类:

  • 归纳算法:包蕴冒泡排序、轻松选拔排序和直接插入排序
  • 革新算法:包蕴Hill排序、堆排序、归并排序和便捷排序

以下的多种排序算法只是有着排序算法中最卓越的二种,不代表全部。

 

迎接大家访问笔者的村办网址《刘江(Liu Jiang)的博客和课程》:www.liujiangblog.com

二、 冒泡排序

冒泡排序(Bubble sort):时间复杂度O(n^2)
换到排序的一种。其核心情想是:两两相比相邻记录的入眼字,要是反序则沟通,直到未有反序记录甘休。

其促成细节能够不一样,举例上边3种:

  1. 最轻便易行排序完毕:bubble_sort_simple
  2. 冒泡排序:bubble_sort
  3. 查对的冒泡排序:bubble_sort_advance

    #!/usr/bin/env python
    # –– coding:utf-8 –
    # Author: Liu Jiang
    # Python 3.5
    # 冒泡排序算法

class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def bubble_sort_simple(self):
        """
        最简单的交换排序,时间复杂度O(n^2)
        """
        lis = self.r
        length = len(self.r)
        for i in range(length):
            for j in range(i+1, length):
                if lis[i] > lis[j]:
                    self.swap(i, j)

    def bubble_sort(self):
        """
        冒泡排序,时间复杂度O(n^2)
        """
        lis = self.r
        length = len(self.r)
        for i in range(length):
            j = length-2
            while j >= i:
                if lis[j] > lis[j+1]:
                    self.swap(j, j+1)
                j -= 1

    def bubble_sort_advance(self):
        """
        冒泡排序改进算法,时间复杂度O(n^2)
        设置flag,当一轮比较中未发生交换动作,则说明后面的元素其实已经有序排列了。
        对于比较规整的元素集合,可提高一定的排序效率。
        """
        lis = self.r
        length = len(self.r)
        flag = True
        i = 0
        while i < length and flag:
            flag = False
            j = length - 2
            while j >= i:
                if lis[j] > lis[j + 1]:
                    self.swap(j, j + 1)
                    flag = True
                j -= 1
            i += 1

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4,1,7,3,8,5,9,2,6])
    # sqlist.bubble_sort_simple()
    # sqlist.bubble_sort()
    sqlist.bubble_sort_advance()
    print(sqlist)

 

四、间接插入排序

间接插入排序(Straight Insertion Sort):时间复杂度O(n^2)
基本操作是将二个笔录插入到已经排好序的平稳表中,进而获得多少个新的、记录数增1的有序表。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 直接插入排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def insert_sort(self):
        lis = self.r
        length = len(self.r)
        # 下标从1开始
        for i in range(1, length):
            if lis[i] < lis[i-1]:
                temp = lis[i]
                j = i-1
                while lis[j] > temp and j >= 0:
                    lis[j+1] = lis[j]
                    j -= 1
                lis[j+1] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
    sqlist.insert_sort()
    print(sqlist)

该算法需求贰个记录的增派空间。最棒状态下,当原始数据正是有序的时候,只需求一轮相比较,不供给活动记录,此时光阴复杂度为O(n)。可是,那基本是白日做梦。
图片 1

4. 优化递归操作

可以使用尾递归的秘诀对全体算法的递归操作实行优化,改写qsort方法如下:

def qsort(self, low, high):
    """根据序列长短,选择使用快速排序还是简单插入排序"""
    # 7是一个经验值,可根据实际情况自行决定该数值。
    MAX_LENGTH = 7
    if high-low < MAX_LENGTH:
        # 改用while循环
        while low < high:
            pivot = self.partition(low, high)
            self.qsort(low, pivot - 1)
            # 采用了尾递归的方式
            low = pivot + 1
    else:
        # insert_sort方法是我们前面写过的简单插入排序算法
        self.insert_sort()

 

二、 冒泡排序

冒泡排序(Bubble sort):时间复杂度O(n^2)
换来排序的一种。其核刺激想是:两两比较相邻记录的首要字,假使反序则交流,直到未有反序记录截至。

其落到实处细节能够分化,比方上面3种:

  1. 最简便易行排序达成:bubble_sort_simple
  2. 冒泡排序:bubble_sort
  3. 革新的冒泡排序:bubble_sort_advance

    #!/usr/bin/env python
    # –– coding:utf-8 –
    # Author: Liu Jiang
    # Python 3.5
    # 冒泡排序算法

class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def bubble_sort_simple(self):
        """
        最简单的交换排序,时间复杂度O(n^2)
        """
        lis = self.r
        length = len(self.r)
        for i in range(length):
            for j in range(i+1, length):
                if lis[i] > lis[j]:
                    self.swap(i, j)

    def bubble_sort(self):
        """
        冒泡排序,时间复杂度O(n^2)
        """
        lis = self.r
        length = len(self.r)
        for i in range(length):
            j = length-2
            while j >= i:
                if lis[j] > lis[j+1]:
                    self.swap(j, j+1)
                j -= 1

    def bubble_sort_advance(self):
        """
        冒泡排序改进算法,时间复杂度O(n^2)
        设置flag,当一轮比较中未发生交换动作,则说明后面的元素其实已经有序排列了。
        对于比较规整的元素集合,可提高一定的排序效率。
        """
        lis = self.r
        length = len(self.r)
        flag = True
        i = 0
        while i < length and flag:
            flag = False
            j = length - 2
            while j >= i:
                if lis[j] > lis[j + 1]:
                    self.swap(j, j + 1)
                    flag = True
                j -= 1
            i += 1

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4,1,7,3,8,5,9,2,6])
    # sqlist.bubble_sort_simple()
    # sqlist.bubble_sort()
    sqlist.bubble_sort_advance()
    print(sqlist)

1. 优化增选的pivot_key

前边大家每趟接纳pivot_key的都以子系列的首先个因素,也正是lis[low],那就比较看运气。运气好时,该值处于整个种类的临近中间值,则构造的树相比平衡,运气相当差,处于最大或纤维地方紧邻则构造的树临近斜树。
为了保证pivot_key选择的尽心方便,接纳选择系列左中右四个奇特职位的值中,处于中间值的这么些数为pivot_key,通常会比直接用lis[low]要好一点。在代码中,在本来的pivot_key
= lis[low]这一行后面扩充上面的代码:

m = low + int((high-low)/2)
if lis[low] > lis[high]:
    self.swap(low, high)
if lis[m] > lis[high]:
    self.swap(high, m)
if lis[m] > lis[low]:
    self.swap(m, low)

借使以为那样还相当不够好,还足以将全体系列先划分为3部分,每一部分求出个pivot_key,再对3个pivot_key再做三次地方的可比得出最后的pivot_key。这时的pivot_key应该非常的大可能率是三个相比可信的值。

 

五、Hill排序

希尔排序(Shell
Sort)是插入排序的立异版本,其主旨境想是将原数据集合分割成几何个子体系,然后再对子系列分别开展直接插入排序,使子连串基本有序,最后再对全体记录实行一回直接插入排序。

此处最器重的是跳跃和分叉的计谋,也正是大家要怎么划分数据,间隔多大的标题。常常将相差有些“增量”的记录组成二个子系列,那样才具担保在子体系内分别进行间接插入排序后获得的结果是大旨不改变实际不是局地有序。下边包车型客车例子中经过:increment
= int(increment/3)+1来规定“增量”的值。

Hill排序的年华复杂度为:O(n^(3/2))

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 希尔排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def shell_sort(self):
        """希尔排序"""
        lis = self.r
        length = len(lis)
        increment = len(lis)
        while increment > 1:
            increment = int(increment/3)+1
            for i in range(increment+1, length):
                if lis[i] < lis[i - increment]:
                    temp = lis[i]
                    j = i - increment
                    while j >= 0 and temp < lis[j]:
                        lis[j+increment] = lis[j]
                        j -= increment
                    lis[j+increment] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22])
    sqlist.shell_sort()
    print(sqlist)

六、堆排序

堆是具有下列性质的一心二叉树:
各类分支节点的值都大于或等于其左右子女的值,称为大顶堆;
种种分支节点的值都低于或等于其做右孩子的值,称为小顶堆;
就此,其根节点肯定是具备节点中最大(最小)的值。

假使依照层序遍历的章程(广度优先)给节点从1方始编号,则节点之间满意如下事关:

堆排序(Heap
Sort)正是采纳大顶堆或小顶堆的性子实行排序的艺术。堆排序的完整时间复杂度为O(nlogn)。(上面选拔大顶堆的方法)

其大旨绪想是:将待排序的队列构形成多少个大顶堆。此时,整个系列的最大值便是堆的根节点。将它与堆数组的结尾成分调换,然后将剩余的n-1个体系重新布局成二个大顶堆。一再施行后面包车型地铁操作,最终获得三个平稳连串。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 堆排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def heap_sort(self):
        length = len(self.r)
        i = int(length/2)
        # 将原始序列构造成一个大顶堆
        # 遍历从中间开始,到0结束,其实这些是堆的分支节点。
        while i >= 0:
            self.heap_adjust(i, length-1)
            i -= 1
        # 逆序遍历整个序列,不断取出根节点的值,完成实际的排序。
        j = length-1
        while j > 0:
            # 将当前根节点,也就是列表最开头,下标为0的值,交换到最后面j处
            self.swap(0, j)
            # 将发生变化的序列重新构造成大顶堆
            self.heap_adjust(0, j-1)
            j -= 1

    def heap_adjust(self, s, m):
        """核心的大顶堆构造方法,维持序列的堆结构。"""
        lis = self.r
        temp = lis[s]
        i = 2*s
        while i <= m:
            if i < m and lis[i] < lis[i+1]:
                i += 1
            if temp >= lis[i]:
                break
            lis[s] = lis[i]
            s = i
            i *= 2
        lis[s] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
    sqlist.heap_sort()
    print(sqlist)

 

堆排序的运行时刻主要消耗在开端创设堆和重新建立堆的频繁筛选上。
其开始创设堆时间复杂度为O(n)。
规范排序时,重新创建堆的时刻复杂度为O(nlogn)。
由此堆排序的欧洲经济共同体时间复杂度为O(nlogn)。

堆排序对原始记录的排序状态不灵活,由此它不管最棒、最坏和平均时间复杂度都以O(nlogn)。在性质上要好于冒泡、简单采用和直接插入算法。

空间复杂度上,只供给七个用来沟通的暂存单元。可是出于记录的相比和调换是跳跃式的,由此,堆排序也是一种动荡的排序方法。

其余,由于最早创设堆的相比次数比较多,堆排序不切合连串个数非常少的排序专门的学问。

 

驷不如舌共享Python 及Django教程以及相关的博客


参谋书目:《大话数据结构》

七、归并排序

归并排序(Merging
Sort):创设在联合操作上的一种有效的排序算法,该算法是使用分治法(Divide
and
Conquer)的三个老大卓越的使用。将已平稳的子系列合併,获得完全有序的队列;即先使各种子种类有序,再使子系列段间有序。若将七个静止表合併成贰个不改变表,称为二路归并。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 归并排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def merge_sort(self):
        self.msort(self.r, self.r, 0, len(self.r)-1)

    def msort(self, list_sr, list_tr, s, t):
        temp = [None for i in range(0, len(list_sr))]
        if s == t:
            list_tr[s] = list_sr[s]
        else:
            m = int((s+t)/2)
            self.msort(list_sr, temp, s,  m)
            self.msort(list_sr, temp, m+1, t)
            self.merge(temp, list_tr, s, m, t)

    def merge(self, list_sr, list_tr, i, m,  n):
        j = m+1
        k = i
        while i <= m and j <= n:
            if list_sr[i] < list_sr[j]:
                list_tr[k] = list_sr[i]
                i += 1
            else:
                list_tr[k] = list_sr[j]
                j += 1

            k += 1
        if i <= m:
            for l in range(0, m-i+1):
                list_tr[k+l] = list_sr[i+l]
        if j <= n:
            for l in range(0, n-j+1):
                list_tr[k+l] = list_sr[j+l]

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23])
    sqlist.merge_sort()
    print(sqlist)

除此以外三个版本:

def merge(lfrom, lto, low, mid, high):
    """
    两段需要归并的序列从左往右遍历,逐一比较,小的就放到
    lto里去,lfrom下标+1,lto下标+1,然后再取,再比,再放,
    最后lfrom里的两段比完了,lto里留下的就是从小到大排好的一段。
    :param lfrom: 原来的列表
    :param lto: 缓存的列表
    :param low: 左边一段的开头下标
    :param mid: 左右两段的中间相隔的下标
    :param high: 右边一段的最右下标
    :return:
    """
    i, j, k = low, mid, low
    while i < mid and j < high:
        if lfrom[i] <= lfrom[j]:
            lto[k] = lfrom[i]
            i += 1
        else:
            lto[k] = lfrom[j]
            j += 1
        k += 1
    while i < mid:
        lto[k] = lfrom[i]
        i += 1
        k += 1
    while j < high:
        lto[k] = lfrom[j]
        j += 1
        k += 1


def merge_pass(lfrom, lto, llen, slen):
    """
    用来处理所有需要合并的段,这需要每段的长度,以及列表的总长。
    最后的if语句处理表最后部分不规则的情况。
    :param lfrom: 原来的列表
    :param lto: 缓存的列表
    :param llen: 列表总长
    :param slen: 每段的长度
    :return:
    """
    i = 0
    while i+2*slen < llen:
        merge(lfrom, lto, i, i+slen, i+2*slen)
        i += 2*slen
    if i+slen < llen:
        merge(lfrom, lto, i, i+slen, llen)
    else:
        for j in range(i, llen):
            lto[j] = lfrom[j]


def merge_sort(lst):
    """
    主函数。
    先安排一个同样大小的列表,作为辅助空间。
    然后在两个列表直接做往复的归并,每归并一次slen的长度增加一倍,
    逐渐向llen靠拢,当slen==llen时说明归并结束了。
    归并完成后最终结果可能恰好保存在templist里,因此代码里做两次归并,
    保证最后的结果体现在原始的lst列表里。
    :param lst: 要排序的原始列表
    :return:
    """
    slen, llen = 1, len(lst)
    templist = [None]*llen
    while slen < llen:
        merge_pass(lst, templist, llen, slen)
        slen *= 2
        merge_pass(templist, lst, llen, slen)
        slen *= 2
  • 归并排序对原有连串成分遍及景况不灵活,其时间复杂度为O(nlogn)。
  • 归并排序在测算进程中需求采取一定的帮忙空间,用于递归和寄放结果,由此其空间复杂度为O(n+logn)。

  • 归并排序中官样文章跳跃,唯有两两比较,因而是一种和睦排序。

简单来说,归并排序是一种相比较占用内部存储器,但作用高,并且稳定的算法。

 

六、堆排序

堆是颇具下列性质的一心二叉树:
各种分支节点的值都大于或等于其左右子女的值,称为大顶堆;
种种分支节点的值都自愧不及或等于其做右孩子的值,称为小顶堆;
故此,其根节点料定是兼具节点中最大(最小)的值。
图片 2
假定遵照层序遍历的方式(广度优先)给节点从1发轫编号,则节点之间满意如下事关:
图片 3

堆排序(Heap
Sort)就是运用大顶堆或小顶堆的属性举办排序的点子。堆排序的完整时间复杂度为O(nlogn)。(上面选取大顶堆的方法)

其核心绪想是:将待排序的队列构变成一个大顶堆。此时,整个体系的最大值就是堆的根节点。将它与堆数组的末尾成分调换,然后将剩余的n-1个类别重新布局成叁个大顶堆。反复施行前边的操作,最终获得二个一步一趋种类。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 堆排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def heap_sort(self):
        length = len(self.r)
        i = int(length/2)
        # 将原始序列构造成一个大顶堆
        # 遍历从中间开始,到0结束,其实这些是堆的分支节点。
        while i >= 0:
            self.heap_adjust(i, length-1)
            i -= 1
        # 逆序遍历整个序列,不断取出根节点的值,完成实际的排序。
        j = length-1
        while j > 0:
            # 将当前根节点,也就是列表最开头,下标为0的值,交换到最后面j处
            self.swap(0, j)
            # 将发生变化的序列重新构造成大顶堆
            self.heap_adjust(0, j-1)
            j -= 1

    def heap_adjust(self, s, m):
        """核心的大顶堆构造方法,维持序列的堆结构。"""
        lis = self.r
        temp = lis[s]
        i = 2*s
        while i <= m:
            if i < m and lis[i] < lis[i+1]:
                i += 1
            if temp >= lis[i]:
                break
            lis[s] = lis[i]
            s = i
            i *= 2
        lis[s] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
    sqlist.heap_sort()
    print(sqlist)

堆排序的运维时刻主要消耗在开班营造堆和重新建立堆的数11回筛选上。
其开端营造堆时间复杂度为O(n)。
标准排序时,重新创建堆的时刻复杂度为O(nlogn)。
进而堆排序的完全时间复杂度为O(nlogn)。

堆排序对原始记录的排序状态不灵动,因而它不管最佳、最坏和平均时间复杂度都是O(nlogn)。在性质上要好于冒泡、简单选拔和直接插入算法。

空中复杂度上,只需求叁个用于沟通的暂存单元。可是出于记录的相比和沟通是跳跃式的,由此,堆排序也是一种不安宁的排序方法。

其余,由于初叶创设堆的比较次数非常多,堆排序不吻合体系个数相当少的排序职业。

2. 回退不要求的置换

原来的代码中pivot_key这么些记录总是再持续的置换中,其实那是没供给的,完全能够将它暂存在某些不经常变量中,如下所示:

def partition(self, low, high):

        lis = self.r

        m = low + int((high-low)/2)
        if lis[low] > lis[high]:
            self.swap(low, high)
        if lis[m] > lis[high]:
            self.swap(high, m)
        if lis[m] > lis[low]:
            self.swap(m, low)

        pivot_key = lis[low]
        # temp暂存pivot_key的值
        temp = pivot_key
        while low < high:
            while low < high and lis[high] >= pivot_key:
                high -= 1
            # 直接替换,而不交换了
            lis[low] = lis[high]
            while low < high and lis[low] <= pivot_key:
                low += 1
            lis[high] = lis[low]
            lis[low] = temp
        return low

 

一、排序的基本概念和归类

所谓排序,正是使一串记录,遵照内部的某部或少数首要字的高低,递增或递减的排列起来的操作。排序算法,正是怎么样使得记录根据供给排列的点子。

排序的天下太平:
因而某种排序后,纵然多少个记录序号同等,且互相在原冬季记录中的前后相继秩序依旧维持不改变,则称所选用的排序方法是安静的,反之是不安宁的。

内排序和外排序
内排序:排序进程中,待排序的持有记录整个身处内部存款和储蓄器中
向外排水序:排序进度中,使用到了表面存款和储蓄。
普通研讨的都以内排序。

影响内排序算法性能的三个因素

  • 时光复杂度:即时间质量,高功能的排序算法应该是负有尽恐怕少的关键字相比较次数和著录的位移次数
  • 空中复杂度:首假如实施算法所急需的帮助空间,越少越好。
  • 算法复杂性。主倘诺指代码的头昏眼花。

依照排序进度中依靠的严重性操作,可把内排序分为:

  • 插入排序
  • 沟通排序
  • 选取排序
  • 归并排序

依照算法复杂度可分为两类:

  • 简易算法:蕴含冒泡排序、轻巧选用排序和直接插入排序
  • 创新算法:包涵Hill排序、堆排序、归并排序和高效排序

以下的种种排序算法只是有着排序算法中最优秀的二种,不代表整个。

九、排序算法计算

排序算法的归类:

从未白玉无瑕的算法,有有一点就能有弱点,虽然是飞速排序算法,也只是完好品质上的优厚,也设有排序不平稳,须要多量帮衬空间,不适于小量数码排序等劣势。

八种排序算法质量比较

  • 若果待排连串基本平稳,请直接选拔简便的算法,不要使用复杂的改进算法。
  • 归并排序和高效排序即便质量高,然而急需越来越多的扶助空间。其实便是用空间换时间。
  • 待排体系的要素个数越少,就越适合用简易的排序方法;成分个数越来越多就越适合用创新的排序算法。
  • 粗略接纳排序固然在时光质量上糟糕,但它在空中应用上品质极高。极其吻合,那多少个数据量相当的小,每条数据的新闻量又比非常多的一类元素的排序。

根源为知笔记(Wiz)

1. 优化增选的pivot_key

前边大家每一遍选择pivot_key的都以子种类的首先个因素,也正是lis[low],那就相比看运气。运气好时,该值处于整个连串的邻近中间值,则构造的树相比平衡,运气比较糟糕,处于最大或纤维地方紧邻则构造的树临近斜树。
为了保险pivot_key接纳的尽心方便,选取选拔连串左中右几个非凡地点的值中,处于中间值的那么些数为pivot_key,经常会比平昔用lis[low]要好一些。在代码中,在本来的pivot_key
= lis[low]这一行前边扩大下边包车型地铁代码:

m = low + int((high-low)/2)
if lis[low] > lis[high]:
    self.swap(low, high)
if lis[m] > lis[high]:
    self.swap(high, m)
if lis[m] > lis[low]:
    self.swap(m, low)

尽管以为这么还非常不够好,还是能够将全方位类别先划分为3部分,每一部分求出个pivot_key,再对3个pivot_key再做三次地点的相比得出最后的pivot_key。这时的pivot_key应该不小约率是二个相比可信赖的值。

四、直接插入排序

直接插入排序(Straight Insertion Sort):时间复杂度O(n^2)
基本操作是将贰个记下插入到已经排好序的不改变表中,进而赢得三个新的、记录数增1的有序表。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 直接插入排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def insert_sort(self):
        lis = self.r
        length = len(self.r)
        # 下标从1开始
        for i in range(1, length):
            if lis[i] < lis[i-1]:
                temp = lis[i]
                j = i-1
                while lis[j] > temp and j >= 0:
                    lis[j+1] = lis[j]
                    j -= 1
                lis[j+1] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
    sqlist.insert_sort()
    print(sqlist)

该算法要求二个笔录的帮带空间。最佳状态下,当原始数据就是有序的时候,只必要一轮比较,无需活动记录,此时光阴复杂度为O(n)。但是,那基本是异想天开。

 

3. 优化小数组时的排序

火速排序算法的递归操作在进展大气数据排序时,其支付能被接受,速度异常的快。但进行小数组排序时则不比直接插入排序来得快,相当于杀鸡用牛刀,未必就比菜刀来得快。
所以,一种很节省的做法正是依照数据的有些,做个使用哪一类算法的选用而已,如下改写qsort方法:

def qsort(self, low, high):
    """根据序列长短,选择使用快速排序还是简单插入排序"""
    # 7是一个经验值,可根据实际情况自行决定该数值。
    MAX_LENGTH = 7
    if high-low < MAX_LENGTH:
        if low < high:
            pivot = self.partition(low, high)
            self.qsort(low, pivot - 1)
            self.qsort(pivot + 1, high)
    else:
        # insert_sort方法是我们前面写过的简单插入排序算法
        self.insert_sort()

八、连忙排序

飞速排序(Quick Sort)由图灵奖获得者托尼Hoare发明,被列为20世纪十大算法之一。冒泡排序的提高版,交流排序的一种。火速排序的时日复杂度为O(nlog(n))。

高效排序算法的核心理想:通过一趟排序将待排记录分割成独立的两有个别,在那之中部分记下的首要性字均比另一有个别记录的严重性字小,然后分别对这两片段继续张开排序,以完结任何记录集结的排序目标。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 快速排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def quick_sort(self):
        """调用入口"""
        self.qsort(0, len(self.r)-1)

    def qsort(self, low, high):
        """递归调用"""
        if low < high:
            pivot = self.partition(low, high)
            self.qsort(low, pivot-1)
            self.qsort(pivot+1, high)

    def partition(self, low, high):
        """
        快速排序的核心代码。
        其实就是将选取的pivot_key不断交换,将比它小的换到左边,将比它大的换到右边。
        它自己也在交换中不断变换自己的位置,直到完成所有的交换为止。
        但在函数调用的过程中,pivot_key的值始终不变。
        :param low:左边界下标
        :param high:右边界下标
        :return:分完左右区后pivot_key所在位置的下标
        """
        lis = self.r
        pivot_key = lis[low]
        while low < high:
            while low < high and lis[high] >= pivot_key:
                high -= 1
            self.swap(low, high)
            while low < high and lis[low] <= pivot_key:
                low += 1
            self.swap(low, high)
        return low

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
    sqlist.quick_sort()
    print(sqlist)

除此以外二个版本:

def quick_sort(nums):
    # 封装一层的目的是方便用户调用
    def qsort(lst, begin, end):
        if begin >= end:
            return
        i = begin
        key = lst[begin]
        for j in range(begin+1, end+1):
            if lst[j] < key:
                i += 1
                lst[i], lst[j] = lst[j], lst[i]
        lst[begin], lst[i] = lst[i], lst[begin]
        qsort(lst, begin, i-1)
        qsort(lst,i+1,end)
    qsort(nums, 0, len(nums)-1)

 
  • 高效排序的岁月质量取决于递归的深度。
  • 当pivot_key恰好处于记录关键码的高级中学级值时,大小两区的分开相比较均匀,临近三个平衡二叉树,此时的小时复杂度为O(nlog(n))。
  • 当原记录群集是三个正序或逆序的情形下,分区的结果正是一棵斜树,其深度为n-1,每二次举办大小分区,都要动用n-i次相比较,其最后时间复杂度为O(n^2)。
  • 在形似情状下,通过数学归咎法可表明,快速排序的年月复杂度为O(nlog(n))。
  • 唯独由于关键字的可比和调换是跳跃式的,由此,火速排序是一种不安定排序。
  • 而且由于采取的递归技艺,该算法须求肯定的帮带空间,其空间复杂度为O(logn)。

上面是二个实例测验数据:

测试数据量(个) 100 1000 10000 100000 1000000
冒泡 0.001 0.11 11s
反序冒泡 0.001 0.14 14s
快速排序 0.001 0.003~0.004 0.040~0.046 0.51~0.53 6.36~6.56s

从数据中可知:

  • 多少过万,冒泡算法基本不可用。测量试验时间忠实的呈现了n平方的年月复杂度,数据增添10倍,耗费时间扩张100倍
  • 对于Python的列表,反序遍历比正序遍历照旧要开销一定的日子的
  • 快快排序在数码非常大时,其威力显现,但远远不够牢固,总体照旧尊崇了nlog(n)的复杂度。

大旨的火速排序还会有能够优化的地点:

 

九、排序算法总括

排序算法的归类:
图片 4

并未有白璧无瑕的算法,有有一点点就能不符合规律,纵然是飞快排序算法,也只是完全质量上的巨惠,也存在排序不稳固,须要大量支援空间,不适于一丢丢数量排序等弱点。

多样排序算法质量比较

图片 5

  • 比如待排体系基本不变,请间接选取轻松的算法,不要使用复杂的精耕细作算法。
  • 归并排序和急速排序尽管品质高,可是要求越来越多的鼎力相助空间。其实正是用空间换时间。
  • 待排系列的要素个数越少,就越适合用简易的排序方法;成分个数越来越多就越适合用立异的排序算法。
  • 简易选拔排序纵然在时刻品质上倒霉,但它在半空中利用上品质相当高。特别符合,那多少个数据量比不大,每条数据的消息量又相当多的一类元素的排序。

三、轻便选取排序

简言之采用排序(simple selection sort):时间复杂度O(n^2)
通过n-i次首要字里面包车型地铁可比,从n-i+1个记录中选出第一字非常的小的记录,并和第i(1<=i<=n)个记录进行置换。

通俗的说正是,对尚未产生排序的具备因素,彻彻底底比贰回,记录下纤维的十三分成分的下标,也正是该因素的职分。再把该因素交流到近期遍历的最后面。其作用之处在于,每一轮中相比了无多次,但只沟通一遍。因而就算它的时刻复杂度也是O(n^2),但比冒泡算法照旧要好一些。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 简单选择排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def select_sort(self):
        """
        简单选择排序,时间复杂度O(n^2)
        """
        lis = self.r
        length = len(self.r)
        for i in range(length):
            minimum = i
            for j in range(i+1, length):
                if lis[minimum] > lis[j]:
                    minimum = j
            if i != minimum:
                self.swap(i, minimum)

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
    sqlist.select_sort()
    print(sqlist)

 

七、归并排序

归并排序(Merging
Sort):创建在集结操作上的一种有效的排序算法,该算法是运用分治法(Divide
and
Conquer)的叁个特别规范的接纳。将已板上钉钉的子系列合并,获得完全有序的种类;即先使各样子连串有序,再使子类别段间有序。若将五个不改变表合併成一个静止表,称为二路归并。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 归并排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def merge_sort(self):
        self.msort(self.r, self.r, 0, len(self.r)-1)

    def msort(self, list_sr, list_tr, s, t):
        temp = [None for i in range(0, len(list_sr))]
        if s == t:
            list_tr[s] = list_sr[s]
        else:
            m = int((s+t)/2)
            self.msort(list_sr, temp, s,  m)
            self.msort(list_sr, temp, m+1, t)
            self.merge(temp, list_tr, s, m, t)

    def merge(self, list_sr, list_tr, i, m,  n):
        j = m+1
        k = i
        while i <= m and j <= n:
            if list_sr[i] < list_sr[j]:
                list_tr[k] = list_sr[i]
                i += 1
            else:
                list_tr[k] = list_sr[j]
                j += 1

            k += 1
        if i <= m:
            for l in range(0, m-i+1):
                list_tr[k+l] = list_sr[i+l]
        if j <= n:
            for l in range(0, n-j+1):
                list_tr[k+l] = list_sr[j+l]

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23])
    sqlist.merge_sort()
    print(sqlist)

除此以外贰个本子:

def merge(lfrom, lto, low, mid, high):
    """
    两段需要归并的序列从左往右遍历,逐一比较,小的就放到
    lto里去,lfrom下标+1,lto下标+1,然后再取,再比,再放,
    最后lfrom里的两段比完了,lto里留下的就是从小到大排好的一段。
    :param lfrom: 原来的列表
    :param lto: 缓存的列表
    :param low: 左边一段的开头下标
    :param mid: 左右两段的中间相隔的下标
    :param high: 右边一段的最右下标
    :return:
    """
    i, j, k = low, mid, low
    while i < mid and j < high:
        if lfrom[i] <= lfrom[j]:
            lto[k] = lfrom[i]
            i += 1
        else:
            lto[k] = lfrom[j]
            j += 1
        k += 1
    while i < mid:
        lto[k] = lfrom[i]
        i += 1
        k += 1
    while j < high:
        lto[k] = lfrom[j]
        j += 1
        k += 1


def merge_pass(lfrom, lto, llen, slen):
    """
    用来处理所有需要合并的段,这需要每段的长度,以及列表的总长。
    最后的if语句处理表最后部分不规则的情况。
    :param lfrom: 原来的列表
    :param lto: 缓存的列表
    :param llen: 列表总长
    :param slen: 每段的长度
    :return:
    """
    i = 0
    while i+2*slen < llen:
        merge(lfrom, lto, i, i+slen, i+2*slen)
        i += 2*slen
    if i+slen < llen:
        merge(lfrom, lto, i, i+slen, llen)
    else:
        for j in range(i, llen):
            lto[j] = lfrom[j]


def merge_sort(lst):
    """
    主函数。
    先安排一个同样大小的列表,作为辅助空间。
    然后在两个列表直接做往复的归并,每归并一次slen的长度增加一倍,
    逐渐向llen靠拢,当slen==llen时说明归并结束了。
    归并完成后最终结果可能恰好保存在templist里,因此代码里做两次归并,
    保证最后的结果体现在原始的lst列表里。
    :param lst: 要排序的原始列表
    :return:
    """
    slen, llen = 1, len(lst)
    templist = [None]*llen
    while slen < llen:
        merge_pass(lst, templist, llen, slen)
        slen *= 2
        merge_pass(templist, lst, llen, slen)
        slen *= 2
  • 归并排序对原有类别成分遍布意况不敏感,其时间复杂度为O(nlogn)。
  • 归并排序在总计进度中须求利用一定的帮手空间,用于递归和寄放结果,因而其空间复杂度为O(n+logn)。

  • 归并排序中海市蜃楼跳跃,唯有两两相比,因而是一种和煦排序。

一句话来讲,归并排序是一种相比占用内部存款和储蓄器,但作用高,何况稳固的算法。

3. 优化小数组时的排序

敏捷排序算法的递归操作在举行大气数目排序时,其开荒能被接受,速度非常快。但实行小数组排序时则比不上直接插入排序来得快,相当于杀鸡用牛刀,未必就比菜刀来得快。
就此,一种很朴素的做法正是根据数量的多少,做个使用哪一种算法的选用而已,如下改写qsort方法:

def qsort(self, low, high):
    """根据序列长短,选择使用快速排序还是简单插入排序"""
    # 7是一个经验值,可根据实际情况自行决定该数值。
    MAX_LENGTH = 7
    if high-low < MAX_LENGTH:
        if low < high:
            pivot = self.partition(low, high)
            self.qsort(low, pivot - 1)
            self.qsort(pivot + 1, high)
    else:
        # insert_sort方法是我们前面写过的简单插入排序算法
        self.insert_sort()

 

4. 优化递归操作

能够动用尾递归的艺术对全体算法的递归操作进行优化,改写qsort方法如下:

def qsort(self, low, high):
    """根据序列长短,选择使用快速排序还是简单插入排序"""
    # 7是一个经验值,可根据实际情况自行决定该数值。
    MAX_LENGTH = 7
    if high-low < MAX_LENGTH:
        # 改用while循环
        while low < high:
            pivot = self.partition(low, high)
            self.qsort(low, pivot - 1)
            # 采用了尾递归的方式
            low = pivot + 1
    else:
        # insert_sort方法是我们前面写过的简单插入排序算法
        self.insert_sort()

八、急迅排序

高效排序(Quick Sort)由图灵奖获得者TonyHoare发明,被列为20世纪十大算法之一。冒泡排序的晋级版,调换排序的一种。急迅排序的岁月复杂度为O(nlog(n))。

敏捷排序算法的核激情想:通过一趟排序将待排记录分割成单身的两有的,个中一部分笔录的要紧字均比另一部分记录的首要字小,然后分别对这两有的继续扩充排序,以高达全体记录集结的排序目标。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 快速排序


class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法,方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def quick_sort(self):
        """调用入口"""
        self.qsort(0, len(self.r)-1)

    def qsort(self, low, high):
        """递归调用"""
        if low < high:
            pivot = self.partition(low, high)
            self.qsort(low, pivot-1)
            self.qsort(pivot+1, high)

    def partition(self, low, high):
        """
        快速排序的核心代码。
        其实就是将选取的pivot_key不断交换,将比它小的换到左边,将比它大的换到右边。
        它自己也在交换中不断变换自己的位置,直到完成所有的交换为止。
        但在函数调用的过程中,pivot_key的值始终不变。
        :param low:左边界下标
        :param high:右边界下标
        :return:分完左右区后pivot_key所在位置的下标
        """
        lis = self.r
        pivot_key = lis[low]
        while low < high:
            while low < high and lis[high] >= pivot_key:
                high -= 1
            self.swap(low, high)
            while low < high and lis[low] <= pivot_key:
                low += 1
            self.swap(low, high)
        return low

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
    sqlist.quick_sort()
    print(sqlist)

除此以外三个本子:

def quick_sort(nums):
    # 封装一层的目的是方便用户调用
    def qsort(lst, begin, end):
        if begin >= end:
            return
        i = begin
        key = lst[begin]
        for j in range(begin+1, end+1):
            if lst[j] < key:
                i += 1
                lst[i], lst[j] = lst[j], lst[i]
        lst[begin], lst[i] = lst[i], lst[begin]
        qsort(lst, begin, i-1)
        qsort(lst,i+1,end)
    qsort(nums, 0, len(nums)-1)
  • 快快排序的年华品质取决于递归的深浅。
  • 当pivot_key恰好处于记录关键码的中游值时,大小两区的分开相比较均匀,接近三个平衡二叉树,此时的时日复杂度为O(nlog(n))。
  • 当原记录会集是一个正序或逆序的气象下,分区的结果便是一棵斜树,其深度为n-1,每贰遍实践大小分区,都要利用n-i次相比,其最终时间复杂度为O(n^2)。
  • 在形似景色下,通过数学总结法可表明,飞速排序的时光复杂度为O(nlog(n))。
  • 不过出于首要字的相比和置换是跳跃式的,因而,快速排序是一种不安静排序。
  • 再者鉴于采用的递归才干,该算法要求自然的扶植空间,其空间复杂度为O(logn)。

上边是七个实例测量试验数据:

测试数据量(个) 100 1000 10000 100000 1000000
冒泡 0.001 0.11 11s
反序冒泡 0.001 0.14 14s
快速排序 0.001 0.003~0.004 0.040~0.046 0.51~0.53 6.36~6.56s

从数额中可见:

  • 数据过万,冒泡算法基本不可用。测验时间忠实的映现了n平方的年华复杂度,数据扩张10倍,耗费时间扩张100倍
  • 对于Python的列表,反序遍历比正序遍历依然要开支一定的时刻的
  • 迅猛排序在数据相当大时,其威力显现,但远远不够稳固,总体依然爱戴了nlog(n)的复杂度。

主干的高速排序还应该有能够优化的地点:

相关文章