算法是程式的靈魂,而排序算法是算法的入門經典,作者在此用python親自實作了7種主流的排序算法,并做簡短的說明.

排序算法

學習難度:

桶排序 < 冒泡排序 < 選擇排序 < 插入排序 < 快速排序 < 歸并排序 < 希爾排序

桶排序(簡化版)

桶排序:

将清單中最大數與最小數之間的數全部做成标簽,貼到N個桶上

将每個元素放到對應值的桶裡面(如果有M個相同的元素值,則将M個元素全部放到相應的桶中,取的時候占用M個位置)

最後按照桶編号的先後順序,從桶中依次取出值,排列完成

__author__ = 'zhaozhao'

def pail_sort(my_list):

    max_num = max(my_list)
    min_num = min(my_list)

    Y_list = list()

    for i in range(min_num, max_num+1):
        zhao_list = [i, 0]
        Y_list.append(zhao_list)

    for m in my_list:
        for Y in Y_list:
            if Y[0] == m:
                Y[1] += 1

    result = list()

    for n in Y_list:
        for t in range(0, n[1]):
            result.append(n[0])


    return result

    pass


def main():

    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("簡單桶排序之前的序列:", Y_list)
    print("簡單桶排序之後的序列:", pail_sort(Y_list))


if __name__ == '__main__':
    main()

冒泡排序

冒泡排序:

有N個待排序元素

1.設定遊标,遊标帶領第一個元素開始,與右側元素(第1個元素)比較,如果大于右側元素,則二者交換數值,然後遊标帶領元素繼續向右移動，如果小于右側元素,則不進行交換，遊标繼續向右移動，當遊标移動到清單最右側，第一輪比較就完成了（共比較N-1次）

2.然後遊标回到起始位置，開始第二輪比較，由于最後一個元素已經确定大于剩餘的元素是以(第二輪共比較N-2)次。

3.由于每次都隻能選取出一個最大值,是以N個元素的數組,進行N-1輪對比即可完成排列

__author__ = 'zhaozhao'

def bubble_sort(my_list):

    N = len(my_list)
    # 循環的次數
    circle_num = N-1

    while circle_num > 0:
        # 初始的遊标值
        index_value = 0

        while index_value < circle_num:

            if my_list[index_value] < my_list[index_value+1]:
                pass
            else:
                my_list[index_value], my_list[index_value+1] = my_list[index_value + 1], my_list[index_value]

            # 遊标右移一個機關
            index_value += 1
            pass

        circle_num -= 1

    print("冒泡排序之後的序列:",my_list)
    return my_list


def main():
    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("冒泡排序之前的序列:",Y_list)
    bubble_sort(Y_list)
    pass

if __name__ == '__main__':
    main()

選擇排序

選擇排序(升序):

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

__author__ = 'zhaozhao'

def selection_sort(my_list):

    # N為清單元素的個數
    N = len(my_list)

    circle_num = 0

    #需要進行N-1次循環
    while circle_num < N:

        # 每次循環開始的遊标索引值 為 circle_num , 結束的索引值為N-1
        for m in range(circle_num, N):
            if my_list[circle_num] <= my_list[m]:
                pass
            else:
                my_list[circle_num], my_list[m] = my_list[m], my_list[circle_num]



        circle_num += 1

    print("選擇排序之後的序列:",my_list)


def main():
    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("選擇排序之前的序列:",Y_list)
    selection_sort(Y_list)
    pass


if __name__ == '__main__':
    main()

插入排序

插入排序:

序列共有N個元素

将序列分為,已排序序列(第一個元素) 和未排序序列(除第一個元素以外的其它元素，共N-1個）兩部分,然後通過N-1輪循環,将N-1個元素,依次添加到已排序序列中

__author__ = 'zhaozhao'

def insert_sort(my_list):
    N = len(my_list)
    finish_list = list()
    f_len = len(finish_list)
    finish_list.append(my_list[0])
    # circle_num為待插入的值的索引
    for circle_num in range(1, N):
        for pre in range(0, circle_num):

            # 如果新加入的值比已排序的值小,就把新值加入到 已排序值的前面
            if my_list[circle_num] < finish_list[pre]:
                finish_list.insert(pre, my_list[circle_num])
                break

            # 如果新加入的值比已排序的序列最大的值都大,那麼
            elif my_list[circle_num] >= finish_list[-1]:
                finish_list.append(my_list[circle_num])

                break
            # 如果新加入的值 比已排序的某個值大但比 已排序後面的值小
            elif my_list[circle_num] >= finish_list[pre] and my_list[circle_num] < finish_list[pre+1]:
                finish_list.insert(pre+1, my_list[circle_num])
                break
            else:
                pass



    return finish_list


def main():
    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("插入排序之前的序列:", Y_list)
    insert_sort(Y_list)
    print("插入排序之後的序列:", insert_sort(Y_list))


if __name__ == '__main__':
    main()

快速排序(面試常用算法)

快速排序

1.選擇左側第一個元素為基準元素(其實基準元素可以是任意值,這裡選擇第一個是為了友善叙述)

建立兩個指針, 左側指針初始位置在清單首部,右側指針初始位置在清單尾部
先移動(為了保證,兩個指針相遇時,所在位置的元素不大于基準元素)右側指針(左移),當到達元素值小于基準值的位置停止(等待左側指針的支援)
移動左側指針(右移),當到達元素值大于基準值的位置停止,将此元素與右側指針當時所在位置的值互換.
互換元素後,右側指針繼續先移動, 循環 3,4步驟

6, 當左右指針相遇時, 将相遇位置的元素值與基準元素對調,完成第一輪循環

7, 此時,基準元素左側的值都小于基準值,基準元素右側的值都大于基準值

8, 遞歸調用上面的算法,将兩側的元素清單進行排序

9, 伴随着層層遞歸,新的基準值兩側的元素會越來越少,當基準值無兩側元素時,排序終止

__author__ = 'zhaozhao'

def q_sort(my_list, left, right):

    #設定左右指針
    left_point = left
    right_point = right
    stand_num = left

    if left > right:
        return

    while left_point != right_point:

        #先移動右指針,如果遇到 比基準值更小 的值,就停下來

        while (my_list[right_point] >= my_list[stand_num]) and (left_point < right_point):
            right_point -= 1

        # 再移動左指針,如果遇到比基準值更大的值,就停下來

        while (my_list[left_point] < my_list[stand_num]) and (left_point < right_point):
            left_point += 1

        # 找到了雙方可交換的點後, 開始交換

        my_list[left_point], my_list[right_point] = my_list[right_point],my_list[left_point]

        # 将基準點 與 指針相遇的點互換

        if left_point == right_point:
            my_list[stand_num], my_list[left_point] = my_list[left_point], my_list[stand_num]


        q_sort(my_list, left, left_point-1)
        q_sort(my_list, right_point+1, right)


    return (my_list)


def quick_sort(out_of_order):
    end = len(out_of_order) - 1
    start = 0
    q_sort(out_of_order, start, end)
    # print("排列完成的數組:",out_of_order)

    return out_of_order



def main():
    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("快速排序之前的序列:", Y_list)
    print("快速排序之後的序列:", quick_sort(Y_list))


if __name__ == '__main__':
    main()

歸并排序（先分後和, 分而治之）

歸并排序(python内置sort方法的實作原理):

歸并排序是典型的分治法排序，将待排序元素拆成多個分組，分組内部進行排序，然後分組進行合并，最終合并成完整的數組。

__author__ = 'zhaozhao'

# 負責 将清單拆分
def merge_sort(Y_list):

    if len(Y_list) <= 1:
        return Y_list

    # 先将未排序的清單進行分組
    num = len(Y_list) // 2

    left_list = merge_sort(Y_list[:num])
    right_list = merge_sort(Y_list[num:])

    # 将分組的清單交給merge函數, merge負責将清單合并
    return merge(left_list, right_list)


# 負責将清單合并
def merge(left, right):

    left_point = 0
    right_point = 0

    finish_list = list()

    while right_point < len(right) and left_point < len(left):

        if left[left_point] <= right[right_point]:
            finish_list.append(left[left_point])
            left_point += 1

        else:
            finish_list.append(right[right_point])
            right_point += 1

    finish_list += left[left_point:]
    finish_list += right[right_point:]

    return finish_list


def main():
    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("歸并排序之前的序列:", Y_list)
    print("歸并排序之後的序列:", merge_sort(Y_list))


if __name__ == '__main__':
    main()

希爾排序

希爾排序:

希爾排序是為優化插入排序,而建立的算法, 其核心思想是通過設定步長将元素分組，對每個分組進行快速排序,然後将步長減少,産生新的分組，對每個新分組進行快速排序，當步長減為1時,完成排序

__author__ = 'zhaozhao'

def shell_sort(Y_list):

    gap = len(Y_list)

    while gap >= 0:

        tem_list = list()

        if gap == 0:
            return Y_list

        # 将要抽取的值和索引儲存到一個 清單裡

        for index, value in enumerate(Y_list):
            if index % gap == 0:
                zhao_list = [index, value]
                tem_list.append(zhao_list)

        tem_value_list = list()

        for i in tem_list:
            tem_value_list.append(i[1])
        tem_value_list = insert_sort(tem_value_list)

        for i, vv in enumerate(tem_value_list):

            tem_list[i][1] = vv

        # 排序好的值  替換 原位置的值
        for iv in tem_list:

            Y_list[iv[0]] = iv[1]


        gap = gap // 2


    return Y_list


def insert_sort(my_list):
    N = len(my_list)
    finish_list = list()
    f_len = len(finish_list)
    finish_list.append(my_list[0])
    # circle_num為待插入的值的索引
    for circle_num in range(1, N):
        for pre in range(0, circle_num):

            # 如果新加入的值比已排序的值小,就把新值加入到 已排序值的前面
            if my_list[circle_num] < finish_list[pre]:
                finish_list.insert(pre, my_list[circle_num])
                break

            # 如果新加入的值比已排序的序列最大的值都大,那麼
            elif my_list[circle_num] >= finish_list[-1]:
                finish_list.append(my_list[circle_num])

                break
            # 如果新加入的值 比已排序的某個值大但比 已排序後面的值小
            elif my_list[circle_num] >= finish_list[pre] and my_list[circle_num] < finish_list[pre+1]:
                finish_list.insert(pre+1, my_list[circle_num])
                break
            else:
                pass



    return finish_list


def main():

    Y_list = [100, 54, 26, 63, 12, 22, 93, 17, 12, 77, 31, 44, 55, 20]
    print("希爾排序之前的序列:", Y_list)
    print("希爾排序之後的序列:", shell_sort(Y_list))


if __name__ == '__main__':
    main()

<算法入門>快速了解7種排序算法 | python3實作(附源碼)學習難度:桶排序(簡化版)冒泡排序選擇排序插入排序快速排序(面試常用算法)歸并排序（先分後和, 分而治之）希爾排序

算法是程式的靈魂,而排序算法是算法的入門經典,作者在此用python親自實作了7種主流的排序算法,并做簡短的說明.

學習難度:

桶排序 < 冒泡排序 < 選擇排序 < 插入排序 < 快速排序 < 歸并排序 < 希爾排序

桶排序(簡化版)

冒泡排序

選擇排序

插入排序

快速排序(面試常用算法)

歸并排序（先分後和, 分而治之）

希爾排序

繼續閱讀

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入

hdu7108哈希

&lt;算法入門&gt;快速了解7種排序算法 | python3實作(附源碼)學習難度:桶排序(簡化版)冒泡排序選擇排序插入排序快速排序(面試常用算法)歸并排序（先分後和, 分而治之）希爾排序

算法是程式的靈魂,而排序算法 是算法的入門經典,作者在此用python親自實作了7種主流的排序算法,并做簡短的說明.

學習難度:

桶排序 < 冒泡排序 < 選擇排序 < 插入排序 < 快速排序 < 歸并排序 < 希爾排序

桶排序(簡化版)

冒泡排序

選擇排序

插入排序

快速排序(面試常用算法)

歸并排序（先分後和, 分而治之）

希爾排序

繼續閱讀

<算法入門>快速了解7種排序算法 | python3實作(附源碼)學習難度:桶排序(簡化版)冒泡排序選擇排序插入排序快速排序(面試常用算法)歸并排序（先分後和, 分而治之）希爾排序

算法是程式的靈魂,而排序算法是算法的入門經典,作者在此用python親自實作了7種主流的排序算法,并做簡短的說明.