排序算法是计算机科学中的重要基础算法之一，其主要功能是将一组数据按照特定的顺序排列。无论是在数据处理、数据库查询还是搜索算法中，排序算法都起着至关重要的作用。本文将详细介绍八种常用的排序算法，包括其基本原理、时间复杂度、空间复杂度以及适用场景，以帮助读者更好地理解这些算法并在实际应用中做出合理的选择。

1. 冒泡排序

1.1 算法原理

冒泡排序是一种简单的排序算法，通过多次遍历待排序的数组，比较相邻元素并交换它们的位置。每次遍历时，将最大的元素“冒泡”到数组的顶端，直至整个数组有序。

1.2 伪代码

plaintext复制代码for i from 0 to n-1
    for j from 0 to n-i-2
        if array[j] > array[j+1]
            swap(array[j], array[j+1])

1.3 时间复杂度

• 最坏情况：O(n^2)

• 最好情况：O(n)（当数组已近乎有序时）

• 平均情况：O(n^2)

1.4 空间复杂度

O(1)

1.5 适用场景

冒泡排序适合小规模数据的排序，由于实现简单，适合教学和学习。

2. 选择排序

2.1 算法原理

选择排序每次从未排序部分中选择最小（或最大）的元素，放到已排序部分的末尾，逐步构建一个有序序列。

2.2 伪代码

plaintext复制代码for i from 0 to n-1
    minIndex = i
    for j from i+1 to n-1
        if array[j] < array[minIndex]
            minIndex = j
    swap(array[i], array[minIndex])

2.3 时间复杂度

• 最坏情况：O(n^2)

• 最好情况：O(n^2)

• 平均情况：O(n^2)

2.4 空间复杂度

O(1)

2.5 适用场景

选择排序适合小规模数组的排序，尤其是在内存占用受到严格限制时。

3. 插入排序

3.1 算法原理

插入排序将数组分为已排序和未排序两部分，逐步将未排序部分的元素插入到已排序部分的合适位置，保持已排序部分的有序性。

3.2 伪代码

plaintext复制代码for i from 1 to n-1
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key
        array[j + 1] = array[j]
        j = j - 1
    array[j + 1] = key

3.3 时间复杂度

• 最坏情况：O(n^2)

• 最好情况：O(n)（当数组已经有序时）

• 平均情况：O(n^2)

3.4 空间复杂度

O(1)

3.5 适用场景

插入排序在小规模数据或部分有序数据的排序中表现优异，因其相对简单且高效。

4. 快速排序

4.1 算法原理

快速排序使用分治法，将待排序数组划分为两个子数组，选择一个“基准”元素，使得左侧所有元素小于基准，右侧所有元素大于基准。然后递归地对左右子数组进行排序。

4.2 伪代码

plaintext复制代码function quicksort(array, low, high)
    if low < high
        pivotIndex = partition(array, low, high)
        quicksort(array, low, pivotIndex - 1)
        quicksort(array, pivotIndex + 1, high)

4.3 时间复杂度

• 最坏情况：O(n^2)（当数组已经有序时）

• 最好情况：O(n log n)

• 平均情况：O(n log n)

4.4 空间复杂度

O(log n)（递归调用栈的空间）

4.5 适用场景

快速排序适用于大规模数据的排序，特别是在处理随机数据时效率极高。

5. 归并排序

5.1 算法原理

归并排序是稳定的排序算法，采用分治法将数组分为两半，分别排序后再合并。合并过程保持了元素的有序性。

5.2 伪代码

plaintext复制代码function mergeSort(array)
    if length(array) <= 1
        return array
    mid = length(array) / 2
    left = mergeSort(array[0..mid])
    right = mergeSort(array[mid..end])
    return merge(left, right)

function merge(left, right)
    result = []
    while left and right are not empty
        if left[0] < right[0]
            append left[0] to result
        else
            append right[0] to result
    append remaining elements of left/right to result
    return result

5.3 时间复杂度

• 最坏情况：O(n log n)

• 最好情况：O(n log n)

• 平均情况：O(n log n)

5.4 空间复杂度

O(n)（需要额外的存储空间用于合并）

5.5 适用场景

归并排序适合大规模数据排序，特别是在需要稳定性时表现出色。

6. 堆排序

6.1 算法原理

堆排序利用堆这种数据结构（尤其是最大堆）来进行排序。首先构建最大堆，然后依次将堆顶元素（最大元素）移至数组末尾，调整堆以保持堆的性质。

6.2 伪代码

plaintext复制代码function heapSort(array)
    buildMaxHeap(array)
    for i from length(array) - 1 to 1
        swap(array[0], array[i])
        heapify(array, 0, i)

function buildMaxHeap(array)
    for i from length(array) / 2 - 1 to 0
        heapify(array, i, length(array))

function heapify(array, i, size)
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < size and array[left] > array[largest]
        largest = left
    if right < size and array[right] > array[largest]
        largest = right
    if largest != i
        swap(array[i], array[largest])
        heapify(array, largest, size)

6.3 时间复杂度

• 最坏情况：O(n log n)

• 最好情况：O(n log n)

• 平均情况：O(n log n)

6.4 空间复杂度

O(1)

6.5 适用场景

堆排序适用于需要较低内存消耗的大规模数据排序。

7. 计数排序

7.1 算法原理

计数排序是一种非比较排序算法，适用于范围已知的整数。通过统计每个元素的出现次数，然后根据统计结果构建排序后的数组。

7.2 伪代码

plaintext复制代码function countingSort(array, maxValue)
    count = array of zeros with size (maxValue + 1)
    output = array of zeros with size length(array)
    
    for number in array
        count[number] += 1
        
    for i from 1 to maxValue
        count[i] += count[i - 1]
        
    for number in reversed(array)
        output[count[number] - 1] = number
        count[number] -= 1
        
    return output

7.3 时间复杂度

• 最坏情况：O(n + k)（k为最大值）

• 最好情况：O(n + k)

• 平均情况：O(n + k)

7.4 空间复杂度

O(k)

7.5 适用场景

计数排序适用于已知范围且数据量较大的整数排序，尤其是数字范围较小的情况。

8. 基数排序

8.1 算法原理

基数排序是一种非比较排序算法，通过将整数分解为多个数字位进行排序。每一位的排序可以使用其他稳定的排序算法（如计数排序）。

8.2 伪代码

plaintext复制代码function radixSort(array)
    maxDigit = getMaxDigit(array)
    for d from 1 to maxDigit
        stableCountingSort(array, d)

function stableCountingSort(array, digit)
    count