博客

python数据结构的排序算法

  • Post category:Python

Python数据结构的排序算法

排序是计算机科学中最基本的问题之一，它可以用于在程序中存储和管理数据。Python中有多种排序算法，包冒泡排序、选择排序、插入排序、归并排序、快速排序等。本文将详细介绍这些排序算法的用法和示。

冒泡排序

冒泡排序是一种简单的排序算法，它通过比较相邻的元素并交换它们来排序。冒排序的时间复杂度为$O(n^2)$。以下是一个使用冒泡排序对列表进行排序的示例：

# 使用冒泡排序对列表进行排序
def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n-i-1):
            if lst] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5,3, 5]
bubble_sort(lst)
print(lst)

输出结果为：

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

在这个例中，我们使用冒泡排序算法对列表lst进行排序。我们使用两个嵌套的循环来比较相邻的元素并交换它们，直到整个列表都被排序。

选择排序

选择排序是一种简单的排序算法，它通过选择最小的元素并将其放在正确的位置来排序。选择排序的时间复杂度为$O(n^2)$。以下是一个使用选择排序对列表进行排序的示例：

# 使用选择排序对列表进行排序
def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if lst[j] < lst[min_idx]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
selection_sort(lst)
print(lst)

输出结果为：

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

在这个例中，我们使用选择排序算法对列表lst进行排序。我们使用两个嵌套的循环来选择最小的元素并将其放在正确的位置，直到整个列表都被排序。

插入排序

插入排序是一种简单的排序算，它通过将元素插入到已排序的部分中来排序。插入排序的时间复杂度为$O(n^2)$。以下是一个使用插入排序对列表进行排序的示例：

# 使用插入排序对列表进行排序
def insertion_sort(lst):
    n = len(lst)
    for i in range(1, n):
        key = lst[i]
        j = i - 1
        while j >=0 and key < lst[j]:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = key

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
insertion_sort(lst)
print(lst)

输出结果为：

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

在这个例中，我们使用插入排序算法对列表lst进行排序。我们使用一个循环来将元素插入到已排序的部分中，直到整个列表都被排序。

归并排序

归并排序是一种分治算法，它将列表分成两个子列表，对每个子列表进行排序，然后将它们合并成一个有序的列表。归并排序的时间复杂度为$O(n\log n)$。以下是一个使用归并排序对列表进行排序的示例：

# 使用归并排序对列表进行排序
def merge_sort(lst):
    if len(lst) > 1:
        mid = len(lst) // 2
        left_lst = lst[:mid]
        right_lst = lst[mid:]
        merge_sort(left_lst)
        merge_sort(right_lst)
        i = j = k = 0
        while i < len(left_lst) and j < len(right_lst):
            if left_lst[i] < right_lst[j]:
                lst[k] = left_lst[i]
                i += 1
            else:
                lst[k] = right_lst[j]
                j += 1
            k += 1
        while i < len(left_lst):
            lst[k] = left_lst[i]
            i += 1
            k += 1
        while j < len(right_lst):
            lst[k] = right_lst[j]
            j += 1
            k += 1

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
merge_sort(lst)
print(lst)

输出结果为：

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

在这个例中，我们使用归并排序算法对列表lst进行排序。我们使用递归将列表分成两个子列表，对每个子列表进行排序，然后将它们合并成一个有序的列表。

快速排序

快速排序是一种分治算法，它通过选择一个基准元素，将列表分成两个子列表，对每个子列表进行排序，然后将它们合并成一个有序的列表。快速排序的时间复杂度为$O(n\log n)$。以下是一个使用快速排序对列表进行排序的示例：

# 使用快速排序对列表进行排序
def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[0]
    left_lst = [x for x in lst[1:] if x < pivot]
    right_lst = [x for x in lst[1:] if x >= pivot]
    return quick_sort(left_lst) + [pivot] + quick_sort(right_lst)

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
lst = quick_sort(lst)
print(lst)

输出结果为：

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

在这个例中，我们使用快速排序算法对列表lst进行排序。我们选择一个基准元素，将列表分成两个子列表，对每个子列表进行排序，然后将它们合并成一个有序的列表。

总结

Python中有多种排序算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。每种排序算法都有其自己的优缺点和适景。本文介绍了这些排序算法的用法和示例，希望能够帮助您更好地理解Python中的排序算法。

Tags: