資料結構與算法-排序(二)

希爾排序

• 基本排序

将原本有大量記錄數的記錄進行分組。分割成若幹序列，此時每個子序列待排序的記錄個數就比較少了，然後在這些子序列内分别進行直接插入排序，當整個序列都基本有序時，再對全體記錄執行一次直接插入排序。其時間複雜度為O(n**3/2),突破了O(n*n)。

快速排序

• 基本思想

快速排序是基于一種“二分”的思想，相比較冒泡排序，總的比較和交換的次數減少。核心是設定基準點，跳躍式交換，平均時間複雜度為O(NlogN)。

代碼實作(python)

import random


def shell_sort(test_list):
    increment = len(test_list)

    while increment > :
        # increment分割的序列
        increment = increment/ + 
        # 以下就是直接插入排序的代碼 
        for i in range(increment, len(test_list)):
            # 每一個子序列都設定一個基準
            temp = test_list[i]
            j = i - 
            while j >=  and test_list[j] > temp:
                test_list[j + ] = test_list[j]
                j -= 
            test_list[j + ] = temp

    return test_list


def quick_sort(arr, left, right):

    if left > right:
        return
    # temp存的基準數
    temp = arr[left]
    pivot_index = left
    pivot_end = right

    while pivot_index != pivot_end:

        # 先從右往左找大于基準數的數
        while arr[pivot_end] >= temp and pivot_index < pivot_end:
            pivot_end -= 

        # 再從左往右找小于基準數的數
        while arr[pivot_index] <= temp and pivot_index < pivot_end:
            pivot_index += 

        # 交換兩個數在數組中的位置
        if pivot_index < pivot_end:
            arr[pivot_index], arr[pivot_end] = arr[pivot_end], arr[pivot_index]

    # 将基準位置歸位
    arr[left], arr[pivot_index] = arr[pivot_index], arr[left]

    # 繼續處理左邊的,這是一個遞歸的過程
    quick_sort(arr, left, pivot_index - )
    # 繼續處理右邊的,這是一個遞歸的過程
    quick_sort(arr, pivot_index + , right)

    return arr

if __name__ == '__main__':
    quick_list = [random.randint(, ) for _ in range()]
    print(quick_sort(quick_list, , len(quick_list)-))

    shell_list = [random.randint(, ) for _ in range()]
    print(quick_sort(shell_list, , len(shell_list)-))