Python排序算法详解

Python 笔记

排序算法一直是计算机科学中最重要的主题，这是因为算法的正确性和效率是影响程序运行时间的主要因素之一，使程序员们在编写程序时要时刻考虑哪一个算法最适合解决当前的问题。在Python中，有很多经典的排序算法，它们各有特点，并可应用于不同的应用场景。在本文中，我们将介绍几种最常见和最有用的Python排序算法。

一、插入排序

插入排序是最简单和最常用的排序算法之一。它的原理是将待排序的元素插入到已排序的序列中。它有多种形式，其中最常见的是直接插入排序。

<!--Python代码-->
def insertSort(arr):
    for i in range(1,len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
<!--Python代码-->

插入排序的时间复杂度是O(n^2)。在输入数据已经排序的情况下，插入排序的时间复杂度可以达到O(n)。它是一个相对简单的排序算法，但是对大规模乱序数组排序时比较低效。但是在小规模的数组排序上，插入排序是一种非常有效且实用的排序算法。

二、归并排序

归并排序是应用分治思想的一种典型算法。它的基本思想是将待排序序列分成两个子序列，然后递归地对子序列进行排序，最后再将已排序的子序列合并成一个完整的有序的序列。

<!--Python代码-->
def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        mergeSort(left)
        mergeSort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    return arr
<!--Python代码-->

归并排序的时间复杂度是O(nlogn)。它是一种稳定的排序算法，但是需要额外的内存空间来进行数组的合并操作。归并排序在数据量比较大的排序、内部排序和外部排序中都有着重要的应用。

三、快速排序

快速排序也是一种分治思想的排序算法，它采用了“分治+递归”的策略来进行排序。它的基本思想是选择一个中间元素作为基准值，将小于基准值的元素放在左边的子数组中，将大于基准值的元素放在右边的子数组中。

<!--Python代码-->
def quickSort(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end)
        quickSort(arr, start, pivot - 1)
        quickSort(arr, pivot + 1, end)
    return arr
   
def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and arr[right] >= pivot:
            right -= 1
        if left > right:
            done = True
        else:
            arr[left], arr[right] = arr[right], arr[left]
    arr[start], arr[right] = arr[right], arr[start]
    return right
<!--Python代码-->

快速排序的时间复杂度是O(nlogn)。它是一种效率比较高的排序算法，也是很多Java内置排序算法的核心。但是，在最坏情况下，快速排序的时间复杂度会退化为O(n^2)，因此在实际应用中，为了降低快速排序的退化情况，我们需要进行优化操作。

四、堆排序

堆排序是一种改进的选择排序算法。它将待排序的序列看作一棵完全二叉树，并将序列构建成一个大根堆或者小根堆。堆排序的基本思想是在堆中选择最大（或最小）元素并删除它，反复执行以上操作直到堆为空或者待排序的序列已经有序。

<!--Python代码-->
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)

def heapSort(arr):
    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
<!--Python代码-->

堆排序的时间复杂度是O(nlogn)。它是一种效率比较高的排序算法，适用于大规模的数据集合排序。它在实现上也比较容易，仅需要非常少的额外内存空间。

五、希尔排序

希尔排序是对插入排序的一种改进和扩展。它的核心思想是先将整个序列分成若干个子序列进行排序，然后再将子序列合并成一个序列。希尔排序是一个复杂度受到外部序列间隔序列影响的复杂度高效算法。

<!--Python代码-->
def shellSort(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
<!--Python代码-->

希尔排序的时间复杂度是O(nlogn)~O(n^2)之间，它是一个效率非常高的排序算法。在数组比较乱的情况下，它比插入排序的效率要高很多，但是在数组比较有序或者很小的情况下，它的效率会大大降低。

六、总结

在本文中，我们详细介绍了Python中最常见和最有用的排序算法。我们了解了它们的基本思想、代码实现以及时间复杂度等相关知识点。希望这篇文章对想要学习排序算法的小伙伴有所帮助。