各种排序算法的复杂度研究.pdf

算法基础（B） Mini-Project #1 算法基础（B） Mini-Project #1 权超禹 P 算法基础（B） Mini-Project #1 实验题目： 实验1： n 1~16 n 排序 个元素，元素为随机生成的长为 的字符串， 的取值为： 4 6 8 10 12 14 16 18 20 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 实现算法：直接插入排序，冒泡排序，堆排序，归并排序，快速排序。 2 实验 ： 排序n 个元素，元素为随机生成的长为1~104 的正整数，n 的取值为： 4 6 8 10 12 14 16 18 20 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 实现算法：直接插入排序，快速排序，基数排序，计数排序。 算法思路： 1. 直接插入排序 插入排序时一个对少量元素进行排序的有效算法，其原理与打牌相 似，每次将新的元素插入已排的序列中，最终得到排序结果。时间复 2 杂度O(n ) 。 2. 冒泡排序 冒泡排序的思路：将待排序的序列分为有序和无序两个子序列，不断 2 将较小元素通过交换到无序子序列首。时间复杂度O(n ) 。 3. 堆排序 堆排序有两个关键操作：建堆、保持和调整大根堆。建堆后，将根节 点与节点n交换，然后“去掉”节点n，再对剩下的节点调整，保持最大 堆性质，如此重复如上操作。时间复杂度O(nlog n) 。 4. 归并排序 算法基础（B） Mini-Project #1 归并排序的操作包括： 分解：将n 个元素分成各含n/2 个元素的子序列。 解决：用归并排序法对两个子序列递归的排序。 合并：合并两个已排序的子序列以得到排序结果。 时间复杂度O(nlog n) 。 5. 快速排序 快速排序的操作包括： 分解：数组A[ p⋯r]被划分成两个子数组A[ p⋯q −1] 和A[q +1⋯r] ，使得 中的每个元素都小于等于 ，而且小于等于 中 A[ p⋯q −1] A[q] A[q+1⋯r] 的元素。下标q 也在划分过程中计算。 解决：通过递归调用快速排序，对子数组A[ p⋯q −1] 和A[q +1⋯r] 排序。 合并：两个子数组都是就地排序，故合并不需操作。 2 最坏时间复杂度O(n ) ，最好时间复杂度O(nlog n) ，平均时间复杂度 O(nlog n) 。 6. 计数排序 假设的整数序列的元素最小值不小于0，最大值不超过k。建立一个长 度为k的线性表C，记录不大于每个值的元素的个数。对于C从头开始 累加，表示出序列中值不大于i的元素的个数。按统计出的值，输出 结果。时间复杂度O(n+k) 。 7. 基数排序 将所有待比较正整数统一为同样的数位长度d，数位较短的数前面补 零。从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高 算法基础（B） Mini-Project #1 位。时间复杂度O (d(n+ k))。 实验结果及分析： 1. 考虑两种计算运行时间的方法： 直接用时