202606231529常见排序算法

常见排序算法

选择排序

思想：将待排序数组分为已排序和未排序两个部分。每次从未排序部分里面选择最小的，append到已排序部分。重复直至未排序部分为空。

SelectionSort(A)
	For i = 1 to n do
		Sort[i] = Find-Minimum from A
		Delete-Minimum from A
	Return(Sort)

从 1 遍历到 n，是 $O(n)$ 的。从未排序部分找最小值也是 $O(n)$ 的。所以选择排序的时间复杂度是 $O(n^2)$. 如果我们能利用某种数据结构，在 $O(\log n)$ 时间找到最小值，算法复杂度就能降到 $O(n\log n)$.

堆排序

哈哈，这次第二个就介绍堆排序，因为我就是为了学习堆而写的这篇笔记。

竖起耳朵听好了，

Heapsort is nothing but an implementation of selection sort using the right data structure.

— The Algorithm Design Manual

先看看什么是堆？

然后按照上面的思路，把获取最值的步骤换成用堆实现。

void heap_sort(std::vector<T>& v) {
    make_heap(v);
    size_t heap_size = v.size();
    for (size_t i = heap_size; i > 0; --i) {
        std::swap(v[0], v[i-1]);
        bubble_down(v, 0, i - 1);
    }
}

由于我们构建的是大顶堆，所以每次取到最大值，放在最后。依次缩减容量，即可排序。