Detaillierte Einführung in sieben klassische Sortieralgorithmen auf Basis von Python

1. Grundkonzepte und Klassifizierungen der Sortierung

Die sogenannte Sortierung besteht darin, eine Reihe von Datensätzen in aufsteigender oder absteigender Reihenfolge entsprechend der Größe eines oder mehrerer Schlüsselwörter anzuordnen es. Aufstehen. Der Sortieralgorithmus ist eine Methode zum Anordnen von Datensätzen nach Bedarf.

Stabilität der Sortierung:

Wenn nach einer gewissen Sortierung die Seriennummern zweier Datensätze gleich sind und die Reihenfolge der beiden Datensätze im ursprünglichen ungeordneten Datensatz erhalten bleibt Bei inkonsistenten Änderungen gilt die verwendete Sortiermethode als stabil, andernfalls ist sie instabil.

Innere Sortierung und äußere Sortierung

Innere Sortierung: Während des Sortiervorgangs werden alle zu sortierenden Datensätze im Speicher abgelegt

Äußere Sortierung: Sortieren Dabei wird externer Speicher genutzt.

Normalerweise wird über innere Sortierung gesprochen.

Drei Faktoren, die die Leistung des internen Sortieralgorithmus beeinflussen:

Zeitkomplexität: Das heißt, Zeitleistung, ein effizienter Sortieralgorithmus sollte so wenige Schlüsselwörter wie möglich haben Die Anzahl der Vergleiche und die Anzahl der aufgezeichneten Züge

Raumkomplexität: Hauptsächlich der für die Ausführung des Algorithmus erforderliche Hilfsraum, je weniger, desto besser.

Algorithmuskomplexität. Bezieht sich hauptsächlich auf die Komplexität des Codes.

Entsprechend den Hauptoperationen, die im Sortierprozess verwendet werden, kann die interne Sortierung unterteilt werden in:

Einfügungssortierung

Austauschsortierung

Auswahlsortierung

Zusammenführungssortierung

kann je nach Algorithmuskomplexität in zwei Kategorien unterteilt werden:

Einfacher Algorithmus: einschließlich Blasensortierung, einfache Auswahl Sortierung und Direkteinfügungssortierung

Verbesserte Algorithmen: einschließlich Hill-Sortierung, Heap-Sortierung, Zusammenführungssortierung und Schnellsortierung

Die folgenden sieben Sortieralgorithmen sind nur die klassischsten aller Sortieralgorithmen und stellen keine dar alle.

2. Blasensortierung

Blasensortierung (Bubble sortieren): Zeitkomplexität O(n^2)

A Art der Börsensortierung. Die Kernidee besteht darin, die Schlüsselwörter benachbarter Datensätze paarweise zu vergleichen und sie auszutauschen, wenn sie in umgekehrter Reihenfolge vorliegen, bis keine Datensätze in umgekehrter Reihenfolge mehr vorhanden sind.

Die Implementierungsdetails können unterschiedlich sein, wie zum Beispiel die folgenden drei:

1. Die einfachste Sortierimplementierung: bubble_sort_simple

2. Blasensortierung: bubble_sort

3. Verbesserte Blasensortierung: 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 == &#39;main&#39;:
  sqlist = SQList([4,1,7,3,8,5,9,2,6])
  # sqlist.bubble_sort_simple()
  # sqlist.bubble_sort()
  sqlist.bubble_sort_advance()
  print(sqlist)

3. Einfache Auswahlsortierung

Einfache Auswahlsortierung ( einfache Auswahlsortierung): Zeitkomplexität O(n^2)

Wählen Sie durch n-i-Vergleiche zwischen Schlüsselwörtern den Datensatz mit dem kleinsten Schlüsselwort aus n-i+1 Datensätzen aus und summieren Sie ihn. Das i (1<= i<=n) Datensatz wird ausgetauscht.

Um es für Laien auszudrücken: Alle Elemente, die noch nicht sortiert wurden, werden von Anfang bis Ende verglichen und der Index des kleinsten Elements wird aufgezeichnet, was die Position des Elements darstellt. Tauschen Sie dann das Element an der Vorderseite des aktuellen Durchlaufs aus. Die Effizienz liegt darin, dass jede Runde viele Male verglichen, aber nur einmal ausgetauscht wird. Obwohl seine zeitliche Komplexität ebenfalls O (n ^ 2) ist, ist er dennoch besser als der Blasenalgorithmus.

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

4. Straight Insertion Sort

Straight Insertion Sort: Zeitkomplexität O(n^2)

Der Grundvorgang besteht darin, einen Datensatz in eine bereits sortierte geordnete Liste einzufügen, wodurch eine neue geordnete Liste mit einer um 1 erhöhten Anzahl von Datensätzen entsteht.

#!/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 == &#39;main&#39;:
  sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
  sqlist.insert_sort()
  print(sqlist)

Dieser Algorithmus erfordert zusätzlichen Speicherplatz für einen Datensatz. Im besten Fall, wenn die Originaldaten in Ordnung sind, ist nur eine Vergleichsrunde erforderlich und es müssen keine Datensätze verschoben werden. In diesem Fall beträgt die Zeitkomplexität O(n). Dies ist jedoch im Grunde eine Fantasie.



5. Shell Sort ist eine verbesserte Version der Einfügungssortierung Datensatz
in mehrere Teilsequenzen aufteilen und dann eine direkte Einfügungssortierung für die Teilsequenzen durchführen, um die Teilsequenzen grundsätzlich zu ordnen. Führen Sie schließlich eine direkte Einfügungssortierung für alle Datensätze durch.
Das Wichtigste hierbei ist die Strategie des Springens und Teilens, also wie wir die Daten aufteilen und wie groß das Intervall ist. Normalerweise werden Datensätze, die um ein bestimmtes „Inkrement“ voneinander getrennt sind, zu einer Teilsequenz zusammengefasst, um sicherzustellen, dass die nach der direkten Einfügungssortierung innerhalb der Teilsequenz erhaltenen Ergebnisse grundsätzlich geordnet und nicht teilweise geordnet sind. Im folgenden Beispiel wird der Wert von „Inkrement“ bestimmt durch: Inkrement = int(Inkrement/3)+1.
Die zeitliche Komplexität der Hill-Sortierung beträgt: 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 == &#39;main&#39;:
  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 == &#39;main&#39;:
  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）：建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide 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 == &#39;main&#39;:
  sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23])
  sqlist.merge_sort()
  print(sqlist)

归并排序对原始序列元素分布情况不敏感，其时间复杂度为O(nlogn)。

归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为O(n+logn)。

归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。

总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。

八、快速排序

快速排序（Quick Sort）由图灵奖获得者Tony 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 == &#39;main&#39;:
  sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
  sqlist.quick_sort()
  print(sqlist)

快速排序的时间性能取决于递归的深度。

当pivot_key恰好处于记录关键码的中间值时，大小两区的划分比较均衡，接近一个平衡二叉树，此时的时间复杂度为O(nlog(n))。

当原记录集合是一个正序或逆序的情况下，分区的结果就是一棵斜树，其深度为n-1，每一次执行大小分区，都要使用n-i次比较，其最终时间复杂度为O(n^2)。

在一般情况下，通过数学归纳法可证明，快速排序的时间复杂度为O(nlog(n))。

但是由于关键字的比较和交换是跳跃式的，因此，快速排序是一种不稳定排序。

同时由于采用的递归技术，该算法需要一定的辅助空间，其空间复杂度为O(logn)。

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

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

九、排序算法总结

排序算法的分类：




没有十全十美的算法，有有点就会有缺点，即使是快速排序算法，也只是整体性能上的优越，也存在排序不稳定，需要大量辅助空间，不适于少量数据排序等缺点。

七种排序算法性能对比



 如果待排序列基本有序，请直接使用简单的算法，不要使用复杂的改进算法。

 归并排序和快速排序虽然性能高，但是需要更多的辅助空间。其实就是用空间换时间。

 待排序列的元素个数越少，就越适合用简单的排序方法；元素个数越多就越适合用改进的排序算法。

 简单选择排序虽然在时间性能上不好，但它在空间利用上性能很高。特别适合，那些数据量不大，每条数据的信息量又比较多的一类元素的排序。

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in sieben klassische Sortieralgorithmen auf Basis von Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!