实验思路

排序算法

算法部分使用 C++ 实现，并根据参数切换算法，返回消耗的时间。数据与画图使用 Python 实现。

快速筛选 top 10

维护一个小顶堆，每次与堆顶比较。

伪代码

1. 选择排序

for i = 0 to len - 1
    minPos = i
    for j = i + 1 to len - 1
        if arr[j] < arr[minPos]
            minPos = j
    swap(arr[i], arr[j])

2. 冒泡排序

for i = 0 to len - 1
    for j = 1 to len - i
        if arr[j] < arr[j - 1]
            swap(arr[j], arr[j - 1])

3. 插入排序

for i = 1 to len
    key = arr[i]
    pos = i - 1
    for pos to 0 and arr[pos] > key
        arr[pos + 1] = arr[pos]
    arr[pos] = key

4. 归并排序

mergeSort(*begin, *end)
    mid = (begin + end) / 2
    // devide
    mergeSort(begin, mid)
    mergeSort(mid, end)

    left = begin, right = mid
    tmp = new arr[n]
    
    while left < mid && right < len
        if arr[left] < arr[right]
            tmp.append(arr[left++])
        else
            tmp.append(arr[right++])

    // handle the rest digits
    while left < mid
        tmp.append(arr[left++])

    while right < len
        tmp.append(arr[right++])

    copy tmp to arr

5. 快速排序

quickSort(*begin, *end)
    left = 1, right = len - 1
    key = begin[0]

    while left < right
        while left < right && begin[right] >= key
            right--

        while left < right && begin[left] <= key
            left++

        if left != right
            swap(begin[left], begin[right])

    swap(begin[0], begin[right])

    quickSort(begin, mid)
    quickSort(mid, end)

top 10

build small_top_heap

for num in input
    if num > heap.top
        heap.popTop
        heap.push(num)
        
return heap.data

算法分析

选择，冒泡，插入：

都是双重 for 循环，时间复杂度为 $O(n^2)$ ，且它们都是稳定的排序算法。

归并排序 ：

归并排序使用二分法，所以归并排序的时间复杂度的计算公式就是：

$$ T(1) = C; \\ T(n) = 2 \times T(\frac{n}{2}) + n; $$

一步步推导下去，我们可以得到

$$ T(n) = 2^k \times T(\frac{n}{2^k}) + kn \ \ \ \ \ \ (1) $$

当 $ T(\frac{n}{2^k}) = T(1) $ 时，即 $ 2^k = 1 $ 时，可以得到

$$ k = log_2n $$

代回上面的 $(1)$ 式可以得到：

$$ T(n) = Cn + nlog_2n $$

用 大 O 表示法 表示则为 $ O(nlogn) $

归并排序不是原地排序算法，需要额外的一个数组来保存数据，所以空间复杂度为 $ O(n) $ 。

快速排序：

快排的递推公式如下：

quickSort(begin, end) = quickSort(begin, mid - 1) + quickSort(mid + 1, end);
// 终止条件为 begin >= end

看上去和归并排序的思路很像。区别在于归并排序是从下到上的排序，即先分解再排序整合。而快排正好相反，是从上到下排序的，即选定哨兵，分区，递归。

top 10：

最好时间复杂度: 所有数都是从大到小有序排列的。这样的话只需要遍历一遍所有数即可，建堆的时间可以忽略不计。所以最好时间复杂度是 $ O(n) $ 。

最坏时间复杂度: 所有数都是从小到大有序排列的。此时每个元素都要入堆并调整。元素为 k 的堆进行堆化操作需要 $ O(logk) $ 的时间复杂度，所以最坏时间复杂度大概是在 $ O(log10) $ 左右。

综上所述，该方法的平均时间复杂度为 $ O(n) $ 。