Python は 8 つの並べ替えアルゴリズムを実装します

Python を使用して 8 つの主要な並べ替えアルゴリズムを実装する方法

1. 挿入並べ替え
説明
挿入並べ替えの基本的な操作は、並べ替えられた順序付けされたデータにデータを挿入して、新しいデータを取得することです。順序付けされたデータの数に 1 を加えたものであり、このアルゴリズムは少量のデータを並べ替えるのに適しており、時間計算量は O(n^2) です。安定した選別方法です。挿入アルゴリズムは、ソートされる配列を 2 つの部分に分割します。最初の部分には、最後の要素を除く配列のすべての要素が含まれます (配列に挿入位置を追加するためのスペースが 1 つ増えます)。2 番目の部分には、この要素のみが含まれます。 1 つの要素 (つまり、挿入される要素)。最初の部分がソートされた後、この最後の要素がソートされた最初の部分に挿入されます。
コードの実装

 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

2. ヒルソート
説明
シェルソートは挿入ソートの一種です。これは削減増分ソートとも呼ばれ、直接挿入ソート アルゴリズムのより効率的かつ改良されたバージョンです。ヒル ソートは、不安定なソート アルゴリズムです。この方法はDLによるものです。シェルは 1959 年に提案されたことにちなんで名付けられました。 ヒル ソートでは、添字の特定の増分でレコードをグループ化し、直接挿入ソート アルゴリズムを使用して各グループをソートします。増分が徐々に減少するにつれて、各グループにはさらに多くのキーワードが含まれます。増分が 1 まで減少すると、ファイル全体がグループ化されます。ちょうど 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

3. バブルソート
説明
順序が間違っている場合は、一度に 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

4. クイックソート
説明
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

5. 直接選択ソート
説明
基本的な考え方: 最初のパスでは、ソートされるレコードの中で最小のものを選択します r1 ~ r[ n] レコードを r1 と交換し、2 番目のパスでソート対象のレコード r2 ~ r[n] の中で最小のレコードを選択し、それを r2 と交換します。並べ替えられるレコード 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

6. ヒープソート
説明
ヒープソートとは、スタックツリー(ヒープ)アルゴリズムなどのデータ構造を使用して設計されたソートを指します。選択ソートのタイプ。配列の特性を使用して、指定したインデックスにある要素をすばやく見つけることができます。ヒープは、大きなルート ヒープと小さなルート ヒープに分割され、完全なバイナリ ツリーになります。大規模なルート ヒープの要件は、各ノードの値がその親ノードの値以下であること、つまり A[PARENT[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)

7、归并排序
描述 
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一 个有序表，称为二路归并。 
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否 则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上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)

8、基数排序
描述 
基数排序（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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Python实现八大排序算法相关文章请关注PHP中文网！