算法与分析实验3： 利用预排序、堆排序和计数排序解决排序问题

算法与分析实验3 利用预排序、堆排序和计数排序解决排序问题 一、实验目的 1. 掌握变治法和时空权衡的思想与实现。 2. 掌握利用利用变治法和时空权衡的思想来解决排序问题。 3. 分析核心代码的时间复杂度和空间复杂度。 二、实验内容和要求 基于预排序算法、堆排序算法和计数排序算法分别编写一个排序算法。 【预排序函数原型及功能说明】 检验数组中元素的唯一性: 先对数组排序，然后只检查它的连续元素:如果该数组有相等的元素，则一定有一对元素是相互紧挨着的，反之亦然。 算法 PresortElementUniqueness PresortElementUniqueness (A[0..n-1]) //先对数组排序来解元素唯一性问题 //输入:n 个可排序元素构成的一个数组 A[0..n-1] //输出:如果A没有相等的元素，返回 true，否则返回 false对数组A排序 for i←0 to n-2 do if A[i]= A[i+1] return false return true 【核心函数实现代码及时间复杂度与空间复杂度分析】