10个python3常用排序算法详细说明与实例（快速排序，冒泡排序，桶排序，基数排序，堆排序，希尔排序，归并排序，计数排序）

10个Python3常用排序算法详细说明与实例

排序算法是计算机科学中的基本问题之一，它的目的是将一组数据按照一定的顺序排列。Python中提供了多种排序算法，本文将介绍10个常用的排序算法，并提供详细的说明和实例。

1. 快速排序

快速排序是一种基于分治思想的排序算法，它的时间复杂度为O(nlogn)。快速排序的基本思想是选择一个基准元素，将序列分为两个子序列，其中一个子序列的所有元素都小于基准元素，另一个子序列的所有元素都大于基准元素，然后递归地对子序列进行排序。

下面是快速排序Python实现代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

在这个示例中，我们首先判断输入序列的长度是否小于等于1，如果是，则直接返回输入序列。否则，我们选择一个基准元素，将序列分为三个子序列，然后递归地对左右两个子序列进行排序，并将三个子序列合并起来。

示例1

假设我们需要对以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行快速排序：

sorted_arr = quick_sort(arr)
print(sorted_arr)

输出结果为：

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

在这个示例中，我们使用快速排序对一个随机数组进行排序。快速排序的时间复杂度为O(nlogn)。

示例2

假设我们需要对以下数组进行排序：

arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

我们可以使用以下代码对这个数组进行快速排序：

sorted_arr = quick_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在这个示例中，我们使用快速排序对一个逆序数组进行排序。快速排序的时间复杂度为O(nlogn)。

2. 冒泡排序

冒泡排序是种简单的排序算法，它的时间复杂度为O(n^2)。冒泡排序的基本思想是从序列的第一个元素开始依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置，直到序列末尾。然后，我们重复这个过程，直到整个序列都有序。

下面是冒泡排序的Python实现代码：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

在这个示例，我们首先获取输入序列的长度，然后使用两个嵌套的循环对序列进行排序。在内层循环中，我们比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。

示例1

假设我们需要对以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行冒泡排序：

sorted_arr = bubble_sort(arr)
print(sorted_arr)

输出结果为：

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

在这个示例中，我们使用冒泡排序对一个随机数组进行排序。冒泡排序的时间复杂度为O(n^2)。

示例2

假设我们需要对以下数组进行排序：

arr = [10, 9, 8, 7, 6, , 4, 3, 2, 1]

我们可以使用以下代码对这个数组进行冒泡排序：

sorted_arr = bubble_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8 9, 10]

在这个示例中，我们使用冒泡排序对一个逆序数组进行排序。冒泡排序的时间复杂度为O(n^2)。

3. 桶排序

桶排序是一种线性时间复杂度排序算法，它的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的取值范围。桶排序的基本思想是将输入的数据分配到有限数量桶中，然后对每个桶中数据进行排序，最后将所有桶中的数据按照顺序依次排列起来。

下面是排序的Python实现代码：

def bucket_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    bucket_num = (max_val - min_val) // len(arr) + 1
    buckets = [[] for _ in range(bucket_num)]
    for i in arr:
        buckets[(i - min_val) // len(arr)].append(i)
    output = []
    for bucket in buckets:
        output += sorted(bucket)
    return output

在这个示例中，我们首先获取输入序列的最大值和最小值，然后计算桶的数量。接着，我们初始化桶，并将输入序列中的元素配到相应的桶中。然后，我们对每个桶中的元素进行排序，并将所有桶中的元素按照顺序依次排列起来。

示例1

假设我们需要以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行桶排序：

sorted_arr = bucket_sort(arr)
print(sorted_arr)

输出结果为：

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

在这个示例中，我们使用桶排序对一个随机数组进行排序。桶排序的时间复杂度为O(n)，其中是待排序元素的个数，k是元素的取值范围。

示例2

假设我们需要对以下数组进行排序：

arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

我们可以使用以下代码对这个数组进行排序：

sorted_arr = bucket_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在这个示例中，我们使用桶排序对一个逆序数组进行排序。桶排序的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是元素的取值范围。

4. 基数排序

基数排序是一种非比较排序算法，它的时间复杂度为O(nk)，其中n是待排序元素的个数，k是元素的大位数。基数排序的基本思想是将待排序元素按照位数划分为不同的桶，然后按照桶的顺序依次输出元素。

下面是基数排序的Python实现代码：

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        buckets = [[] for _ in range(10)]
        for i in arr:
            buckets[(i // exp) % 10].append(i)
        arr = [x for bucket in buckets for x in bucket]
        exp *= 10
    return arr

在这个示例中，我们首先获取输入序列的最大值，然后使用一个循环对序列进行排序。在每次循环中，我们将序列中的素按照位数划分为不同的桶，然后按照桶的顺序依次输出元素。

示例1

假设我们需要对以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行基数：

sorted_arr = radix_sort(arr)
print(sorted_arr)

输出结果为：

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

在这个示例中，我们使用基数排序对一个随机数组进行排序。基数排序的时间复杂度为O(nk)，其中是待排序元素的个数，k是元素的最大位数。

示例2

假设我们需要对以下数组进行排序：

arr = [10, 9, 8, 7, , 5, 4, 3, 2, 1]

我们可以使用以下代码对个数组进行基数排序：

sorted_arr = radix_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在这个示例中，我们使用基数排序对一个逆序数组进行排序。基数排序的时间复杂度为O(nk)，其中n是待排序元素的个数，k是元素的最大位数。

5. 堆排序

堆排序是一种基于堆的排序算法，它的时间复杂度为O(nlogn)。堆排序的基本思想是将待排序元素构建成一个堆，然后依次将堆顶元素取出，直到堆为空。

下面是堆排序的Python实现代码：

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and arr[i] < arr[l]:
            largest = l
        if r < n and arr[largest] < arr[r]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

在这个示例中，我们首先定义了一个heapify函数，用于将一个元素插入到堆中。然后，我们使用一个循环将输入序列构建成一个堆。接着，我们依次将堆顶元取出，并将剩余元素重新构建成一个堆。

示例1

假设我们需要对以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行堆排序：

sorted_arr = heap_sort(arr)
print(sorted_arr)

输出结果为：

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

在个示例中，我们使用堆排序对一个随机数组进行排序。堆排序的时间复杂度为O(nlogn)。

示例2

假设我们需要对以下数组进行排序：

arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

我们可以使用以下代码对这个数组进行堆排序：

sorted_arr = heap_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

在这个示例中我们使用堆排序对一个逆数组进行排序。堆排序的时间复杂度为O(nlogn)。

6. 希尔排序

希尔排序是一种基于插入排序的排序算法，它的时间复杂度为O(n^2)。希尔排序的基本思想是将待排序元素按照一定的间隔分组，后对每个分组进行插入排序，最后缩小间隔，直到间隔为1。

下面是希尔排序的Python实现代码：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

在这个示例中，我们首先获取输入序列的长度，然后使用一个循环对序列进行排序。在每次循环中，我们将序列按照一定的间隔分组，然对每个分组进行插入排序。

示例1

假设我们需要对以下数组进行排序：

arr = [5, 3, 2, 8, 6, 4, 1, 3]

我们可以使用以下代码对这个数组进行排序：

```python