数据结构第一章导论
基数排序
先将最高位选择,放入0到9三个桶中,在对下一位进行排序,直至形成一个有序数列
数据结构第一章导论
GCP问题
- Welch Powell法
a).将G的结点按照度数递减的次序排列.
b).用第一种颜色对第一个结点着色,并按照结点排列的次序
对与前面着色点不邻接的每一点着以相同颜色.
c).用第二种颜色对尚未着色的点重复步骤b).用第三种颜色
继续这种作法, 直到所有点着色完为止. - 回朔法
从根节点开始，对根节点用第一种颜色进行着色，第一个肯定着色有效，接下去接着对下一个节点着色，先用第一种颜色对其节点着色，然后判断这个节点与相邻节点是否相同，有相同颜色则判定为无效着色，继续用第二种颜色着色，直到着色有效为止，如果与相邻节点颜色没有相同，则判定为有效着色，继续下一节点着色。
时间复杂度
- 总的执行次数为1-n的和,n*(1+n)/2,时间复杂度为O(n^2)
- 归并排序法在最坏情况下的时间复杂度是nlgn
- 冒泡排序和插入排序法最坏的情况下时间复杂度是n^2
常用排序算法的性能与待排数组的循序的关系作一个总结：
1）冒泡：无关；
2）选择：无关；
3）插入：有关，有序程度越大，比较越少；
4）shell：有关，它的基本思想基于插入排序；
5）合并：有关，有序程度愈大，合并过程的比较次数越少；
6）堆排序：有关，有序程度越大，建立堆下沉操作越少；
7）快排序：有关，如果选择最后值作为阀值，那么有序程度越好，就越可能退化成O(n^2)(冒泡排序)；
Shell排序<希尔排序>
- Shell排序算法的时间复杂度约为O（n（ldn）2）
- Shell排序的时间性能优于直接插入排序
- Shell 最初建议步长选择为n/2，并且对步长取半直到步长达到 1
将一个无序数列分为n/2组,第一个和第n/2+1一组,第二个和第n/2+2个一组,是否交换,直至交换完成,再将组变少(n/4),每组内的成员变多,继续交换,(n/8…1),直至完成排序.