Python 기반의 7가지 고전적인 정렬 알고리즘에 대한 자세한 소개

1. 정렬의 기본 개념 및 분류

소위 정렬은 하나 또는 일부 키워드의 크기에 따라 일련의 레코드를 오름차순 또는 내림차순으로 배열하는 것입니다. 일어나세요. 정렬 알고리즘은 필요에 따라 레코드를 정렬하는 방법입니다.

정렬의 안정성:

일부 정렬 후에도 두 레코드의 일련번호가 동일하고 순서가 없는 원본 레코드의 두 레코드 순서가 그대로 유지되는 경우 일관되지 않은 변경이 있는 경우 사용된 정렬 방법은 안정적이라고 하며, 그렇지 않으면 불안정하다고 합니다.

내부 정렬 및 외부 정렬

내부 정렬: 정렬 과정에서 정렬할 모든 레코드가 메모리에 저장됩니다.

외부 정렬: 정렬 이 과정에서 외부 저장소가 사용됩니다.

보통 논의되는 것은 내부 정렬입니다.

내부 정렬 알고리즘의 성능에 영향을 미치는 세 가지 요소:

시간 복잡도: 즉, 시간 성능, 효율적인 정렬 알고리즘은 가능한 한 적은 수의 키워드를 가져야 합니다. 비교 횟수와 기록된 동작 횟수

공간 복잡성: 주로 알고리즘을 실행하는 데 필요한 보조 공간이 적을수록 좋습니다.

알고리즘 복잡성. 주로 코드의 복잡성을 나타냅니다.

정렬 과정에서 사용되는 주요 작업에 따라 내부 정렬은 다음과 같이 나눌 수 있습니다.

삽입 정렬

교환 정렬

선택 정렬

병합 정렬

은 알고리즘 복잡도에 따라 두 가지 범주로 나눌 수 있습니다.

단순 알고리즘: 버블 정렬 포함, 단순 선택 정렬 및 직접 삽입 정렬

향상된 알고리즘: Hill 정렬, 힙 정렬, 병합 정렬 및 빠른 정렬 포함

다음 7가지 정렬 알고리즘은 모든 정렬 알고리즘 중에서 가장 고전적일 뿐이며 이를 대표하지 않습니다. 모두.

2. 버블 정렬

버블 정렬(Bubble sort): 시간 복잡도 O(n^2)

A 교환 정렬 유형. 핵심 아이디어는 인접한 레코드의 키워드를 쌍으로 비교하고, 역순인 레코드가 없을 때까지 역순인 경우 교환하는 것입니다.

구현 세부 사항은 다음 세 가지와 같이 다를 수 있습니다.

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 == &#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. 간단한 선택 정렬

간단한 선택 정렬(간단한 선택) sort): 시간복잡도 O(n^2)

키워드 간 n-i 비교를 통해 n-i+1 레코드 중 가장 작은 키워드를 갖는 레코드를 선택하고 i번째 레코드(1
비공개 용어로 아직 정렬되지 않은 모든 요소를 ​​처음부터 끝까지 비교하고 가장 작은 요소의 첨자, 즉 요소의 위치를 ​​기록합니다. 그런 다음 요소를 현재 순회 앞쪽으로 바꿉니다. 효율성은 각 라운드가 여러 번 비교되지만 한 번만 교환된다는 사실에 있습니다. 따라서 시간 복잡도도 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)

4. 직선 삽입 정렬

직선 삽입 정렬: 시간 복잡도 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 == &#39;main&#39;:
  sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
  sqlist.insert_sort()
  print(sqlist)

이 알고리즘에는 기록을 위한 보조 공간이 필요합니다. 가장 좋은 경우에는 원본 데이터가 순서대로 있을 때 한 번의 비교만 필요하며 레코드를 이동할 필요가 없습니다. 이 경우 시간 복잡도는 O(n)입니다. 그러나 이것은 기본적으로 환상이다.



5. 쉘 정렬

쉘 정렬은 삽입 정렬의 개선된 버전입니다. 데이터 세트 를 여러 하위 시퀀스로 만든 다음 하위 시퀀스에 대해 직접 삽입 정렬을 수행하여 하위 시퀀스를 기본적으로 순서대로 만듭니다. 마지막으로 모든 레코드에 대해 직접 삽입 정렬을 수행합니다.

여기서 가장 중요한 것은 점프와 분할 전략, 즉 데이터를 어떻게 분할하고 간격이 얼마나 큰지입니다. 일반적으로 특정 "증분"으로 분리된 레코드는 하위 시퀀스로 형성되어 하위 시퀀스 내에서 직접 삽입 정렬 후 얻은 결과가 부분적으로 정렬되지 않고 기본적으로 정렬되도록 합니다. 다음 예에서 "increment" 값은 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 == &#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()

九、排序算法总结

排序算法的分类：




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

七种排序算法性能对比



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

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

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

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

위 내용은 Python 기반의 7가지 고전적인 정렬 알고리즘에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!