- 浏览: 50419 次
- 性别:
- 来自: 湖南
最新评论
这一段时间都在看TAOCP的排序算法,这些都是我大学生活里面很想看却没看到的部分,同时也为了巩固实践,把它们都写出程序来了。供自己复习之用,也希望能与网友分享。如果有什么问题,还请各位网友能够指正出来。
一、计数排序(位于TAOCP第三卷中的内部排序前面的内容中,是高德纳先生讲的第一种类型的排序方法,其适应面比较窄,但却是很有效。同时可以证明此算法是稳定的)
如果说上面的程序属于“比较计数”[引自TAOCP]的话,那么还有一种方法就是“分布计数”[引自TAOCP]了。
二、比较排序(这也是TAOCP书中讲的第一类排序方法,也是各类数据结构或算法教材必须涉及到的一类算法,过多的解释就无需展开了,让我们来直接用程序对话。)
因为看书的进度比较慢,这些程序就是我先根据算法原理实现了的。后续还有很多排序和查找算法,我还要进一步学习。同时,有关这些算法的优缺点和分析需要做进一步探讨,欢迎各位网友能与多一起学习这等重要基础性知识。我的邮箱地址是:tanzek@gmail.com
一、计数排序(位于TAOCP第三卷中的内部排序前面的内容中,是高德纳先生讲的第一种类型的排序方法,其适应面比较窄,但却是很有效。同时可以证明此算法是稳定的)
<!---->// a数组存储输入数据,count数组用来计数
for(int i=0; i<N-1; i++) {
for(int j=i+1; j<N; j++) {
if(a[i] > a[j]) {
count[i] ++;
} else {
count[j] ++;
}
}
}
// b数组用于存储排序后的数据
for(int i=0; i<N; i++) {
b[count[i]] = a[i];
}
for(int i=0; i<N-1; i++) {
for(int j=i+1; j<N; j++) {
if(a[i] > a[j]) {
count[i] ++;
} else {
count[j] ++;
}
}
}
// b数组用于存储排序后的数据
for(int i=0; i<N; i++) {
b[count[i]] = a[i];
}
如果说上面的程序属于“比较计数”[引自TAOCP]的话,那么还有一种方法就是“分布计数”[引自TAOCP]了。
<!---->for(int i=0; i<N; i++) {
count[a[i]-1] ++;
}
for(int i=u; i<v; i++) {
count[i] += count[i-1]; // 其中count[v-1]=N,且count的下标从u-1至v-1
}
for(int i=N-1; i>=0; i--) {
b[count[a[i]-1]-1] = a[i]; // b的下标从0至N-1
count[a[i]-1] --;
}
需要注意的是,在“分布计数”中的count与“比较计数”中的count的计数方式有一点点不同,所以在最终转换成排序后的数组时也有不同的处理。而且,在“分布计数”中,要求各个记录的键码值最好满足一定的分布条件[u,v],全都在一个比较整齐的区间内。也可以证明,此排序算法是稳定的,主要就是在构成排序数组b时采用的循环是倒序,如果是顺序的话,那就不同了。count[a[i]-1] ++;
}
for(int i=u; i<v; i++) {
count[i] += count[i-1]; // 其中count[v-1]=N,且count的下标从u-1至v-1
}
for(int i=N-1; i>=0; i--) {
b[count[a[i]-1]-1] = a[i]; // b的下标从0至N-1
count[a[i]-1] --;
}
二、比较排序(这也是TAOCP书中讲的第一类排序方法,也是各类数据结构或算法教材必须涉及到的一类算法,过多的解释就无需展开了,让我们来直接用程序对话。)
<!---->for(int i=1; i<N; i++) {
int r = a[i];
int j = i - 1;
while(r < a[j] && j >= 0) {
a[j+1] = a[j];
j --;
}
a[j+1] = r;
}
上面这个是顺序表的直接插入方法,针对于2~N的各个记录,用直接寻找最佳位置的方式来进行排序,寻找过程可以和移动过程(顺序表独有)结合起来,以节省时间。在这种方式下,其实最好采用表方式进行存储。在TAOCP一书中还提到,如果结合二叉插入或“两路”插入的方法,可以进一步节省时间,但是其实质上还是会得不到最终的改善。int r = a[i];
int j = i - 1;
while(r < a[j] && j >= 0) {
a[j+1] = a[j];
j --;
}
a[j+1] = r;
}
<!---->int h[4] = {8, 4, 2, 1}; // shell排序每步步长
for(int ih=0; ih<4; ih++) {
for(int i=h[ih]; i<N; i+=h[ih]) {
int r = a[i];
int j = i - h[ih];
while(r < a[j] && j>=0) {
a[j+h[ih]] = a[j];
j -= h[ih];
}
a[j+h[ih]] = r;
}
}
结合多步长跳跃方式和直接插入方法,就构成了Shell排序方法,也叫做“减少增量的排序”[引自TAOCP]。选择一个较好的增量序列来作为步长,在上述程序中就是h数组,优点是对直接插入方法会有实质性的改进。for(int ih=0; ih<4; ih++) {
for(int i=h[ih]; i<N; i+=h[ih]) {
int r = a[i];
int j = i - h[ih];
while(r < a[j] && j>=0) {
a[j+h[ih]] = a[j];
j -= h[ih];
}
a[j+h[ih]] = r;
}
}
<!---->int t = N-1; // 已经排好序的最低元素下标-1
int temp;
int s;
while(t != 0) {
s = t;
t = 0;
for(int i=0; i<s; i++) { // 如果t以上的元素都已经排好序,则无需再排序了
if(a[i] > a[i+1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
t = i;
}
}
}
上面这个程序是冒泡排序方法,在TAOCP书中讲是第二类排序算法,通过“交换”或“换位”方法来实现。在程序中,t变量是相当于选择最后(假设每一次都是把大元素往后移动)还要排序元素的下标,因此对于t以后的元素就无须再去比较和考察了。因此,冒泡排序也可称为“交换选择”或“扩散”等。int temp;
int s;
while(t != 0) {
s = t;
t = 0;
for(int i=0; i<s; i++) { // 如果t以上的元素都已经排好序,则无需再排序了
if(a[i] > a[i+1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
t = i;
}
}
}
因为看书的进度比较慢,这些程序就是我先根据算法原理实现了的。后续还有很多排序和查找算法,我还要进一步学习。同时,有关这些算法的优缺点和分析需要做进一步探讨,欢迎各位网友能与多一起学习这等重要基础性知识。我的邮箱地址是:tanzek@gmail.com
发表评论
-
项目开发日志杂记
2009-05-04 13:05 928开发日志 0:32 2008-9-18 1、中文 ... -
笔记本维护故障一则
2007-03-18 23:40 672唉呀,今天真的是羞死 ... -
多Web服务器的80端口访问
2007-03-23 11:42 1421写这篇文章,源自于自己的一个需求。这几天一校园WEB站点因为域 ... -
[转]Windows系统文件详细解说
2007-04-02 23:38 584详细的介绍了WINDOWS系统文件的用途,我想各位保存一份以后 ... -
关于Windows文件共享服务的一些问题
2007-04-02 23:44 2478[问题引出]:我刚安装windows2003时,Compute ... -
MS Project 2003的一个问题
2007-04-03 18:04 1001[问题引出]:刚装完MS Project 2003,一运行就出 ... -
IBM xSeries服务器安装内存一则
2007-04-04 00:55 771部门进购IBM xSeries 225服务器已经达三年之久了, ... -
JAVA与蓝牙起步(Getting Started with Java and Bluetooth)
2007-04-26 00:39 1469栈初始化在你做任何事之前,你需要初始化你的栈。记住,栈是一个用 ... -
Windows 2000下的远程桌面工具
2007-04-28 18:10 971在Windows XP之后的系统中都会在“系统”属性中可以设置 ... -
最近在看的书
2007-06-25 03:17 6141、JSP网络开发技术与整合应用 ... -
想看的书---<<开发自己的搜索引擎---Lucene 2.0 + Heritrix>>
2007-06-26 21:47 1690开发自己的搜索引擎---Lucene 2.0 + Heritr ... -
数据挖掘相关
2007-06-27 08:43 713什么是规则?就是一个条件和一个结果的和:If con ... -
不要用浏览器来测试
2007-07-03 11:02 887进行B/S系统编程,大概浏览器就是最直接的测试程序是否正确的方 ... -
Big-Endian And Little-Endian
2007-07-07 11:32 825今天老师给我们复习单片机,出了一个题目,就这个字节存储顺序搞得 ... -
MySQL的中文问题
2007-07-08 21:12 695唉,看到网上这么多的关于MySQL中文编码的问题。今天自己碰到 ... -
[转]RAW FileSystem Recovery
2007-07-11 09:09 961To know ho ... -
关于人工神经网络中的M-P模型的一点疑问
2007-08-08 22:31 892人工神经网络M-P模型构成一个逻辑非模型,从书中抄下来的,如下 ... -
JOONE(Java Object-Oriented Network Engine)使用初探
2007-09-30 16:03 12361 /**/ ... -
OpenGL in VC++
2008-01-19 00:30 960首先看一个简单的例子: 1 #include <wind ... -
VC++中的ON_COMMAND_RANGE宏
2008-01-26 13:51 1718VC++中的ON_COMMAND_RANGE宏 ...
相关推荐
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 ...
《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 ...
《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 ...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了...
Sedgewick之巨著,与高德纳TAOCP一脉相承 几十年多次修订,经久不衰的畅销书 涵盖所有程序员必须掌握的50种算法 内容简介 《算法(第4版)》全面讲述算法和数据结构的必备知识,具有以下几大特色。 1、 ...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 ...
《算法 第4版 》是Sedgewick之巨著 与高德纳TAOCP一脉相承 是算法领域经典的参考书 涵盖所有程序员必须掌握的50种算法 全面介绍了关于算法和数据结构的必备知识 并特别针对排序 搜索 图处理和字符串处理进行了论述 ...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...
算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了...
《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行...