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

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

选择排序

选择排序是一种简单的排序算法，它的基本思想是每次从未排序的元素中选择最小的元素，放到已排序的尾。选择排序的时间复杂度为(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(nn)。

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

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

另一个示例，演示如何使用两个列表里元素对应相乘的方法计算两个向量的点积：

vector1 = [1, 2, 3]
vector2 = [4, 5, 6]
dot_product = sum([a * b for a, b in zip(vector1, vector2)])
print(dot_product)    # 输出：32

在这个示例中，我们首先定义了两个向量vector1和vector2，然后使用两个列表里素对应相乘的方法计算它们的点积，并将结果打印出来。

总之，使用zip函数和列表推导式可以很方便地实现两个列表里元素对应相乘的方法，适用于各种需要对应元素相乘的场景。

堆排序

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

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

总结

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

总之，这些排序算法是Python编程中非常重要的基础知识，掌握它们可以帮助我们更好地理解和应用Python编程语言。