Posted on 2008-11-22 04:37
tanzek 阅读(2875)
评论(2) 编辑 收藏 所属分类:
读书记录
这一段时间都在看TAOCP的排序算法，这些都是我大学生活里面很想看却没看到的部分，同时也为了巩固实践，把它们都写出程序来了。供自己复习之用，也希望能与网友分享。如果有什么问题，还请各位网友能够指正出来。
一、计数排序（位于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];
}
如果说上面的程序属于“比较计数”[引自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时采用的循环是倒序，如果是顺序的话，那就不同了。
二、比较排序（这也是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 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数组，优点是对直接插入方法会有实质性的改进。
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以后的元素就无须再去比较和考察了。因此，冒泡排序也可称为“交换选择”或“扩散”等。
因为看书的进度比较慢，这些程序就是我先根据算法原理实现了的。后续还有很多排序和查找算法，我还要进一步学习。同时，有关这些算法的优缺点和分析需要做进一步探讨，欢迎各位网友能与多一起学习这等重要基础性知识。我的邮箱地址是：tanzek@gmail.com