Pythonは8大ソートアルゴリズム(転載)+バケツソート(オリジナル)を実現
ソートアルゴリズムの重要性は言うまでもない.ここで1編抜粋して、ここに転載して、学習鑑賞に供する.
ソートの挿入
核心思想.
ソートを挿入する基本的な操作は、1つのデータを並べ替えられたソートデータに挿入し、新しい、個数に1を加えたソートデータを得ることであり、アルゴリズムは少量のデータのソートに適用され、時間複雑度はO(n^2)である.安定したソート方法です.挿入アルゴリズムは、ソートする配列を2つの部分に分けます.第1の部分には、この配列のすべての要素が含まれていますが、最後の要素を除いて(配列の複数の空間に挿入された位置があるようにします)、第2の部分には、この要素(すなわち、挿入される要素)しか含まれていません.最初の部分のソートが完了したら、最後の要素をソートされた最初の部分に挿入します.
コード実装
def insert_sort(lists):
#
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return listsヒルソート
核心思想.
ヒルソート(Shell Sort)は、ソートを挿入するものです.インクリメンタルソートの縮小とも呼ばれ、ソートアルゴリズムを直接挿入するより効率的な改良バージョンです.ヒルソートは非安定ソートアルゴリズムである.この方法はDL.Shellが1959年に提案したことから名付けられた.ヒルソートは、レコードを下付きの一定の増分でグループ化し、各グループに対して直接挿入ソートアルゴリズムを使用してソートする.増分が減少するにつれて、各グループに含まれるキーワードはますます多くなり、増分が1に減少すると、ファイル全体がグループに分けられ、アルゴリズムは終了する.
コード実装
def shell_sort(lists):
#
count = len(lists)
step = 2
group = count / step
while group > 0:
for i in range(0, group):
j = i + group
while j < count:
k = j - group
key = lists[j]
while k >= 0:
if lists[k] > key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return listsバブルソート
核心思想.
ソートする数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.数列を訪問する作業は、交換が必要になるまで繰り返し、すなわち、その数列がソートされるまで行われる.
コード実装
def bubble_sort(lists):
#
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
lists[i], lists[j] = lists[j], lists[i]
return listsクイックソート
核心思想.
1回のソートでソートするデータを独立した2つの部分に分割し、一部のすべてのデータが他の部分のすべてのデータよりも小さくなり、この方法で2つの部分のデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行うことで、データ全体が秩序化されたシーケンスになるようにします.
コード実装
def quick_sort(lists, left, right):
#
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists直接選択ソート
核心思想.
基本思想:第1回目は、ソート待ち記録r 1~r[n]の中から最小の記録を選択し、r 1と交換する.2回目は、ソート対象レコードr 2~r[n]の中から最小のレコードを選択し、r 2と交換する.このように,i回目はソート対象レコードr[i]~r[n]の中で最小のレコードを選択し,r[i]と交換し,すべてのソートが完了するまで秩序シーケンスを成長させる.
コード実装
def select_sort(lists):
#
count = len(lists)
for i in range(0, count):
min = i
for j in range(i + 1, count):
if lists[min] > lists[j]:
min = j
lists[min], lists[i] = lists[i], lists[min]
return listsヒープのソート
核心思想.
スタックソート(Heapsort)とは、スタックツリー(スタック)というデータ構造を用いて設計されたソートアルゴリズムであり、ソートを選択するものである.配列の特徴を使用して、指定したインデックスの要素をすばやく配置できます.山は大根の山と小根の山に分かれていて、完全に二叉木です.ルートスタックの要件は、各ノードの値が親ノードの値より大きくないことです.すなわち、A[PROD[i]>=A[i]です.配列の非降順ソートでは、大きなスタックが使用される必要があります.大きなスタックの要求によって、最大の値は必ずスタックの頂上にあることがわかります.
コード実装
#
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):
for i in range(0, (size/2))[::-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)集計ソート
核心思想.
集計ソートは集計操作に確立された有効なソートアルゴリズムであり,このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの順序テーブルを1つの順序テーブルに結合すると、2ウェイ集計と呼ばれます.
集計プロセスは、a[i]とa[j]のサイズを比較し、a[i]≦a[j]の場合、最初の秩序テーブルの要素a[i]をr[k]にコピーし、iとkにそれぞれ1を加算する.そうでなければ、2番目の順序テーブルの要素a[j]をr[k]にコピーし、jとkにそれぞれ1を加算し、そのうちの1つの順序テーブルが終わるまでループし、その後、別の順序テーブルの残りの要素をrの下付きkから下付きtのユニットにコピーする.集計ソートのアルゴリズムは通常再帰的に実現され,まずソート対象区間[s,t]を中点二分し,次に左サブ区間をソートし,右サブ区間をソートし,最後に左区間と右区間を一次集計操作で秩序ある区間[s,t]に統合する.
コード実装
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:]
return result
def merge_sort(lists):
#
if len(lists) <= 1:
return lists
num = len(lists) / 2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)ベースソート
核心思想.
基数ソート(radix sort)は「分配式ソート」(distribution sort)に属し、「バケツ法」(bucket sort)またはbin sortとも呼ばれる.名前の通り、キー値の一部の情報を通して、ソートする要素をいくつかの「バケツ」に割り当て、ソートの役割を果たすために、基数ソート法は安定性のソートに属し、その時間複雑度はO(nlog(r)m)である.ここで、rは採用された基数であり、mはスタック数であり、場合によっては、基数ソート法の効率は他の安定性ソート法よりも高い.
コード実装
import math
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:
bucket[j/(radix**(i-1)) % (radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists以上、他の人のよく使うソートアルゴリズムを転載しましたが、もちろんソートアルゴリズムの実現についてはまだまだたくさんありますが、ここでは「バケツソート」に関する小さな例を書いてみましょう.
バケツソート
核心思想.
スペースと時間を節約するには、ソートするデータの最小値と最大値を指定して、便器ソートアルゴリズムの演算を行う必要があります.
コード実装
# coding:utf-8
import sys
reload(sys)
sys.setdefaultencoding('utf8')
# __author__ = ' '
# __date__ = '2016/9/6'
# __Desc__ = ，
def sort(arr):
result = []
for index in range(0,len(arr)):
result.append(0)
for index in range(len(arr)):
counter = result[arr[index]]+1
result[arr[index]]=counter
return result
if __name__ == '__main__':
arr = [1,3,5,7,9,2,9,4,6,8,0,1,1,3,2,2,2,2]
arr = sort(arr)
for item in range(len(arr)):
if arr[item]!=0:
step = arr[item]
while step>0:
print item,
step-=1テスト結果
D:\Software\Python2\python.exe E:/Code/Python/DataStructor/temp/BarrelSort.py
0 1 1 1 2 2 2 2 2 3 3 4 5 6 7 8 9 9
Process finished with exit code 0
まとめ
以上、大牛が完成した古典的な8大ソートアルゴリズムと、自分が実現した簡単なバケツソートに関する小さなケースを紹介した.