用Python实现各种排序算法函数

排序算法是计算机科学中的一类重要算法，用于排序一系列元素的顺序。在实际应用中，我们经常需要对数据进行排序，例如搜索引擎根据搜索词的相关性对搜索结果进行排序，电商网站对商品进行价格或销量排序等等。Python语言是一种非常适合实现各种排序算法的编程语言，下面我们将逐一介绍并实现常见的排序算法。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历数列，每次比较相邻两个元素，如果前一个元素大于后一个元素，就交换两个元素的位置。每一轮遍历都可以确定一个元素的最终位置。它的时间复杂度为O(n^2)。

实现代码如下：

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

2. 选择排序

选择排序是一种简单直观的排序算法，它每次从待排序序列中选择最小的元素，并与序列中的 个元素交换位置。重复这个过程，直到序列排序完成。它的时间复杂度也是O(n^2)。

实现代码如下：

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

3. 插入排序

插入排序是一种简单直观的排序算法，它将待排序序列分成已排序和未排序两部分，每次从未排序部分选择一个元素插入已排序部分的正确位置。它的时间复杂度也是O(n^2)。

实现代码如下：

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

4. 希尔排序

希尔排序采用分组插入排序的思想，先将整个待排序序列分成若干个子序列分别进行插入排序，然后再对整个序列进行插入排序。它的时间复杂度取决于选取的增量序列，最坏情况下的时间复杂度为O(n^2)。

实现代码如下：

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

5. 归并排序

归并排序采用分治思想，将待排序序列分成两个子序列，分别对子序列进行排序，然后将两个已排好序的子序列合并起来。它的时间复杂度为O(nlogn)。

实现代码如下：

def merge_sort(array):
    if len(array) > 1:
        mid = len(array) // 2
        left = array[:mid]
        right = array[mid:]
        merge_sort(left)
        merge_sort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                array[k] = left[i]
                i += 1
            else:
                array[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1

6. 快速排序

快速排序采用分治思想，每次选取一个基准元素将待排序序列分成两个子序列，其中一个子序列中的所有元素都比基准元素小，另一个子序列中的所有元素都比基准元素大。然后对两个子序列进行排序。它的时间复杂度为O(nlogn)。

实现代码如下：

def quick_sort(array, low, high):
    if low < high:
        pivot = partition(array, low, high)
        quick_sort(array, low, pivot-1)
        quick_sort(array, pivot+1, high)

def partition(array, low, high):
    pivot = array[high]
    i = low
    for j in range(low, high):
        if array[j] < pivot:
            array[i], array[j] = array[j], array[i]
            i += 1
    array[i], array[high] = array[high], array[i]
    return i

7. 堆排序

堆排序采用建堆和调整堆两个过程，在建堆过程中，将待排序序列转化成一个大顶堆或小顶堆，然后将堆顶元素和堆底元素交换位置并将堆底元素移除，然后对剩余的元素重新进行堆调整。它的时间复杂度为O(nlogn)。

实现代码如下：

def heap_sort(array):
    n = len(array)
    for i in range(n//2-1, -1, -1):
        heapify(array, n, i)
    for i in range(n-1, 0, -1):
        array[i], array[0] = array[0], array[i]
        heapify(array, i, 0)

def heapify(array, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and array[largest] < array[left]:
        largest = left
    if right < n and array[largest] < array[right]:
        largest = right
    if largest != i:
        array[i], array[largest] = array[largest], array[i]
        heapify(array, n, largest)

总结

这里我们介绍并实现了常见的七种排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。虽然它们的时间复杂度不同，但是它们都是基于比较的排序算法，其时间复杂度的下限是O(nlogn)。除此之外，还有一些非基于比较的排序算法，例如桶排序、计数排序和基数排序，它们的时间复杂度可以达到O(n)，但是它们的应用范围有限。在实际开发中，我们需要根据具体问题选择合适的排序算法。