史上最全十大经典排序算法

以上就是十种经典的排序算法的详细讲解和实现。每种算法都有其适用的场景和优缺点，选择合适的排序算法需要根据具体的问题和数据特性来决定。希望本文能帮助你更好地理解和掌握这些排序算法！

木辰287

1498人浏览 · 2025-04-13 14:40:31

木辰287 · 2025-04-13 14:40:31 发布

十大经典排序算法详解与实现

排序算法是计算机科学中一个非常重要的主题，它不仅在实际应用中广泛使用，也是面试中经常考察的内容。本文将详细介绍十种经典的排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。每种算法都会从核心思想、算法步骤、性能分析和代码实现四个方面进行讲解。

1. 冒泡排序

核心思想

冒泡排序是一种简单的排序算法，它通过重复地遍历待排序的数列，比较相邻的两个元素，如果顺序错误就交换它们。这个过程会不断重复，直到没有需要交换的元素为止。

算法步骤

从数组的第一个元素开始，依次比较相邻的两个元素。
如果前一个元素大于后一个元素，则交换它们的位置。
每次遍历结束后，最大的元素会被移到数组的末尾。
重复上述过程，直到整个数组有序。

性能分析

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

代码实现

package main
import "fmt"

func bubbleSort(arr []int) []int {
    for i := 0; i < len(arr)-1; i++ {
        for j := 0; j < len(arr)-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

func main() {
    var a []int = []int{1, 7, 3, 4, 5}
    fmt.Println(bubbleSort(a))
}

2. 选择排序

核心思想

选择排序的核心思想是每次从未排序的部分中找到最小（或最大）的元素，将其放到已排序部分的末尾。

算法步骤

将数组分为已排序部分和未排序部分。
在未排序部分中找到最小的元素。
将找到的最小元素与未排序部分的第一个元素交换。
重复上述过程，直到整个数组有序。

性能分析

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

代码实现

func selectionSort(arr []int) []int {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[minIndex] > arr[j] {
                minIndex = j
            }
        }
        if minIndex != i {
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
        }
    }
    return arr
}

3. 插入排序

核心思想

插入排序的工作方式类似于整理扑克牌。每次从未排序部分取出一个元素，插入到前面有序部分的正确位置。

算法步骤

假设数组的第一个元素已经有序。
从第二个元素开始，依次将每个元素插入到前面有序部分的正确位置。
每次插入时，从后向前比较，找到合适的位置后插入。

性能分析

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

代码实现

func insertionSort(arr []int) []int {
    n := len(arr)
    for i := 1; i < n; i++ {
        current := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > current {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = current
    }
    return arr
}

4. 希尔排序

核心思想

希尔排序是插入排序的改进版，通过引入“增量”来减少元素的移动次数。它将数组分成多个子数组，分别进行插入排序，然后逐渐减小增量，直到增量为1时完成排序。

算法步骤

选择一个增量序列，通常从数组长度的一半开始。
按照增量将数组分成多个子数组。
对每个子数组进行插入排序。
逐渐减小增量，重复上述过程，直到增量为1。

性能分析

时间复杂度：O(n²)（最坏情况），O(n log n)（最好情况）
空间复杂度：O(1)
稳定性：不稳定

代码实现

func shellSort(arr []int) []int {
    n := len(arr)
    gap := n / 2
    for gap > 0 {
        for i := gap; i < n; i++ {
            current := arr[i]
            j := i - gap
            for j >= 0 && arr[j] > current {
                arr[j+gap] = arr[j]
                j -= gap
            }
            arr[j+gap] = current
        }
        gap /= 2
    }
    return arr
}

5. 归并排序

核心思想

归并排序是一种分治算法，它将数组分成两部分，分别排序，然后将两个有序部分合并成一个有序数组。

算法步骤

将数组分成两部分。
递归地对两部分分别进行归并排序。
将两个有序子数组合并成一个有序数组。

性能分析

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定

代码实现

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

6. 快速排序

核心思想

快速排序也是一种分治算法，它通过选择一个基准值，将数组分为两部分：小于基准值的部分和大于基准值的部分，然后递归地对这两部分进行排序。

算法步骤

选择一个基准值。
将数组分为两部分：小于基准值的部分和大于基准值的部分。
递归地对两部分进行快速排序。

性能分析

时间复杂度：O(n log n)（平均情况），O(n²)（最坏情况）
空间复杂度：O(log n)
稳定性：不稳定

代码实现

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[len(arr)-1]
    left, right := 0, len(arr)-1
    for i := range arr {
        if arr[i] < pivot {
            arr[left], arr[i] = arr[i], arr[left]
            left++
        }
    }
    arr[left], arr[right] = arr[right], arr[left]
    quickSort(arr[:left])
    quickSort(arr[left+1:])
    return arr
}

7. 堆排序

核心思想

堆排序利用堆的性质，将数组构造成一个最大堆，然后每次取出堆顶元素放到数组的末尾，逐渐缩小堆的范围。

算法步骤

将数组构造成一个最大堆。
将堆顶元素与最后一个元素交换。
调整堆，使其重新满足最大堆的性质。
重复上述过程，直到整个数组有序。

性能分析

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

代码实现

func heapSort(arr []int) []int {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
    return arr
}

func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

8. 计数排序

核心思想

计数排序是一种非比较排序算法，它通过统计每个元素的出现次数，然后根据计数结果重构有序数组。

算法步骤

找出数组中的最大值和最小值。
创建一个计数数组，统计每个元素的出现次数。
根据计数数组的值，重构有序数组。

性能分析

时间复杂度：O(n + k)（k是元素的范围）
空间复杂度：O(n + k)
稳定性：稳定

代码实现

func countingSort(arr []int) []int {
    max, min := arr[0], arr[0]
    for _, num := range arr {
        if num > max {
            max = num
        }
        if num < min {
            min = num
        }
    }
    count := make([]int, max - min + 1)
    for _, num := range arr {
        count[num - min]++
    }
    index := 0
    for i, cnt := range count {
        for ; cnt > 0; cnt-- {
            arr[index] = i + min
            index++
        }
    }
    return arr
}

9. 桶排序

核心思想

桶排序将数组中的元素分配到多个桶中，每个桶内部使用其他排序算法（如插入排序）进行排序，最后将所有桶中的元素合并。

算法步骤

将数组中的元素均匀分配到多个桶中。
对每个桶内部的元素进行排序。
按顺序将所有桶中的元素合并。

性能分析

时间复杂度：O(n + k)（k是桶的数量）
空间复杂度：O(n + k)
稳定性：稳定

代码实现

func bucketSort(arr []int, bucketSize int) []int {
    if len(arr) == 0 {
        return arr
    }
    min, max := arr[0], arr[0]
    for _, num := range arr {
        if num < min {
            min = num
        }
        if num > max {
            max = num
        }
    }
    bucketCount := (max - min) / bucketSize + 1
    buckets := make([][]int, bucketCount)
    for _, num := range arr {
        index := (num - min) / bucketSize
        buckets[index] = append(buckets[index], num)
    }
    result := make([]int, 0, len(arr))
    for _, bucket := range buckets {
        insertionSort(bucket)
        result = append(result, bucket...)
    }
    return result
}

10. 基数排序

核心思想

基数排序是一种非比较排序算法，它通过逐位比较元素的每一位数字，从最低位到最高位进行排序。

算法步骤

找出数组中的最大值，确定最大的位数。
从最低位开始，逐位进行计数排序。
每次计数排序后，将数组重新排列。

性能分析

时间复杂度：O(n * k)（k是元素的位数）
空间复杂度：O(n + k)
稳定性：稳定

代码实现

func radixSort(arr []int) []int {
    max := arr[0]
    for _, num := range arr {
        if num > max {
            max = num
        }
    }
    exp := 1
    for max/exp > 0 {
        countingSortByDigit(arr, exp)
        exp *= 10
    }
    return arr
}

func countingSortByDigit(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10)
    for i := 0; i < n; i++ {
        index := (arr[i] / exp) % 10
        count[index]++
    }
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }
    for i := n - 1; i >= 0; i-- {
        index := (arr[i] / exp) % 10
        output[count[index]-1] = arr[i]
        count[index]--
    }
    for i := 0; i < n; i++ {
        arr[i] = output[i]
    }
}