基于python的七种经典排序算法的详细介绍

#!/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 = 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)

#!/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)

#!/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]  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)

#!/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 &gt; 1:      increment = int(increment/3)+1      for i in range(increment+1, length):        if lis[i] = 0 and temp <p><br><br><strong>六、堆排序</strong><br><br>堆是具有下列性质的完全二叉树：<br><br>每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆；<br><br>每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆；<br><br>因此，其根节点一定是所有节点中最大（最小）的值。<br><br><img src="https://img.php.cn/upload/article/000/000/013/21120990cb4c62a8a092e2aec4afd2ac-1.png"    style="max-width:90%"  style="max-width:90%" title="基于python的七种经典排序算法的详细介绍" alt="基于python的七种经典排序算法的详细介绍"><br><br>如果按照层序遍历的方式（广度优先）给节点从1开始编号，则节点之间满足如下关系：<br><br><img src="https://img.php.cn/upload/article/000/000/013/3fe7f7d17341254a23e6dbf78c0f1c54-2.png"    style="max-width:90%"  style="max-width:90%" title="基于python的七种经典排序算法的详细介绍" alt="基于python的七种经典排序算法的详细介绍"><br><br>堆排序（Heap Sort）就是利用大顶堆或小顶堆的性质进行排序的方法。堆排序的总体时间复杂度为O(nlogn)。（下面采用大顶堆的方式）<br><br>其核心思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆的根节点。将它与堆<a href="http://www.php.cn/wiki/58.html" target="_blank">数组</a>的末尾元素交换，然后将剩余的n-1个序列重新构造成一个大顶堆。反复执行前面的操作，最后获得一个有序序列。<br><br></p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/00968c3c2c15" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">Python免费学习笔记（深入）</a>”；</p><pre class="brush:py;">#!/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 &gt;= 0:      self.heap_adjust(i, length-1)      i -= 1    # 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。    j = length-1    while j &gt; 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 = 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 retif name == 'main':  sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])  sqlist.heap_sort()  print(sqlist)

#!/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 <p><br><br>  归并排序对原始序列元素分布情况不敏感，其时间复杂度为O(nlogn)。<br><br>  归并排序在计算过程中需要使用一定的辅助空间，用于<a href="http://www.php.cn/wiki/80.html" target="_blank">递归</a>和存放结果，因此其空间复杂度为O(n+logn)。<br><br>  归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。<br><br>总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。<br><br><strong>八、快速排序</strong><br><br>快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。<br><br>快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。<br><br></p><pre class="brush:py;">#!/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 = pivot_key:        high -= 1      self.swap(low, high)      while low <p><br>  快速排序的时间性能取决于递归的深度。<br><br>  当pivot_key恰好处于记录关键码的中间值时，大小两区的划分比较均衡，接近一个平衡二叉树，此时的时间复杂度为O(nlog(n))。<br><br>  当原记录集合是一个正序或逆序的情况下，分区的结果就是一棵斜树，其深度为n-1，每一次执行大小分区，都要使用n-i次比较，其最终时间复杂度为O(n^2)。<br><br>  在一般情况下，通过数学归纳法可证明，快速排序的时间复杂度为O(nlog(n))。<br><br>  但是由于关键字的比较和交换是跳跃式的，因此，快速排序是一种不稳定排序。<br><br>  同时由于采用的递归技术，该算法需要一定的辅助空间，其空间复杂度为O(logn)。<br><br>基本的快速排序还有可以优化的地方：<br><br><strong>1. 优化选取的pivot_key</strong><br><br>前面我们每次选取pivot_key的都是子序列的第一个元素，也就是lis[low]，这就比较看运气。运气好时，该值处于整个序列的靠近中间值，则构造的树比较平衡，运气比较差，处于最大或最小位置附近则构造的树接近斜树。<br><br> 为了保证pivot_key选取的尽可能适中，采取选取序列左中右三个特殊位置的值中，处于中间值的那个数为pivot_key，通常会比直接用lis[low]要好一点。在代码中，在原来的pivot_key = lis[low]这一行前面增加下面的代码：<br><br></p><pre class="brush:py;">m = low + int((high-low)/2)if lis[low] &gt; lis[high]:  self.swap(low, high)if lis[m] &gt; lis[high]:  self.swap(high, m)if lis[m] &gt; lis[low]:  self.swap(m, low)

def partition(self, low, high):        lis = self.r    m = low + int((high-low)/2)    if lis[low] &gt; lis[high]:      self.swap(low, high)    if lis[m] &gt; lis[high]:      self.swap(high, m)    if lis[m] &gt; lis[low]:      self.swap(m, low)    pivot_key = lis[low]    # temp暂存pivot_key的值    temp = pivot_key    while low = pivot_key:        high -= 1      # 直接替换，而不交换了      lis[low] = lis[high]      while low <p><br><br><strong>3. 优化小数组时的排序</strong><br><br>快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小<a href="http://www.php.cn/code/54.html" target="_blank">数组排序</a>时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。<br><br>因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：<br><br></p><pre class="brush:py;">def qsort(self, low, high):  """根据序列长短，选择使用快速排序还是简单插入排序"""  # 7是一个经验值，可根据实际情况自行决定该数值。  MAX_LENGTH = 7  if high-low <p><br><strong>4. 优化递归操作</strong><br><br>可以采用尾递归的方式对整个算法的递归操作进行优化，改写qsort方法如下：<br><br></p><pre class="brush:py;">def qsort(self, low, high):  """根据序列长短，选择使用快速排序还是简单插入排序"""  # 7是一个经验值，可根据实际情况自行决定该数值。  MAX_LENGTH = 7  if high-low <p><br><br><strong>九、排序算法总结</strong><br><br>排序算法的分类：<br><br><img src="https://img.php.cn/upload/article/000/000/013/1e2dbb39919f4c6662cdb3944ff82a1e-3.png"    style="max-width:90%"  style="max-width:90%" title="基于python的七种经典排序算法的详细介绍" alt="基于python的七种经典排序算法的详细介绍"><br><br><br>没有十全十美的算法，有有点就会有缺点，即使是快速排序算法，也只是整体性能上的优越，也存在排序不稳定，需要大量辅助空间，不适于少量数据排序等缺点。<br><br><strong>七种排序算法性能对比</strong><br><br><img src="https://img.php.cn/upload/article/000/000/013/05ff1ac0bb5e8cf204176e7d6f79b764-4.png"    style="max-width:90%"  style="max-width:90%" title="基于python的七种经典排序算法的详细介绍" alt="基于python的七种经典排序算法的详细介绍"><br><br>  如果待排序列基本有序，请直接使用简单的算法，不要使用复杂的改进算法。<br><br>  归并排序和快速排序虽然性能高，但是需要更多的辅助空间。其实就是用空间换时间。<br><br>  待排序列的元素个数越少，就越适合用简单的排序方法；元素个数越多就越适合用改进的排序算法。<br><br>  简单选择排序虽然在时间性能上不好，但它在空间利用上性能很高。特别适合，那些数据量不大，每条数据的信息量又比较多的一类元素的排序。<br><br></p>