プログラマーがマスターしなければならないソート アルゴリズムのトップ 10 (パート 1)

書籍の問題の紹介

ソートアルゴリズムすべてのプログラマーがマスターした後に必ず持っていると言えるでしょう。 、その原理と実装を理解する必要があります。.以下は、学習を容易にする、最も一般的に使用される 10 個の並べ替えアルゴリズムの Python 実装の紹介です。 . .

#01 バブル ソート——交換ソート#02 クイック ソート——交換ソート

03 選択ソート —— 選択ソート 04 ヒープ ソート —— クラスの選択sort

05 挿入ソート—挿入クラス sort

06 丘選別-挿入選別

#07 併合選別-併合選別

##08 計数選別-分布のソート

09 基数ソート-分散ソート

10 バケットソート-分散ソート

01

##リスクバブルソート

#バブルソート:

古典的なソートアルゴリズムがその名前の由来ですアルゴリズムの動作中に、水中の泡のように極端な値が徐々に現れるためです。

#アルゴリズム原理:

隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。

• 隣接する要素の各ペアに対して、最初のペアから始めて最後のペアで終わるまで、同じことを実行します。この時点では、最後の要素が最大の数値である必要があります。

• # 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

• 比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

#コードは以下のように表示されます:

'''冒泡排序'''
def Bubble_Sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Bubble_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]

##02

クイックソート

クイックソート:

並べ替えるデータを 1 回の並べ替えで 2 つの独立した部分に分割してから、これを使用しますデータの 2 つの部分をそれぞれすばやく並べ替える方法です。並べ替えプロセス全体を再帰的に実行できるため、データ全体が順序付けされたシーケンスになります。これはバブル ソート アルゴリズムの改良点です。

#アルゴリズム原理:

まず分割値を設定し、この分割値によって配列を左右に分割します。

• 配列の右側のカットオフ値以上のデータと、カットオフ値未満のデータを収集します。 off 値は配列の左側に集中します。このとき、左側の各要素は除算値以下、右側の各要素は除算値以上となります。

• #これにより、左右のデータを独立して並べ替えることができます。左側の配列データについては、分割値を取得してデータのこの部分を左右に分割し、同様に、小さい値を左側に、大きい値を右側に配置します。右側の配列データも同様に処理できます。

• # 左側と右側の部分のデータがソートされるまで、上記のプロセスを繰り返します。

#コードは以下のように表示されます。

'''快速排序'''
def Quick_Sort(arr):
    # 递归入口及出口
    if len(arr) >= 2:
        # 选取基准值，也可以选取第一个或最后一个元素
        mid = arr[len(arr) // 2]
        # 定义基准值左右两侧的列表
        left, right = [], []
        # 从原始数组中移除基准值
        arr.remove(mid)
        for num in arr:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return Quick_Sort(left) + [mid] + Quick_Sort(right)
    else:
        return arr

arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

#03

#並べ替えの選択

##選択ソート

: これは、シンプルで直感的なソート アルゴリズムです。 どのようなデータが入力されても、時間計算量は O(n²) です。したがって、使用する場合はデータサイズが小さいほど良いです。

#アルゴリズム原理:

未並べ替えのシーケンスで最小の (大きな) 要素を見つけ、それを並べ替え済みのシーケンスの開始位置に保存します。

• 引き続き、ソートされていない残りの要素から最小 (最大) の要素を検索し、それをソートされたシーケンスの最後に置きます。

• すべての要素が並べ替えられるまで、これを繰り返します。

代码如下：

'''选择排序'''
def Selection_Sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30]
result = Quick_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

04

插入排序

插入排序（Insertion Sort）：一般也被称为直接插入排序，是一种最简单直观的排序算法。

算法原理：

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码如下：

'''插入排序'''
def Insertion_Sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Insertion_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

05

堆排序

堆排序（Heap sort）：是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

算法原理：

• 创建一个堆 H[0……n-1]；
  

• 把堆首（最大值）和堆尾互换；

• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

• 重复步骤 2，直到堆的尺寸为 1。

代码如下：

'''堆排序'''
def Heapify(arr, n, i):
    largest = i
    # 左右节点分块
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        # 大小值交换
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归
        Heapify(arr, n, largest)

def Heap_Sort(arr):
    nlen = len(arr)
    for i in range(nlen, -1, -1):
        # 调整节点
        Heapify(arr, nlen, i)
    for i in range(nlen - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # 调整节点
        Heapify(arr, i, 0)
    return arr

arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75]
result = Heap_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]

以上がプログラマーがマスターしなければならないソート アルゴリズムのトップ 10 (パート 1)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。