Python 排序算法



Python 排序算法

Python 排序算法详细操作教程

排序是指以特定格式排列数据。排序算法指定了按特定顺序排列数据的方式。最常见的顺序是按数字顺序或字典顺序。

排序的重要性在于,如果以排序方式存储数据,则可以将数据搜索优化到很高的水平。排序还用于以更具可读性的格式表示数据。下面我们看到在python中进行排序的五个此类实现。

冒泡排序
合并排序
插入排序
希尔排序
选择排序

冒泡排序

这是一种基于比较的算法,其中比较每对相邻元素,如果元素顺序不正确,则将其交换。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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)

运行结果如下:
 [2, 6, 11, 19, 27, 31, 45, 121]

合并排序

合并排序首先将数组分成相等的两半,然后以排序的方式将它们合并。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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))

运行结果如下:
 [11, 12, 22, 25, 34, 64, 90]

插入排序

插入排序涉及在排序列表中找到给定元素的正确位置。因此,从一开始我们就比较前两个元素,并通过比较将它们排序。然后,我们选择第三个元素并找到其在前两个排序元素中的正确位置。通过这种方式,我们逐渐将更多元素添加到已经排序的列表中,方法是将它们放置在适当的位置。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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)

运行结果如下:
 [2, 11, 19, 27, 30, 31, 45, 121]

希尔排序

Shell Sort涉及对其他元素进行排序的元素。我们对给定列表的一个大子列表进行排序,然后继续减小列表的大小,直到对所有元素进行排序。下面的程序通过将其等于列表大小长度的一半来找到间隙,然后开始对其中的所有元素进行排序。然后我们继续重置间隙,直到对整个列表进行排序。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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)

运行结果如下:
 [2, 11, 19, 27, 30, 31, 45, 121]

选择排序

在选择排序中,我们首先在给定列表中找到最小值,然后将其移到排序列表中。然后,我们对未排序列表中的每个其余元素重复该过程。将进入排序列表的下一个元素与现有元素进行比较,并放置在其正确位置。因此,最后对未排序列表中的所有元素进行排序。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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)

运行结果如下:
 [2, 11, 19, 27, 30, 31, 45, 121]