常見(jiàn)排序算法大比拼：原理與性能分析

排序算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，不同算法有不同原理和性能表現(xiàn)。下面對(duì)比幾種常見(jiàn)排序算法。

冒泡排序是簡(jiǎn)單直觀的排序算法。它重復(fù)走訪要排序的數(shù)列，一次比較兩個(gè)元素，若順序錯(cuò)誤就交換，直到?jīng)]有要交換的元素。時(shí)間復(fù)雜度為 O (n2) ，代碼實(shí)現(xiàn)如下：

def bubble_sort(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]
    return arr

快速排序是高效的排序算法，采用分治思想。選擇一個(gè)基準(zhǔn)元素，將數(shù)組分為兩部分，小于基準(zhǔn)的放左邊，大于基準(zhǔn)的放右邊，遞歸對(duì)兩部分排序。平均時(shí)間復(fù)雜度為 O (n log n) ，代碼如下：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

歸并排序同樣基于分治思想，將數(shù)組分成兩半，分別排序后再合并。時(shí)間復(fù)雜度穩(wěn)定在 O (n log n) 。在實(shí)際應(yīng)用中，根據(jù)數(shù)據(jù)規(guī)模和特點(diǎn)選擇合適的排序算法，能提高程序運(yùn)行效率。小規(guī)模數(shù)據(jù)用冒泡排序簡(jiǎn)單直接；大規(guī)模數(shù)據(jù)用快速排序或歸并排序更高效。