python 排序算法

排序是指以特定格式排列數(shù)據(jù)。排序算法指定按特定順序排列數(shù)據(jù)的方式。最常見的訂單是數(shù)字或字典順序。

排序的重要性在于如果數(shù)據(jù)以分類方式存儲，數(shù)據(jù)搜索可以優(yōu)化到非常高的水平。排序也用于以更易讀的格式表示數(shù)據(jù)。下面我們看到五個這樣的python排序實現(xiàn)。

• 冒泡排序
• 合并排序
• 插入排序
• 希爾排序
• 選擇排序

冒泡排序

它是一種基于比較的算法，其中每對相鄰元素進行比較，如果元素不合適，元素將進行交換。

def bubblesort(list):

# swap the elements to arrange in order
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp


list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結果 -

[2, 6, 11, 19, 27, 31, 45, 121]

合并排序

合并排序首先將數(shù)組分成相等的一半，然后以排序的方式組合它們。

def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list
# find the middle point and devide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

# merge the sorted halves

def merge(left_half,right_half):

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half
    return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結果 -

[11, 12, 22, 25, 34, 64, 90]

插入排序

插入排序包括為排序列表中的給定元素找到正確的位置。所以在開始時我們比較前兩個元素并通過比較它們來對它們進行排序。然后我們選取第三個元素，并在前兩個排序元素中找到它的正確位置。通過這種方式，我們逐漸將更多元素添加到已排序的列表中，并將它們置于適當?shù)奈恢谩?/p>

def insertion_sort(inputlist):
    for i in range(1, len(inputlist)):
        j = i-1
        nxt_element = inputlist[i]
# compare the current element with next one

        while (inputlist[j] > nxt_element) and (j >= 0):
            inputlist[j+1] = inputlist[j]
            j=j-1
        inputlist[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結果 -

[2, 11, 19, 27, 30, 31, 45, 121]

希爾排序

希爾排序涉及排序遠離其他的元素。我們對給定列表的大型子列表進行排序，并繼續(xù)縮小列表的大小，直到所有元素都被排序。下面的程序通過將其等于列表大小的一半來找到間隙，然后開始對其中的所有元素進行排序。然后我們不斷重置差距，直到整個列表被排序。

def shellsort(input_list):

    gap = len(input_list) / 2
    while gap > 0:

        for i in range(gap, len(input_list)):
            temp = input_list[i]
            j = i
# sort the sub list for this gap

            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j-gap
            input_list[j] = temp

# reduce the gap for the next element

        gap = gap/2

list = [19,2,31,45,30,11,121,27]

shellsort(list)
print(list)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結果 -

[2, 11, 19, 27, 30, 31, 45, 121]

選擇排序

在選擇排序中，我們首先查找給定列表中的最小值并將其移至排序列表。然后我們?yōu)槲磁判蛄斜碇械拿總€剩余元素重復該過程。輸入排序列表的下一個元素將與現(xiàn)有元素進行比較并放置在正確的位置。所以最后所有來自未排序列表的元素都被排序。

def selection_sort(input_list):

    for idx in range(len(input_list)):

        min_idx = idx
        for j in range( idx +1, len(input_list)):
            if input_list[min_idx] > input_list[j]:
                min_idx = j
# swap the minimum value with the compared value

        input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]


l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結果 -

[2, 11, 19, 27, 30, 31, 45, 121]