Python 排序算法：5 种实现代码的方法

排序是指以某种格式排列数据。排序算法确定数据如何按特定顺序排列。最常见的排序是数字顺序或词序。

排序的重要性在于，如果信息被分类存储，则可以将信息搜索优化到非常高的水平。排序还用于以更易读的格式呈现数据。我们来看看Python中实现的五种排序方法。 † 它们不适合，更换元件。

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)

Python

运行上面的示例代码，得到以下结果 -

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

Shell

归并排序

归并排序先将数组进行等分合并，然后等分排序。看下面的代码实现 -

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))

Python

执行上面的示例代码，你会得到以下结果 -

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

Shell

输入排序

输入需要找到元素的正确位置。排序列表。所以首先比较前两个元素，然后通过比较对它们进行排序。然后选择第三个元素并在前两个已排序元素中找到它的正确位置。这样，更多的元素就会逐渐添加到排序列表中，并放置在适当的位置。

参见下面代码的实现 -

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)

Python

执行上面的示例代码，你将得到以下结果 -

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

Shell

Shell 元素

希尔排序 on 排序关闭 。对给定列表的大子列表进行排序，并继续减小列表的大小，直到所有元素都排序完毕。下面的程序通过将其变为列表大小的一半来找到间隙，然后开始对其中的所有元素进行排序。然后不断重置间隔，直到整个列表排序完毕。

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)

Python

运行上面的示例代码，得到以下结果 -

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

Shell

选择排序

在选择排序中，首先从给定列表中找到最小值并将其移动到列表中。 。然后对未排序列表的每个剩余元素重复该过程。将输入排序列表中的下一个元素与现有元素进行比较并放置在正确的位置。所以最终未排序列表的所有元素都会被排序。看下面的代码实现 -

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)

Python

运行上面的示例代码，你会得到以下结果 -

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