Sepuluh algoritma pengisihan teratas yang mesti dikuasai oleh pengaturcara (Bahagian 1)

Pengenalan kepada isu ini

algoritma pengisihan Boleh dikatakan setiap pengaturcara mesti menguasainya Perlu memahami prinsip dan pelaksanaannya Berikut adalah pengenalan kepada pelaksanaan ular sawa bagi sepuluh algoritma pengisihan yang biasa digunakan untuk memudahkan pembelajaran anda.

01 Isih Buih - Isih Pertukaran 02 Isih Pantas - Isih Pertukaran
Pilih

Isih 04 Isih timbunan - isihan pilihan

05 Isih sisipan - isihan sisipan

06 Isih sisipan

🎜08 Isih mengira - isihan pengedaran 🎜🎜

09 Isih Radix - isihan pengedaran

10 Isih baldi - isihan pengedaran

01

Isih Gelembung

Isih Buih: Algoritma pengisihan klasik:
secara beransur-ansur muncul seperti buih di dasar air, oleh itu namanya. . Jika yang pertama lebih besar daripada yang kedua, tukar kedua-duanya.

Lakukan perkara yang sama untuk setiap pasangan elemen bersebelahan, bermula dengan pasangan pertama di awal dan berakhir dengan pasangan terakhir di penghujung. Pada ketika ini, elemen terakhir hendaklah nombor terbesar.

Ulang langkah di atas untuk semua elemen kecuali yang terakhir.

Teruskan mengulangi langkah di atas untuk semakin sedikit elemen setiap kali sehingga tiada pasangan nombor untuk dibandingkan.

Kod adalah seperti berikut:

'''冒泡排序'''
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

Cepat Isih

Isih Pantas:

Keseluruhan proses pengisihan boleh dilakukan secara rekursif, supaya keseluruhan data menjadi urutan tertib, yang merupakan penambahbaikan pada algoritma pengisihan gelembung.

Algoritma Prinsip:

First menetapkan nilai pemisah, dan bahagikan array ke bahagian kiri dan kanan melalui nilai pemisah ini.

• Tumpukan data yang lebih besar daripada atau sama dengan nilai cutoff ke sebelah kanan tatasusunan dan data lebih kecil daripada nilai cutoff ke sebelah kiri tatasusunan. Pada masa ini, setiap elemen di bahagian kiri adalah kurang daripada atau sama dengan nilai pembahagian, dan setiap elemen di bahagian kanan lebih besar daripada atau sama dengan nilai pembahagian.

• Kemudian, data di kiri dan kanan boleh diisih secara bebas. Untuk data tatasusunan di sebelah kiri, anda boleh mengambil nilai pembahagian dan membahagikan bahagian data ini kepada bahagian kiri dan kanan Begitu juga, letakkan nilai yang lebih kecil di sebelah kiri dan nilai yang lebih besar di sebelah kanan. Data tatasusunan di sebelah kanan juga boleh diproses dengan cara yang sama.

• Ulang proses di atas sehingga data di bahagian kiri dan kanan disusun. Kod adalah seperti berikut:

03

Isihan pilihan

: Ia adalah pengisihan yang Mudah dan intuitif algoritma.

Tidak kira apa data yang dimasukkan, kerumitan masa ialah O(n²). Jadi apabila menggunakannya, lebih kecil saiz data, lebih baik.

Prinsip algoritma:

unsur yang paling kecil

simpannya pada kedudukan permulaan urutan yang disusun. .

• Dan seterusnya sehingga semua elemen disusun.

代码如下：

'''选择排序'''
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]

Atas ialah kandungan terperinci Sepuluh algoritma pengisihan teratas yang mesti dikuasai oleh pengaturcara (Bahagian 1). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!