Python の 8 つのソート アルゴリズムのまとめ (パート 2)

この記事は主に Python で実装された 8 つのソート アルゴリズムの後半を詳しく紹介します。興味のある方は参考にしてください。 Python を使用して、8 つの主要なソート アルゴリズムのうち残りの 4 つを実装します: クイック ソート、ヒープ ソート、マージ ソート、基数ソート

5、クイック ソート

クイック ソートは一般に同じ桁であると考えられます ( O(nlog2n) ) は、ソート方法の中で最も平均的なパフォーマンスが優れています。

アルゴリズムのアイデア:

順序付けされていないデータ a[1]、a[2]、...a[n] のセットが既知であり、昇順に配置する必要があります。まず、任意のデータ a[x] がベンチマークとして使用されます。 a[x]を他のデータと比較し、a[x]がデータのk番目に位置するように並べ替え、各データをa[1]~a[k-1]a[x] の各データを分割し、それぞれ a[1]~a[k-1] と a[k+1]~a に分割統治戦略を使用します。 [n] 2 セットのデータをすばやく並べ替えます。

利点: 非常に高速で、データ移動が少ない。

欠点: 不安定。

Python コードの実装:

def quick_sort(list):
  little = []
  pivotList = []
  large = []
  # 递归出口
  if len(list) <= 1:
    return list
  else:
    # 将第一个值做为基准
    pivot = list[0]
    for i in list:
      # 将比基准小的值放到less数列
      if i < pivot:
        little.append(i)
      # 将比基准大的值放到more数列
      elif i > pivot:
        large.append(i)
      # 将和基准相同的值保存在基准数列
      else:
        pivotList.append(i)
    # 对less数列和more数列继续进行快速排序
    little = quick_sort(little)
    large = quick_sort(large)
    return little + pivotList + large

次のコードは、Python クイック ソートを実装するための「Python クックブック 第 2 版」の 3 行からのものです。

#!/usr/bin/env python
#coding:utf-8
'''
file:python-8sort.py
date:9/1/17 9:03 AM
author:lockey
email:lockey@123.com
desc:python实现八大排序算法
'''
lst = [65,568,9,23,4,34,65,8,6,9]
def quick_sort(list):
  if len(list) <= 1:
    return list
  else:
    pivot = list[0]
    return quick_sort([x for x in list[1:] if x < pivot]) + \
        [pivot] + \
        quick_sort([x for x in list[1:] if x >= pivot])

実行中のテスト結果のスクリーンショット:

わかりました。すべて 1 行にまとめられた、より合理化された糖衣構文があります:

quick_sort = lambda xs : ( (len(xs) <= 1 and [ xs]) または [quick_sort( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + Quick_sort( [x for x in xs[1:] if x > ;= xs[0]] ) ] )[0]

初期シーケンスがキー順または基本的に順序付けされている場合、クイックソートはバブルソートに縮退します。これを改善するために、ベンチマーク レコードの選択には通常「スリーインワン方式」が使用されます。つまり、2 つのエンドポイントとソート間隔の中点を中心とする 3 つのレコード キーが支点レコードとして調整されます。クイックソートは不安定な並べ替え方法です。

改良されたアルゴリズムでは、長さが k より大きいサブシーケンスに対してのみクイック ソートを再帰的に呼び出して、元のシーケンスを基本的に順序付けし、その後、挿入ソート アルゴリズムを使用して基本的な順序付けシーケンス全体を並べ替えます。実践により、改良されたアルゴリズムの時間計算量が軽減され、k の値が約 8 のときに改良されたアルゴリズムのパフォーマンスが最高になることが証明されています。

6. ヒープソート

ヒープソートはツリー選択ソートであり、直接選択ソートを効果的に改良したものです。

長所: 高効率

短所: 不安定

ヒープの定義の下: (hi>=h2i,hi> =2i の場合に限り) n 要素のシーケンス (h1, h2,...,hn) +1) または (hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)、これはヒープと呼ばれます。ここでは、前者の条件を満たすヒープのみを説明します。ヒープの定義から、ヒープの最上位要素 (つまり、最初の要素) が最大の項目 (ビッグトップ ヒープ) でなければならないことがわかります。完全なバイナリ ツリーは、ヒープの構造を非常に直観的に表現できます。ヒープの最上位はルートであり、その他は左のサブツリーと右のサブツリーです。

アルゴリズムの考え方:

まず、ソート対象の数値列を順番に格納された二分木とみなし、その格納順序を調整してヒープ化します。このとき、ヒープのルートノードの数が決まります。は最もおおきい。次に、ルート ノードをヒープの最後のノードと交換します。次に、以前の (n-1) 個の数値を再調整してヒープを形成します。以下同様に、ノードが 2 つだけのヒープが存在し、それらが交換され、最終的には n 個のノードの順序付けられたシーケンスが取得されます。アルゴリズムの説明から、ヒープのソートには 2 つのプロセスが必要です。1 つはヒープを確立することで、もう 1 つはヒープの先頭とヒープの最後の要素の間の位置を交換することです。したがって、ヒープソートは 2 つの関数で構成されます。 1 つはヒープを構築するペネトレーション関数、もう 1 つはペネトレーション関数を繰り返し呼び出してソートを実現する関数です。

Pythonコードの実装:

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
lst = [65,568,9,23,4,34,65,8,6,9]
def adjust_heap(lists, i, size):# 调整堆
  lchild = 2 * i + 1;rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)
def build_heap(lists, size):# 创建堆
  halfsize = int(size/2)
  for i in range(0, halfsize)[::-1]:
    adjust_heap(lists, i, size)
def heap_sort(lists):# 堆排序
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)
    print(lists)

結果の例:

7. マージソート

アルゴリズムのアイデア:

マージ操作に基づく効果的なアルゴリズムです。これは、分割統治法を使用する非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。

マージプロセスは次のとおりです: a[i] と a[j] のサイズを比較し、a[i]≤a[j] の場合、最初の順序付きリストの要素 a[i] を r[k ] にコピーします。それ以外の場合は、2 番目の順序付けされたリストの要素 a[j] を r[k] にコピーし、j と k にそれぞれ 1 を追加するというように、順序付きリストの 1 つがフェッチされるまで続きます。 、次に、もう一方の順序付きリストの残りの要素を、r の下付き文字 k から下付き文字 t までのセルにコピーします。通常、再帰を使用してマージ ソート アルゴリズムを実装します。まず、ソート対象の区間 [s, t] が中点で 2 つに分割され、次に左側のサブ範囲がソートされ、次に右側のサブ範囲がソートされます。最後に、左側の間隔と右側の間隔がマージされ、順序付けられた間隔 [s,t] になります。

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
lst = [65,568,9,23,4,34,65,8,6,9]
def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  print(result)
  return result
def merge_sort(lists):# 归并排序
  if len(lists) <= 1:
    return lists
  num = int(len(lists) / 2)
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

プログラム結果の例:

8、桶排序/基数排序(Radix Sort)

优点：快，效率最好能达到O(1)
缺点：

1.首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

2.其次待排序的元素都要在一定的范围内等等。

算法思想：

是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先，可以把桶大小设为10，这样就有100个桶了，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。

然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。

最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

python代码实现：

# -*- coding: UTF-8 -*-
'''
Created on 2017年9月2日
Running environment：win7.x86_64 eclipse python3
@author: Lockey
'''
import math
lst = [65,56,9,23,84,34,8,6,9,54,11]
#因为列表数据范围在100以内，所以将使用十个桶来进行排序
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      gg = int(j/(radix**(i-1))) % (radix**i)
      bucket[gg].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
      print(lists)
  return lists

程序运行测试结果：

以上がPython の 8 つのソート アルゴリズムのまとめ (パート 2)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。