算法设计与分析：实验1 排序算法性能分析

1.常见排序算法分析

（1）选择排序

算法原理：

• 从数组 a[1--n] 中找到最小的元素，将其与第一个元素 a[1] 进行值的交换，这样数组中第一个位置就是最小的元素，即第一个位置变得有序。
• 接着从数组 a[2--n] 中找到最小的元素，将其与第二个元素 a[2] 进行值的交换，这样数组中前两个位置就是最小的两个元素，即前两个位置变得有序。
• 以此类推，每次从未排序的部分中选择最小的元素，将其与当前位置进行交换，使得数组的前面部分是有序的，并且有序的部分随着算法的不断迭代增大。
• 最终经过 n-1 次迭代之后，整个数组变得有序。

伪代码实现：

选择排序
 1:Function Selection_Sort()
 2:  For i=1 to n-1    //n-1次迭代
 3:    Min_idx=i    //记录a[i--n]最小值的下标,初始为i
 4:    For j=i+1 to n  //在a[i+1--n]中找到最小值的下标
 5:      If a[j]<a[min_idx]
 6:        Min_idx=j
 7:    Swap(a[i],a[Min_idx])  //a[i--n]中的最小值与a[i]交换

 时间复杂度分析：

• 外层循环执行了n-1次迭代。
• 内层循在每次外层循环中执行了n-i次迭代，并执行比较更新和交换常数操作。
• 总的时间复杂度表示：
• 
• 可以看到T(n)的主要部分是n^2，所以选择排序的时间复杂度为O(n^2)。
• 无论是最优情况还是最坏情况，选择排序都需要执行两层嵌套的循环，外层循环控制迭代次数，内层循环用于在未排序部分中找到最小值，时间复杂度都为O(n^2)。

 实际性能与预测性能对比：可以发现实际性能与预测性能是比较符合的，两条曲线几乎吻合。

优化性能测试：

• 考虑优化，单取最小值与同时取最大值和最小值，同时取最大值和最小值是每次迭代中同时找到最大值和最小值，并将他们交换到正确的位置上。
• 例子如下，设原序列为{9,8,2,6,3}，蓝色代表当前最小值，红色代表当前最大值，灰色代表已经排序后的数，3趟即可完成。

• 同时取最大值和最小值的选择排序算法的伪代码如下

  选择排序优化
   1:Function Selection_Sort_withMaxMin(a[],begin,end)
   2:  n=end-begin+1
   3:  For i=1 to n
   4:    //设置min_idx和max_idx初始值为当前位
   5:    min_idx=i 
   6:    max_idx=i
   7:    For j=i+1 to n  //在当前未排序部分找到最小值和最大值的下标
   8:      If a[j]<a[min_idx] min_idx=j
   9:      If a[j]<a[min_idx] min_idx=j
   10:    Swap(a[i],a[min_idx])
   11:    If max_idx==i    //如果最大值的下标与当前位置相同，则更新           
   12:      max_idx=min_idx  //max_idx为最小值的下标
   13:    Swap(a[n],a[max_idx]) 
   14:    //将未排序的部分的最后一个元素与最大值交换

• 对比图如下：

• 可以发现实际运行中，优化后的性能反而运行更慢了，这是因为虽然减少了比较次数，不过需要进行两次交换操作，增加了交换的开销，所测数据应该是交换操作次数比比较次数多太多，反而花费了额外的时间，使得运行时间更久。

 （2）冒泡排序

算法原理：

• 遍历数组中的每对相邻元素 (a[j], a[j+1])，其中 i 和 j 分别表示数组的索引，范围为j∈[1, n-i], i∈[1, n-1]。
• 对于每一对相邻元素 (a[j], a[j+1])，比较它们的值。如果 a[j] 大于 a[j+1]，则交换它们的位置，即将较大的元素向后移动。

• 通过重复执行步骤 1 和步骤 2，可以确保每一趟冒泡都会将当前未排序部分的最大元素“冒泡”到合适的位置。以此类推，使得数组的后面部分是有序的，并且有序的部分随着算法的不断迭代不断增大。
• 经过 n-1 趟冒泡之后，整个数组会变得有序。

 伪代码实现：

时间复杂度分析：

• 外层循环执行了n-1趟冒泡。
• 内层循环在每次外层循环中执行了n-i次迭代，执行比较和交换常数时间操作。
• 总的时间复杂度表示：
• 
• 可以看到T(n)的主要部分是n^2，所以冒泡排序的时间复杂度为O(n^2)。
• 在最优情况下，冒泡排序仍然需要执行 n−1 趟冒泡操作，但在每一趟冒泡中都不需要进行任何元素的交换，因为数组已经是有序的。尽管如此，每趟冒泡仍需完整遍历一次未排序部分，因此时间复杂度仍然是 O(n^2)。

 实际性能与预测性能对比：可以发现实际性能与预测性能是比较符合的，两条曲线比较贴近，可以验证得算法的正确性。

优化性能测试：

• 有序性检查优化，如果在一趟遍历中没有发生元素之间的交换，则说明序列已经有序，可以直接退出排序过程。伪代码如下：

• 双向冒泡排序，可以同时从序列的两端向中间进行冒泡。具体来说，它先让最大的元素冒泡到序列的末尾，然后再让最小的元素冒泡到序列的开头，如此反复，直到序列完全有序。伪代码如下：

• 双向冒泡排序的例子：设原序列为{9,8,2,6,3,4,1,7}，蓝色代表当前最小值，红色代表当前最大值，灰色代表已经排序后的数，4趟即可完成。

• 对比图如下：

从图中我们可以清楚地看到双向冒泡排序在处理大量数据时表现最佳，而有序性检查冒泡排序虽然稍微逊色一些，但仍然比普通冒泡排序要好。这说明不同的冒泡排序方法在处理大量数据时确实存在差异，这可能是因为它们在如何检查数据是否有序以及如何进行迭代方面有所不同。

（3）插入排序

算法原理：

• 第一个元素默认为已排序部分，从第二个元素开始处理。
• 在每一次外层循环的迭代中，将当前未排序部分的第一个元素（即 a[i]）保存在临时变量temp中。
• 内层循环从当前未排序部分的位置向前遍历，直到找到 temp 应该插入的位置。如果a[j-1]小于temp，说明 temp 已经找到了应该插入的位置，否则将 a[j-1] 向后移动一位，为 temp 腾出位置。
• 将 temp 插入到已排序部分的正确位置，即 a[j] = tmp。
• 通过以上步骤，每一次外层循环迭代都会将未排序部分的一个元素插入到已排序部分的正确位置，使得已排序部分保持有序。

 伪代码实现：

时间复杂度分析：

• 外层循环执行了n-1次迭代。
• 内层循环在每次外层循环中最坏执行了i次，每次循环都需要遍历到数组的第一个元素。
• 总的时间复杂度表示：
• 
• 可以看到T(n)的主要部分是n^2，所以插入排序的时间复杂度为O(n^2)。
• 在最优情况下，即输入数据已经完全有序的情况下，内层循环每次只需要比较一次就可以确定当前元素的位置,插入排序的时间复杂度为O(n)，最坏情况则为O(n^2)。

 实际性能与预测性能对比：可以发现实际性能与预测性能是接近一致的，两条曲线几乎完全吻合。

（4）合并排序

算法原理：

• 合并排序是一种基于分治策略的排序算法，它的主要思想是将待排序的数组分割成两个子序列，分别对这两个子序列进行排序，然后将排序好的子序列合并成一个有序的序列。
• 分割阶段： 首先将待排序的数组分割成两个子序列，直到每个子序列只包含一个元素为止。这个过程通过递归实现，将数组不断地分割成更小的子序列，直到每个子序列只有一个元素。
• 排序阶段： 对分割得到的子序列进行排序。这里采用递归的方式，对每个子序列分别调用合并排序算法，使得每个子序列都变成有序的。
• 合并阶段： 将排序好的子序列进行合并，生成最终的有序序列。合并的过程是通过比较两个有序子序列的元素，然后将较小的元素依次放入一个临时数组中，最后将临时数组中的元素复制回原始数组的相应位置，完成合并排序。

 伪代码实现：

时间复杂度分析：

• 分割阶段： 在每一次递归调用中，数组都被分成两半，直到每个子数组只有一个元素为止。假设数组长度为n，此数组会迭代logn层，那么分割阶段的时间复杂度可以用如下公式表示：

• 合并阶段： 在每个递归层次上，合并操作需要线性时间来将两个有序子数组合并成一个有序数组。由于递归调用是平衡的，因此每个元素最终都会参与一次合并操作。所以，合并操作的总时间复杂度为O(n)。
• 综上所述，合并排序的时间复杂度为：
• 
• 因此，合并排序的时间复杂度为 O(nlogn)。
• 在合并排序中，无论数组的初始状态如何，每次都会将数组均匀地划分成两部分，然后递归地对这两部分进行排序，最后再合并起来。因此合并排序无论是最优情况下还是最坏情况下的时间复杂度都是O(nlogn)。

 实际性能与预测性能对比：实际性能与预测性能的对比如下所示，带有标记的线代表预测性能。实际运行所需的时间与预测性能基本吻合。

（5）快速排序

算法原理：

• 快速排序是一种基于分治思想的排序算法。
• 选取基准点： 首先从数组中选取一个基准点（通常选择第一个元素），然后将数组中的其他元素按照与基准点的比较结果分为两部分，一部分小于基准点，一部分大于基准点。
• 划分子序列： 将数组中小于基准点的元素放在基准点的左侧，大于基准点的元素放在右侧。
• 递归排序： 对划分后的两个子序列分别递归地进行快速排序。即对左侧子序列和右侧子序列分别执行快速排序操作。
• 合并结果： 将左侧子序列、基准点、右侧子序列合并起来，得到最终有序的序列。

 伪代码实现：

时间复杂度分析：

• 分割阶段： 在每一次分割中，选择一个基准元素，并将其他元素根据与基准元素的大小关系分为两部分。这个过程的时间复杂度主要取决于比较和移动元素的次数。在最坏情况下，每次分割需要移动 O(n) 个元素，因此，最坏情况下的分割阶段的时间复杂度为O(n)。
• 递归排序阶段： 递归排序阶段的时间复杂度可以表示为递归树的深度。由于每次分割都将问题规模减半，因此递归树的深度为logn，所以时间复杂度可表示为：

• 综上所述，快速排序的时间复杂度为：
• 

• 因此，快速排序的时间复杂度为 O(nlogn)。
• 在快速排序中，最优情况发生在每次划分操作都能均匀地将数组分成两部分的情况下。这种情况下，快速排序的时间复杂度最佳，为O(nlogn)。最坏情况下发生在每次划分操作都只能将数组划分成一个元素和其余元素的情况下。这样的情况可能在数组已经有序或者逆序的情况下发生。每一次选择的基准都是剩余序列中的最值，可以得到需要递归的深度为序列长度规模O(n)。在这种情况下，快速排序的时间复杂度为 O(n^2)。

实际性能与预测性能对比：实际性能与预测性能的对比如下所示，带有标记的线代表预测性能。实际运行所需的时间略高于预测值，但整体表现仍相当接近。

 优化性能测试：

• 传统的快速排序算法通常会选择序列中的第一个元素作为基准，但是对于某些特殊的序列，这种选择可能会导致排序性能的下降。我的优化方法是在快速排序的基准选择过程中，如果子序列长度大于等于5个元素，就随机选取5个元素并排序，然后选择排序后的中间元素作为基准。
• 伪代码修改如下：

• 对比图如下：可以发现优化后的运行时间比未优化前快，因为优化基准选择，它更有可能选择到一个接近中位数的基准元素，从而更好地平衡了子序列的大小。这可以减少快速排序中递归深度的波动，提高了算法的整体性能。

（6）堆排序

算法原理：

• 堆排序是一种基于二叉堆的排序算法
• 构建最大堆： 首先将待排序数组视为一个完全二叉树，然后从最后一个非叶子节点开始，依次向前调整每个节点，使得以该节点为根的子树满足最大堆的性质，即父节点的值大于等于其子节点的值。
• 堆化调整： 构建完成最大堆后，将根节点（即最大值）与数组末尾元素交换，然后对剩余元素进行堆化调整，保持剩余部分仍然满足最大堆的性质。交换后，最大值被移到数组末尾，剩余元素的最大值重新上浮到根节点位置。
• 重复步骤2： 重复以上步骤，每次将最大值交换到数组末尾，并对剩余部分进行堆化调整，直到所有元素都被排序完成。

 伪代码实现：

时间复杂度分析：

• 堆的构建：堆的构建包含初始化一个未排序的数组，并将其调整为一个有效的堆结构。因为堆的构建需要对每个非叶子结点进行调整，而非叶子结点的数量为n/2，因此这一过程的时间复杂度为O(n)。 
• 堆化调整： 堆化调整是将一个元素插入到一个已经构建好的堆中，重新调整使其满足堆的性质。在堆排序中，每次将堆顶元素与数组末尾元素交换，然后对剩余元素进行堆化调整，要执行n-1次堆化调整。因为需要向下比较、交换和调整，树的高度为logn。所以这一过程的时间复杂度为：

• 综上所述，堆排序的时间复杂度为：
• 

• 因此，堆排序的时间复杂度为 O(nlogn)。
• 在堆排序中，无论是最优情况还是最坏情况下，堆的构建时间复杂度都是 O(n)，因为构建堆只需要对每个非叶子节点进行一次堆化调整，共需n/2 次操作。在堆化调整阶段，无论是最优情况还是最坏情况下，每次调整的时间复杂度都是 O(logn)，因为堆的高度是O(logn)。因此，堆排序的时间复杂度无论最优还是最坏情况下都是O(nlogn)。

 实际性能与预测性能对比：实际性能与预测性能的对比如下所示，带有标记的线代表预测性能。实际运行时间比预测运行时间要慢一些，且随着n规模的增长，二者的差距逐渐增大，但总体来说相差不大。

 2.O(n^2)排序算法的实际性能与预测性能对比

1. O(n^2)排序算法有选择排序、冒泡排序、插入排序。
2. 性能测试与预测性能对比的分析中，预测性能的耗费时间的计算方法为：耗费时间 = 数据规模2 * 数据规模为10000时的实际运行时间 / (10000*10000)。
3. 将三种排序算法进行比较后发现，冒泡排序的时间开销明显高于其他两种排序算法。这主要是因为冒泡排序中存在大量的无效访问操作，导致时间复杂度较高。相比之下，插入排序是三种算法中执行速度最快的，略快于选择排序。

3.O(nlogn)排序算法的实际性能与预测性能对比

1. O(nlogn)排序算法有合并排序、快速排序、堆排序。
2. 性能测试与预测性能对比的分析中，预测性能的耗费时间的计算方法为：耗费时间 = 数据规模*log(数据规模) * 数据规模为10000时的实际运行时间 / (10000*log10000)。
3. 在这三种算法中，快速排序的执行效果最佳，而堆排序的效果最差。这可能是因为快速排序在平均情况下具有较好的时间复杂度，并且具有较好的缓存局部性，从而提高了执行效率。相比之下，堆排序的性能可能受到堆的数据结构限制，导致了更多的内存访问和调整操作，从而影响了执行效率。

4.6种排序算法的实际性能与预测性能对比

1. 由于6种排序算法时间的差异较大，因此对运行时间取对数以便于观察。
2. 我们可以清晰地看到六种排序算法分成了两组。三种O(n^2)的算法聚集在上方，而三种O(nlogn)的算法则聚集在下方。在每组算法中，有些算法的时间花费较高，而有些则较低，但总体上，由于时间复杂度的不同所导致的时间增加明显大于由常数项导致的时间增加。

5.求解TOPK问题

以k为1，10，50，100，500，1000，10000，100000分别测试算法的实际运行效率。

（1）直接排序O(NlogN)：

考虑使用直接排序方法是最直观的思路。

这种方法首先对 n 个数进行排序，然后从排序后的序列中取出最大的 k 个数，即可得到 TopK 的结果。

直接排序的时间复杂度取决于排序算法的性能，其中最快的排序算法是快速排序，时间复杂度为 O(NlogN)。

数据统计与对比分析：

K 与 N 的影响：

• 在不同规模下，我们观察 K 与 N 对实际运行性能的影响。
• 从图中（下图为上图的放大）可以看出实际运行性能与 K 的大小并没有直接关系，而主要与数据规模 N 有关。因为无论K的多少都要全部排序后再选出最大的K个数。
• 这意味着无论 K 的大小如何变化，整体的运行时间呈现出与 N 相关的 O(NlogN) 曲线。

尽管我们只需要找到 TopK 的结果，但直接排序方法却需要对整个数据集进行排序，这使得其时间复杂度非常高。这种方法的主要缺点在于它没有充分利用我们只关心最大的 K 个元素这一特点，而是对整个数据集进行排序。然而，我们可以避免对整个数据集进行排序，只对局部数据进行排序。

（2）局部排序O(NK)：

 可以发现冒泡排序和选择排序都具有按序列的前i大先排好的特点，所以可以选择做K次循环找到序列的前K大。

局部排序的时间复杂度为O(NK)。

数据统计与对比分析：

局部排序的时间复杂度与N和K的大小密切相关，且当K的规模达到500时，其运行时间就已经达到6000秒左右，算法运行时间已经显著增加。

在相同的数据规模 N 下，不同的 K 呈现出与 K 同比例的运行时间，而在相同的 K 下，不同的数据规模 N 呈现出与 N 同比例的运行时间。这表明了该方法的有效性和可靠性。

（3）堆排序O(NlogK)：

维护一个大小为 K 的小顶堆，用于存储序列的前 K 大位数字。

算法的思路是，在扫描序列时，如果堆内的元素个数小于 K，则直接将扫描到的元素插入堆的末尾。如果堆内的元素个数为 K，就判断扫描到的元素与堆顶的关系：如果大于堆顶，则将扫描到的元素顶替堆顶，并进行更新；否则，扫描下一个元素。

该方法的时间复杂度为 O(NlogK)。

数据统计与对比分析：

在不同规模的数据集下，我们观察到在不同的 K 下，算法的运行性能呈现出了一定的差异，但并不明显。尽管在较大的 N 下可能会略微增加，但并不呈现出与 K 成对数关系的增长趋势。这与我们预测的时间复杂度 O(NlogK) 中 K 对运行性能的影响并不相符。

这种情况的出现是因为在实际遍历序列时，仅当当前元素大于堆顶元素时才会推入堆中，并进行 O(logK) 的更新。因此，在序列遍历到后期时，堆中的元素基本已经稳定，许多元素在与堆顶的对比中就被筛掉，没有占用太多时间。因此，增大 K 并不会以对数方式显著增加时间复杂度。

（4）随机排序O(NC)：

对于给定的问题，我们需要找到前 n 大的元素，并不要求按顺序排列这些元素。我们可以使用类似于快速排序中的 divide 函数的方法。在变形的快速排序中，我们选取一个 base，并将大于 base 的元素放在其左边，小于 base 的元素放在右边。

算法原理：减治法，大问题分解为小问题，小问题只要递归一个分支。选取的 base进行 divide 函数后，如果左边部分的元素个数大于 K，则在左部分序列继续找前 K 大的数，舍弃右部分；如果左边部分的元素个数小于 K，则在右部分的序列找前 K - base大的数。如果左部分的元素个数正好为 K 则序列的前 K 个元素即为序列的前 K 大的元素。

传统快速排序是基于分治法，大问题分解为小问题，小问题都要递归各个分支，此方法是基于减治法，大问题分解为小问题，小问题只要递归一个分支。设计的算法每次都会舍弃左右两个部分中的其中一个。

在平均情况下，每次选择的base恰好能将剩余序列平均分割为两部分，因此每次调用divide函数的时间复杂度为 O(N / (2^t))。总的时间复杂度为 2N，该方法的时间复杂度为 O(N)。

数据统计与对比分析：

K与N在不同规模下的实际运行性能：可以发现，实际运行性能确实如我们所想的，并不直接与k有很大的关系，而K与N的比例会在一定程度上影响算法的速率，整体趋向于稳定。

（5）四种算法复杂度对比

四种方法的直接比较（选取K=10，100，1000）

• K=10：

可以得到第三种O(NlogK)的方法有比较好的实现性能，第四种O(NC)也很好，而第一种直接排序O(NlogN)的方法运行效率明显比较慢。

• K=100：

可以看出随着K规模的变大，第二种方法O(NK)时间复杂度的缺点开始暴露，运行时间变得相对缓慢，其他三种没什么变化。仍是第三和第四种方法占优势。

• K=1000：

可以看出，这时候第二种方法O(NK)运行时间已经大大慢于其他三种方法，不再适用了。而其他三种方法相较于第二种方法，运行时间已经比较接近了。

根据K=10，100，1000三个图像的分析，我们可以发现第三种方法O(NlogK)和O(NC)的运行效率是比较接近的，所以我们继续分析第三和第四种方法。

（6）O(NlogK)和O(NC)的性能对比

• 从图像上看（实线表示O(NlogK)，虚线表示O(NC)），我们观察到第四种方法（O(NC)）并没有像预期的那样性能优于第三种方法（O(NlogK)）。
• 这主要有两个原因：
• 首先，第三种方法的时间复杂度并不总是接近其最坏情况下的时间复杂度O(NlogK)。序列遍历到后面时，堆中元素基本已经稳定，很多元素基本在与堆顶的对比中就被筛掉，并没有占用很多时间。所以K的增大不会以logK的趋势去影响时间复杂度。它在实际运行中通常会表现得更好。
• 其次，即使第四种方法经过优化，仍然有可能出现不理想的情况，例如取得的base值偏离了序列的中间位置，导致时间花费增加。
• 尽管第四种方法不如第三种方法，但它们之间的差距并不大，通常在两倍的差距以内。在时间复杂度的角度来看，这样的误差是可以容忍的。而且，即使K的规模增大，两者之间的差距也不会显著扩大。
• 虽然第三种方法在处理较大的K时的性能差异较小，但总体趋势是时间花费随K的增大而单调增加。相比之下，第四种方法在处理更大的K时，并没有表现出这种趋势，因此在处理较大的K时可能会呈现出更好的性能表现。