计数排序以及标准库排序算法.docVIP

基数排序和使用STL排序算法 前提，目标和结果 前提: 学生应该具有如下知识 基数排序 – 有关基数排序算法的知识 C++ 标准模板库(STL)– 有关C++标准模板库的用法 C++ 函数指针 – 有关C++函数指针的基本概念 目标: 本次作业用于加强学生对于基数排序的理解，该算法的时间复杂度是. 作为排序部分的最后一次作业，要求学生掌握STL中排序算法的使用。 结果: 学生独立完成本次作业应该有如下收获： 加深了对于线性排序算法的理解 掌握了STL中相关排序算法的使用 背景 基数排序 基数排序算法首先从最小显著特征开始，排序，然后再将所有的数据组合起来。例如，如果关键码有5位，则首先从1位开始，然后计算10位，…，最后计算10,000位。在该排序算法中，需要不停的分割和重新组合操作。最后达到排序的目的（是稳定的）。 一个简单的例子，为了简单起见，每个位只有三个可能的取值。 初始化数据 第一轮 第二轮 最后一轮 组合 123 231 111 111 111 222 111 312 113 113 312 121 113 121 121 113 + + 123 123 231 222 121 + 222 111 312 222 222 231 333 + 123 231 312 121 123 + + 333 113 231 312 333 333 333 STL排序算法 在头文件algorithm中定义了一系列的算法，这些算法都是针对一个容器的一部分数据进行操作的。 一个区间是一个对象的序列，这些序列可以通过迭代器或者是指针去访问，例如数组或者是STL中的容器对象。注意，这些操作，只会影响数据中的值，而并不会影响容器的其他结构（它不会影响容器的大小或者是空间分派）。 STL中一共有五个排序算法，这些算法的函数原型如下表所示： sort 对一个区间的元素进行排序 stable_sort 对于一个区间的元素进行排序，该算法是稳定的 partial_sort 部分元素排序算法 partial_sort_copy 复制和部分排序算法 nth_element 对区间数据进行排序 Sort template class RandomAccessIterator void sort ( RandomAccessIterator first, RandomAccessIterator last ); template class RandomAccessIterator, class Compare void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); 描述 对区间[first,last)内的元素进行排序，按照升序的顺序。其中的元素是通过运算符来进行比较的，在第二个版本中是通过函数comp来进行比较的。相等的元素并不能保证能够保持原来的顺序。 参数 first, last 随机访问迭代器用来指示第一个和最后一个进行排序的位置。在排序中使用的区间为[first,last), 该区间包含第一个元素，但没有包含最后一个元素。 comp 进行比较的函数对象，它将两个容器中的类型的对象作为参数，返回true如果第一个参数参数按照定义的序列应该在前面，否则的话返回false。 stable_sort template class RandomAccessIterator void stable_sort ( RandomAccessIterator first, RandomAccessIterator last ); template class RandomAccessIterator, class Compare void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); 描述 将在区间 [first,last) 内的元素排列为一个上升的顺序，很像函数sort，但是stable_sort函数保证了稳定性。在第一个版本中这些元素都是通过操作符来进行比较的，而在第二个版本中是通过comp函数进行比较的。 参数 first, last 随机访问迭代器指出了第一个和最后一个需要访问的序列的位置。这个区间为[first,last)其中包含第一个元素first，但是不包含最后一个元素last所指的位置。 comp 进行比较的函数对象，取该区间内的两个数据作为参数，返回true如果按照定义的序列，第一个参数应该