2015年初级软考辅导:程序员数据结构笔记（三）
发布时间：2010/3/13 14:17:05 来源：城市学习网 编辑：MOON
排序查找是我自己觉得最头疼的算法了，常搞混去的啊.不知道各位学得如何，如果不错，还请告诉我一些经验!
查找
一、知识点/静态查找->数组
1、什么是查找
“动态查找->链树
顺序查找，时间复杂度O
折半查找：条件：有序；时间复杂度O
索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素。
算法：根据index来确定X所在的块（i）时间复杂度：m/2
在第Ｉ块里顺序查找X时间复杂度：n/2
总的时间复杂度：/2
二叉排序树1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。
2）特点：中序遍历有序->（删除节点用到此性质）
3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。
4）结点的插入->二叉排序树的构造方法
5）结点删除（难点）1、右子树放在左子树的最右边
2、左子树放在右子树的最左边
avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。
B树：n阶B树满足以下条件1）每个结点（除根外）包含有N～2N个关链字。2）所有叶子节点都在同一层。
3）B树的所有子树也是一棵B树。
特点：降低层次数，减少比较次数。
排序
一、知识点
1、排序的定义
/内排序：只在内存中进行
2、排序的分类
“外排序：与内外存进行排序
内排序：/直接插入排序
1）插入排序
“shell排序
/冒泡排序
2）交换排序
“快速排序
/简单选择排序
3）选择排序堆
“锦标赛排序
4）归并排序（二路）
5）基数排序（多关链字排序）
3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）
1515
/稳定1515
排序
“不稳定1515
经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。
锦标赛排序方法：13161118213176
“/“/“/“/
131136
“/“/
113
“/
3（胜出，将其拿出，并令其为正无穷&GoOn）
归并排序方法：13161118213176
“/“/“/“/
13，1611，183，216，17
“/“/
11，13，16，183，6，17，21
“/
3，6，11，13，16，17，18，21
shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1
2）共排m趟，其中第i趟增量为D[i]，把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。
程序如下：for
}
快速排序data
di->13161118213176248<-j
先从后往前找，再从前往后找。
思想：空一个插入一个，i空j挪，j空i挪（这里的i，j是指i，j两指针所指的下标）。
一次执行算法：1）令temp=d[0]，i=0，j=n-1;
2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置i往后挪。
3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;)
4）当i=j时，结束循环。d[i]=temp；
再用递归对左右进行快速排序，因为快速排序是一个典型的递归算法。
堆排序
定义：d[n]满足条件：d[i]<d[2i+1]&&d[i]<d[2i+2]大堆（上大下小）
d[i]>d[2i+1]&&d[i]>d[2i+2]小堆（上小下大）
判断是否为堆应该将其转换成树的形式。总共排序n-1次
调整
程序:flag=0;
while
}
else
flag=1;//是堆
}
堆排序过程：
基数排序
扑克:1)大小->分配
2)花色->分配，收集
思想:分配再收集.
构建链表:链表个数根据关键字取值个数有关.
例:将下面九个三位数排序:
321214665102874699210333600
定义一个有十个元素的数组:
a[0]aaaaaaaaa
第一趟:210321102333214665699
600874
结果:210600321102333214874665699
第二趟:600210321333665874699
102214
结果:600102210214321333665874699
第三趟:102210321600874
214333665
699
结果:102210214321333600665699874
最近在看一位程序员的笔记，也挺不错的啊.这应当是他的网站.他总说他的网站人气不够，现在顺便就帮他宣传一下啦！"target=_self>
