Python实现八大排序算法（2）

在本文中，我们将继续讲解Python实现八大排序算法的内容，包括选择排序、插入排序、希尔排序、归并排序、快速排序、堆、计数排序和桶排序。

选择排序

选择排序是一种简单的排序算法，它的基本思想是每次从未排序的元素中选择最小的元素，放到已排序的末尾。选择排序的时间复杂度为O(n^2)。

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

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

下面是一个示例，演示如何使用选择排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用选择排序对它进行排序，并将排序后的结果打印出来。

插入排序

插入排序是一种简单的排序算法，它的基本思想是将未排序的元素插入到已排序的部分中。插入排序的时间复杂度为O(n^2)。

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

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

下面是一个示例，演示如何使用插入排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = insertion_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用插入排序对它进行排序，并将排序后的结果打印出来。

希尔排序

希尔排序是一种改进的插入排序算法，它的基本思想是将列表分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终完成排序。希尔排序的时间复杂度为O(nlogn)。

面是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

下面是一个示例，演示如何使用希尔排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = shell_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用希尔排序对它进行排序，并将排序后的结果打印出来。

归并排序

归并排序是一种分治算法，它的基本思想是将列表分成若干个子序列，每个子序列进行排序，然后将排好序的子序列合并成一个大的有序序列。归并排序的时间复杂度O(nlogn)。

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

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_arr = arr[:mid]
        right_arr = arr[mid:]
        merge_sort(left_arr)
        merge_sort(right_arr)
        i = j = k = 0
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1
        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1
        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1
    return arr

下面是一个示例，演示如何使用归并排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = merge_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用归并对它进行排序，并将排序后的结果打印出来。

快速排序

快速排序是一种分治算法，它的基本思想是选择一个基准元素，将列表分成两个子序列，小于基准元素的放在左边，大于基准元素的放在右边，然后递归地对左右两个子列进行排序。快速排序的时间复杂度为O(nlogn)。

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

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left_arr = [x for x in arr if x < pivot]
    middle_arr = [x for x in arr if x == pivot]
    right_arr = [x for x in arr if x > pivot]
    return quick_sort(left_arr) + middle_arr + quick_sort(right_arr)

下面是一个示例，演示如何使用快速排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = quick_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

这个示例中，我们首先定义了一个列表arr，然后使用快速排序对它进行排序，并将排序后的结果打印出来。

堆排序

堆排序是一种树形选择排序算法，它的基本思想是将列表看成一个完全二叉树，将其转换成一个大根堆或小根堆，然后将堆顶元素与堆底元素交换，再将剩余元素重新调整成一个堆，重复以上步骤，直到整个序列有序。堆排序的时间复杂度为(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

下面是一个示例，演示如何使用堆排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = heap_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用堆排序对它进行排序，并将排序后的结果打印出来。

计数排序

计数排序是一种非比较排序算法，它的基本思想是统计每个元素出现的次数，然后根据元素出现的次数将元素排序。计数排序的时间复杂度为O(n+k)，其中k是元素的范围。

下面是Python实现计数的代码：

def counting_sort(arr):
    n = len(arr)
    output = [0] * n
    count = [0] * (max(arr)+1)
    for i in range(n):
        count[arr[i]] += 1
    for i in range(1, len(count)):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        output[count[arr[i]]-1] = arr[i]
        count[arr[i]] -= 1
    for i in range(n):
        arr[i] = output[i]
    return arr

下面是一个示例，演示如何使用计数排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = counting_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用计数排序对它进行排序，并将排序后的结果打印出来。

桶排序

桶排序是一种非比较排序算法，它的基本思想是将元素分到不同的桶中，对每个桶中的元素进行排序，然后将所有桶中的元素按顺序合并起来。桶排序的时间复杂度为O(n+k)，其中k是桶的数量。

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

def bucket_sort(arr):
    n = len(arr)
    max_val = max(arr)
    bucket_size = max_val // n + 1
    buckets = [[] for _ in range(bucket_size)]
    for i in range(n):
        bucket_index = arr[i] // bucket_size
        buckets[bucket_index].append(arr[i])
    for i in range(bucket_size):
        buckets[i].sort()
    output = []
    for i in range(bucket_size):
        output += buckets[i]
    return output

下面是一个示例，演示如何使用桶排序对一个列表进行排序：

arr = [64, 25, 12, 22, 11]
sorted_arr = bucket_sort(arr)
print(sorted_arr)    # 输出：[11, 12, 22, 25, 64]

在这个示例中，我们首先定义了一个列表arr，然后使用桶排序对它进行排序，并将排序后的结果打印出来。

总结

在本文中，我们讲解了Python实现八大排序算法的内容，包括选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序和桶排序。这些排序算法各有优缺点，应根据具体情况选择合适的算法。