考试网 >> IT认证 >> 水平 >> 软件指导 >> 程序员数据结构笔记(二)

发布时间：2006-06-28 04:46     点击：

　　排序　　

　　　　\ 不稳定　* * * * * * * * 15 15 * * * *(前后改变)

　　经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。

　●锦标赛排序方法：　13　　16　　11　　18　　21　　3　　17　　6 

　　　　　　　　　　　　 \　　/　　　\　　/　　　\　 /　　　 \　/

　　　　　　　　　　　　　 13　　　　　11　　　　　3　　　　　 6 

　　　　　　　　　　　　　　\　　　　　/　　　　　　\　　　　 /

　　　　　　　　　　　　　　　　　11　　　　　　　　　　　3

　　　　　　　　　　　　　　　　　 \　　　　　　　　　　 /

　　　　　　　　　　　 　　　　　　　　　　　　3（胜出，将其拿出，并令其为正无穷&Go On）

　　●归并排序方法：　　13　　16　　11　　18　　21　　3　　17　　6 

　　　　　　　　　　　　 \　　/　　　\　　/　　　\　 /　　　\　 /

　　　　　　　　　　　　　13,16　　　 11,18　　　 3,21　　　 6,17

　　　　　　　　　　　　　　\　　　　　/　　　　　　\　　　　 /

　　　　　　　　　　　　　　11,13,16,18　　　　　　　3,6,17,21

　　　　　　　　　　　　　　　　　\　　　　　　　　　　 /

　　　　　　　　　　　　　　　　　 3,6,11,13,16,17,18,21

　　●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全)

　　　　　　　　　2）共排m趟，其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。

　　　　　　 　　程序如下： for(i=0;i<m;i++)

　　　　　　　　　　　　　　{for(j=0;j<d[i];j++)

　　　　　　　　　　　　　　　{对第i个子序列进行直接插入排序；　

　　　　　　　　　　　　　　　　　　注意：下标之差为D[i];

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。