基于Python的七大经典排序算法是什么

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

所谓排序，就是将一串记录按照一个或几个关键字的大小进行升序或降序排列的操作。排序算法就是如何让记录按要求排列。

排序的稳定性：

经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。

内排序和外排序

内排序：排序过程中，待排序的所有记录全部放在内存中

外排序：排序过程中，使用到了外部存储。

通常讨论的都是内排序。

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

时间复杂度：即时间性能。一个高效的排序算法应该有尽可能少的关键字比较和记录移动。空间复杂度：主要是执行算法所需的辅助空间，越少越好。算法复杂性。主要是指代码的复杂度。

根据分拣过程中使用的主要操作，内部分拣可分为：

插入排序交换排序选择排序归并排序

按照算法复杂度可分为两类：

简单算法：包括冒泡排序、简单选择排序和直接插入排序改进算法：包括希尔排序、堆排序、归并排序和快速排序

下面的七种排序算法只是所有排序算法中最经典的，不是全部。

二、 冒泡排序

冒泡排序（Bubble sort）：时间复杂度O(n^2)

交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。

其实现细节可以不同，比如下面3种：

最简单排序实现:bubble_sort_simple

冒泡排序:bubble_sort

改进的冒泡排序: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 retif __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)

简单选择排序（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 retif __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
    sqlist.select_sort()
    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 retif __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
    sqlist.insert_sort()
    print(sqlist)

该算法需要一个记录的辅助空间。最好情况下，当原始数据就是有序的时候，只需要一轮对比，不需要移动记录，此时时间复杂度为O(n)。然而，这基本是幻想。

五、希尔排序

Shell 排序是插入排序的改进版本。它的核心思想是将原始数据集分成若干个子序列，然后直接对子序列进行插入排序，使子序列基本有序。记录按插入排序一次。

这里最关键的是跳跃和分裂的策略，也就是我们如何分裂数据，间隔有多大。通常，以一定“增量”隔开的记录组成一个子序列，以保证子序列中直接插入排序后得到的结果基本是有序的，而不是偏序的。在以下示例中，“increment”的值由以下公式确定：increment = int(increment/3)+1。

希尔排序的时间复杂度为：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)。在性能上优于冒泡、简单选择和直接插入算法。

在空间复杂度上，交换只需要一个临时存储单元。但是由于记录的比较交换是跳跃式的，所以堆排序也是一种不稳定的排序方式。

另外，由于堆的初始构建时比较次数较多，堆排序不适合序列数量少的排序任务。

七、归并排序

合并排序（Merging Sort）：一种基于合并操作的有效排序算法，是分治法的一个非常典型的应用。将有序的子序列组合起来，得到一个完全有序的序列；即先把每个子序列排好序，再把子序列段排好序。将两个排序列表合并为一个排序列表称为双向合并。

#!/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 += 1def 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)。

归并排序没有跳跃，只有两两比较，所以是稳定排序。

简而言之，归并排序是一种相对占用内存但高效且稳定的算法。

八、快速排序

快速排序（Quick Sort）由图灵奖得主托尼·霍尔发明，被列为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)。

下面是一个实例测试数据：

从数据中可见：

如果数据超过10000条，冒泡算法基本没法用了。测试时间忠实反映n平方的时间复杂度，数据放大10倍，耗时增加100倍。对于Python列表，逆序遍历还是会比正序遍历消耗一定的时间。数据量大时快速排序，威力可见一斑，但不够稳定，整体复杂度维持在nlog(n)。

基本的快速排序还有可以优化的地方：

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应该是一个比较靠谱的值，概率比较大。

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

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()

九、排序算法总结

排序算法的分类：

没有完美的算法，有一点点就会有不足之处。即使是快速排序算法，也只是综合性能优越，也存在排序不稳定、需要大量辅助空间、不适合小数据量排序等缺点。

七种排序算法性能对比

如果待排序的列基本有序，请直接使用简单算法，不要使用复杂的改进算法。归并排序和快速排序虽然性能高，但需要更多的辅助空间。其实就是用空间换时间。需要排序的列中的元素个数越少，越适合使用简单的排序方式；元素个数越多，越适合使用改进的排序算法。简单选择排序虽然在时间性能上不佳，但在空间利用率上却有很高的性能。特别适用于数据量小，每条数据中信息量大的元素排序。