Python 3中的排序

引言

在编程中，排序是最常见也是最重要的问题之一。排序是将一组无序数据按照某个规则重新排列的过程。

Python 3中提供了多种排序算法，以便不同的数据结构选择最适合的排序算法。在本文中，我们将介绍几种最常用的排序算法，并提供示例代码。

算法说明

冒泡排序

冒泡排序是一种简单的排序算法。它不断地交换相邻元素，将较大的元素逐渐“浮”到数列的顶部。

def bubbleSort(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]

冒泡排序的时间复杂度是O(n^2)

快速排序

快速排序是一种分治法的排序算法。它使用递归的方式将数列划分成左右两个较小的子序列，在子序列中分别进行排序，最后将两个有序子序列合并成一个有序数列。

def partition(arr, low, high):
    i = (low-1)
    pivot = arr[high]

    for j in range(low, high):

        if arr[j] <= pivot:

            i = i+1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)


def quickSort(arr, low, high):
    if len(arr) == 1:
        return arr
    if low < high:

        pi = partition(arr, low, high)

        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

快速排序的平均时间复杂度为O(nlogn)。

选择排序

选择排序是一种简单的排序算法。该算法的主要思想是从未排序的序列中选择最小的数放到已排序序列的末尾。

def selectionSort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
                
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

选择排序的时间复杂度为O(n^2)。

插入排序

插入排序是一种简单稳定的排序算法。它的主要思想是将一个记录插入到已经排好序的有序序列中，从而得到一个新的、记录数增加1的有序序列。

def insertionSort(arr):
    for i in range(1, len(arr)):

        key = arr[i]

        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key

插入排序的时间复杂度为O(n^2)。

归并排序

归并排序是一种分治法的排序算法。它将数列分成两个有序序列，递归地将它们排序，并将结果归并到一个新的、更大的有序序列中。

def mergeSort(arr):
    if len(arr) >1:
        mid = len(arr)//2 
        L = arr[:mid] 
        R = arr[mid:] 

        mergeSort(L) 
        mergeSort(R) 

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

归并排序的时间复杂度为O(nlogn)。

结论

以上是Python 3中五种常用的排序算法，分别是冒泡排序、快速排序、选择排序、插入排序和归并排序。它们各自有其优点和适用范围，根据具体情况选择最合适的算法可以提高程序的效率，减少资源的消耗。