Loading... ## 实验思路 ### 排序算法 算法部分使用 C++ 实现，并根据参数切换算法，返回消耗的时间。数据与画图使用 Python 实现。 ### 快速筛选 top 10 维护一个小顶堆，每次与堆顶比较。 ## 伪代码 ### **1.** **选择排序** ```C++ 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.** **冒泡排序** ```C++ 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.** **插入排序** ```C++ 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.** **归并排序** ```c++ 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.** **快速排序** ```c++ 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 ```C++ 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) $ 。 ### **快速排序：** 快排的递推公式如下： ```c++ quickSort(begin, end) = quickSort(begin, mid - 1) + quickSort(mid + 1, end); // 终止条件为 begin >= end ``` 看上去和归并排序的思路很像。区别在于归并排序是从下到上的排序，即先分解再排序整合。而快排正好相反，是从上到下排序的，即选定哨兵，分区，递归。 ### **top 10：** **最好时间复杂度:** 所有数都是从大到小有序排列的。这样的话只需要遍历一遍所有数即可，建堆的时间可以忽略不计。所以最好时间复杂度是 $ O(n) $ 。 **最坏时间复杂度:** 所有数都是从小到大有序排列的。此时每个元素都要入堆并调整。元素为 k 的堆进行堆化操作需要 $ O(logk) $ 的时间复杂度，所以最坏时间复杂度大概是在 $ O(log10) $ 左右。 综上所述，该方法的平均时间复杂度为 $ O(n) $ 。 最后修改：2020 年 04 月 14 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏