实验思路
排序算法
算法部分使用 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) $ 。