(一)目标
在实际问题的解决过程中,我们发现,很多问题都可以归结为对数据的排序和查询。而查询的效率则在很大程度上依赖于排序的效率;尤其是在数据量达到海量级的时候。因此,设计一个有效的排序算法是至关重要的。本文设计了一个通用的c++ quicksort 模板类。通过简单的提供一个Data类,可以实现任意数据的快速排序算法,提高了开发效率。
(二)快速排序算法的思想
最基本的快速排序的思想是基于分治策略的:
对于输入的子序列L[p..r],如果规模足够小则直接进行排序,否则分三步处理:
1 分解(Divide):将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r], 使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
2 递归求解(Conquer):通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
3 合并(Merge):由于对分解出的两个子序列的排序是就地进行的, 所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
(三)准备工作和源代码
1 使用vc6建立console工程
2 加入下面的模板类:
// 切分数据为左右两个部分,返回中间元素x的编号
// 主要的过程就是:选择一个元素x作为分界点,将比x大的元素放到x右边,其余放到x左边。
以上就实现了快速排序的模板类。
3 数据类接口的实现
从上面模板类的实现我们可以看出,为了使用这个模板类对某种类型的数据数组DataType * data进行排序,我们必须实现DataType的接口CompareTo(比较两个DataType 元素a,b的大小,a>b返回1,a==b返回0,否则返回-1)。
举个例子来说:现在要排序二维点坐标,定义大小关系是:先比较x轴坐标值大小,x相同的话,由y值大小决定大小关系。即:(1,1) == (1,1) , (2,1) > (1, 10) , (3, 5) < (4, 1)。
此外:还必须实现DataType类型的无参数的默认构造函数(因为模板类中要使用)。
定义数据类型MyPoint如下:
(四)测试
下面是用于测试的主函数:
结果输出如下:
before quicksort:
0 <-------> (1,1)
1 <-------> (2,5)
2 <-------> (7,11)
3 <-------> (100,2)
4 <-------> (1,7)
5 <-------> (9,32)
6 <-------> (7,1)
7 <-------> (2,2)
8 <-------> (1,1)
9 <-------> (9,5)
after quicksort:
0 <-------> (1,1)
1 <-------> (1,1)
2 <-------> (1,7)
3 <-------> (2,2)
4 <-------> (2,5)
5 <-------> (7,1)
6 <-------> (7,11)
7 <-------> (9,5)
8 <-------> (9,32)
9 <-------> (100,2)
请按任意键继续 . . .
(五)说明
本文根据快速排序算法,实现了一个c++快速排序模板类。使用这个模板类,并遵守欲排序数据类型必须实现的接口定义,就能实现对任意数据类型的快速排序。当然,本文的例子只是一个基本的引导。
分享到:
相关推荐
用模板类实现的一个简易的c++程序,实现了快速排序。
这是我用c++语言编写的一个模板类,主要封装了各种排序方法(直接插入、二分插入、简单交换、冒泡、简单选择、快速排序、归并排序、堆排序),并能统计所用时间以及排序所用的交换次数、比较次数,在Visual stidio ...
C++模板类实现的动态数组、双向循环链表、队列、栈等数据结构,以及基于迭代器的静态查找和排序算法,包括顺序查找、折半查找、简单选择排序(用于单向迭代器)、快速排序(双向迭代器)、堆排序(随机迭代器)。...
C++模板类实现的动态数组、双向循环链表、队列、栈等数据结构,以及基于迭代器的静态查找和排序算法,包括顺序查找、折半查找、简单选择排序(用于单向迭代器)、快速排序(双向迭代器)、堆排序(随机迭代器)
1.1 编写简单的C++程序 2 1.2 初窥输入/输出 5 1.2.1 标准输入与输出对象 5 1.2.2 一个使用IO库的程序 5 1.3 关于注释 8 1.4 控制结构 10 1.4.1 while语句 10 1.4.2 for语句 12 1.4.3 if语句 14 1.4.4 读入未知数目...
*5.6 C++处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...
为可能 这一章利用多继承和虚拟继承 把第 16 章的模板类例子扩展成一个三层的类模板层 次结构 第 19 章介绍 RTTI 运行时刻类型识别 设施 使用 RTTI我们的程序在执行过程中可 以查询一个多态类对象的类型 例如 ...
18.2.3 快速排序 18.2.4 选择 18.2.5 相距最近的点对 18.3 解递归方程 18.4 复杂度的下限 18.4.1 最小最大问题的下限 18.4.2 排序算法的下限 第19章 动态规划 19.1 算法思想 19.2 应用 19.2.1 0/1背包问题 19.2.2 ...
11.2.2 快速排序 312 11.2.3 基数排序 319 11.3 各种排序算法的比较 321 C++片段4 类关系和重用 325 C4.1 回顾继承 326 C4.1.1 类的公有、私有和受保护部分 331 C4.1.2 公有、私有和受保护继承 332 C4.1.3 is...
*5.6 C++处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...
快速排序.mp4 11.归并排序.mp4 12.顺序栈.mp4 13.顺序队列.mp4 14.链表的基本概念.mp4 15.单链表的基本运算.mp4 16.循环单链表.mp4 17.双向链表.mp4 18.链式栈.mp4 19.链式队列.mp4 20.基数排序.mp4 21....
《Visual C++编程技巧精选500例》pdf Visual C++编程技巧精选500例.pdf 第1章 消息框 001 如何创建消息框? 002 如何设置消息框标题? 003 如何使用资源串创建消息框? 004 如何使用资源串动态显示消息框内容? 005 如何...
23_案例_数组模板类_数组元素存储的是类对象思想抛砖_传智扫地僧 24_作业 代码 文档 01_泛型编程_知识点梳理 02_模板数组类_作业讲解和思想强化(数据类型和算法的分离)_传智扫地僧 03_类型转换_static_cast和...
为PDF文件增加了目录,便于快速浏览。 摘录一些不知道以及没有做到的: 1、防止多重包含(头文件的形式不能完美做到) 所有头文件都应该使用#define防止头文件被多重包含(multiple inclusion),命名格式当是:...
内容及步骤: 1、 设计一个图的类,采用临接表法进行存储,该图每个结点的数据类型类模板的模板参数进行定义(注:需先设计一个结点类Node); 2、 为该类分别设计一个实现深度优先搜索和广度优先搜索的成员...
7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 间接排序 7.8.1 vector*>不运行 7.8.2 智能指针类 7.8.3 重载operator 7.8.4 ...
7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 间接排序 7.8.1 vector*>不运行 7.8.2 智能指针类 7.8.3 重载operator 7.8.4 使用“*...
C++ STL使用技巧 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS 树与图的遍历:拓扑排序 最短路 最小生成树 二分图:染色法、匈牙利算法 数学知识 —— 代码模板链接 常用代码模板4——数学...