快速排序、归并排序、堆排序对比

在所有排序算法中，平均时间复杂度为O(nlogn)的算法一共有三种：快速排序、归并排序、堆排序。

排序算法	最好情况时间复杂度	平均情况时间复杂度	最坏情况时间复杂度	空间复杂度	稳定性
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
希尔排序	O(n)	O(n log n)	O(n log n)	O(1)	不稳定
基数排序	O(nk)	O(nk)	O(nk)	O(n + d)	稳定

注：

• 稳定性：如果两个元素相等，排序后它们的相对顺序不变，则称该排序算法是稳定的。
• 希尔排序的时间复杂度和增量选择有关，如果增量序列是1，2，4，8，16，32，64，128，256，512，1024，则时间复杂度为O(n)。
• 基数排序的时间复杂度为O(nk)，其中k为元素的位数。
  

出于好奇我打算自己实现这三种排序，并对比它们的性能。

一、快速排序

步骤详解：

1. 选择基准值：一般选择第一个元素作为基准值。
2. 分区操作：将数组分成两个部分，左边的元素都小于基准值，右边的元素都大于基准值。
3. 递归排序：对基准值左右子数组进行递归执行以上两步，直到左右子数组长度为0，数组便有序。

func partition(arr []int, left, right int) int {
    pivot := arr[right]
    i := left - 1
    for j := left; j < right; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    i++
    arr[right], arr[i] = arr[i], arr[right]
    return i
}

func QuickSort(arr []int, left, right int) {
    if left < right {
        mid := partition(arr, left, right)
        QuickSort(arr, left, mid-1)
        QuickSort(arr, mid+1, right)
    }
}

二、归并排序

步骤详解：

1. 递归分割：如果数组长度大于1，则递归地将数组分成两个子数组。
2. 排序：直到子数组长度为1，然后将两个子数组进行排序成一个新的有序数组。
3. 合并：将两个已经有序的子数组合并成一个新的有序数组并返回。

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
}

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)
}

三、堆排序

堆的概念：

堆（heap）是一种满足特定条件的完全二叉树，一般使用数组作为存储方式，对于数组中每个下标 i（从0开始），左孩子为 2i+1，右孩子为 2i+2，堆分为两种：

• 小顶堆（min heap）：任意节点的值 ≤ 其子节点的值，堆顶（根节点）的元素最小。
• 大顶堆（max heap）：任意节点的值 ≥ 其子节点的值，堆顶（根节点）的元素最小。

步骤详解：

1. 构建堆：从最后一个非叶子节点（下标为 n/2-1）开始，从下往上，依次将每个节点的值赋值为其左右子节点值中的最大值，直到根节点，使整个数组形成一个最大堆。
2. 从数组中最后一个元素开始，和根节点交换位置，此时该元素已经处于排好序的位置，堆长度减1，重新对堆顶调整，使剩余的数组仍为最大堆。
3. 重复步骤2，直到堆长度为1。

func HeapSort(arr []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)
    }
}

func heapify(arr []int, n, i int) {
    largest := i
    left := i*2 + 1
    right := i*2 + 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)
    }
}

四、性能测试对比

在下文中通过生成一个长度为 200000 的随机数数组，对我们自己实现的三种排序算法进行性能测试，并对比它们的性能。

快速排序：
goos: windows
goarch: amd64
pkg: demo2/algorithms
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkQuickSort-16                 90          13047283 ns/op         1605665 B/op          1 allocs/op
BenchmarkQuickSort-16                 80          12976745 ns/op         1605635 B/op          1 allocs/op
BenchmarkQuickSort-16                100          13071114 ns/op         1605633 B/op          1 allocs/op
PASS

归并排序：
goos: windows
goarch: amd64
pkg: demo2/algorithms
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkMergeSort-16                 45          28383313 ns/op        31327008 B/op     200002 allocs/op
BenchmarkMergeSort-16                 49          30430869 ns/op        31326802 B/op     200000 allocs/op
BenchmarkMergeSort-16                 39          27267669 ns/op        31326759 B/op     200000 allocs/op
PASS

堆排序：
goos: windows
goarch: amd64
pkg: demo2/algorithms
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkHeapSort-16                  49          23543824 ns/op         1605634 B/op          1 allocs/op
BenchmarkHeapSort-16                  50          23547334 ns/op         1605633 B/op          1 allocs/op
BenchmarkHeapSort-16                  50          23595582 ns/op         1605687 B/op          1 allocs/op
PASS

从结果可以看出，快速排序的内存开销和时间开销都比归并排序和堆排序要小

但是！ 在上文中我使用的堆排序函数中，堆调整的方式是递归的
每次递归都是一个函数调用，这意味着需要分配新的栈帧来存储局部变量、参数和其他状态信息。此外还需要进行参数传递、返回地址的保存以及函数体的执行，这增加了额外的时间开销。因此我们将该函数改为迭代方式，使其在一个for循环内完成，以提高性能。

func heapify(arr []int, n, i int) {
    largest := i
    left := i*2 + 1
    right := i*2 + 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) // 递归调用自己
    }
}

func heapify(arr []int, n, i int) {
    //使用迭代方式替换了递归
    for {
        largest := i
        left := i*2 + 1
        right := i*2 + 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]
            i = largest
        } else {
            break
        }
    }
}

性能对比

递归堆调整：
goos: windows
goarch: amd64
pkg: demo2/algorithms
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkHeapSort-16                  49          23543824 ns/op         1605634 B/op          1 allocs/op
BenchmarkHeapSort-16                  50          23547334 ns/op         1605633 B/op          1 allocs/op
BenchmarkHeapSort-16                  50          23595582 ns/op         1605687 B/op          1 allocs/op
PASS

迭代堆调整：
goos: windows
goarch: amd64
pkg: demo2/algorithms
cpu: AMD Ryzen 7 5800H with Radeon Graphics
BenchmarkHeapSort-16                  58          20431231 ns/op         1605637 B/op          1 allocs/op
BenchmarkHeapSort-16                  58          20289929 ns/op         1605632 B/op          1 allocs/op
BenchmarkHeapSort-16                  58          20366748 ns/op         1605633 B/op          1 allocs/op
PASS

可以看出，迭代堆调整的性能比递归堆调整的性能要好一些。