Java与算法(二)
六八皇后问题
如果动手来摆放皇后，可以用这样一种思路：在最左侧一列放下一个皇后，然后在右边一列从上到下找到第一个与左边皇后不冲突的位置，摆放第二个皇后；再向yo一列，从上到下找到第一个与前两个皇后不冲突的位置摆放第三个皇后，依次类推，直到在最后一列摆下第八个皇后。
认真思考的话，可以发现这仍然是深度优先搜索的思路，即步步推进，下一步做的事情和当前是一样的。代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassDfsEightQueens{
int[]queens=newint[8];//记录每一列皇后的摆放位置
intcount=0;//摆法总数
publicvoiddfs(intcolumn){
if(column==8){//8个皇后都已经摆放
count++;
System.out.println("第"+count+"种方法:");
print();
return;
}
for(inti=0;i<8;i++){
queens[column]=i;//在该列的第i行上放置皇后
if(isValid(column))//检查摆放在该位置是否与前column-1列的皇后有冲突
dfs(column+1);//没有冲突则开始下一列8个位置的尝试
}
}
privatebooleanisValid(intcolumn){
for(inti=0;i
if(queens[i]==queens[column])//两个皇后在同一行上
returnfalse;
if(Math.abs(queens[i]-queens[column])==(column-i))//两个皇后在同一对角线上
returnfalse;
}
returntrue;
}
privatevoidprint(){
for(inti=0;i<8;i++){
for(intj=0;j<8;j++){
if(queens[i]==j)
System.out.print("");
else
System.out.print("_");
}
System.out.println();
}
}
publicstaticvoidmain(String[]args){
DfsEightQueensq=newDfsEightQueens();
q.dfs(0);
System.out.println("共"+q.count+"种摆放方法");
}
}
输出：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
共92种摆放方法
七完全二叉树
树
下图是一“棵”树的样子。树这个名称起的很形象，整个数据结构由根、枝、叶组成，其中1为根节点，2、3是1的子节点，4、5、6、8、9、10这几个没有子节点的节点称为叶节点。
节点的度：一个节点的子树的数量称为该节点的度。例如，图中节点2的度为3，节点3的度为2。
树的度：一棵树的度是指该树中节点的最大度数。如图中树的度是3。
节点的层数：每个节点都处在一定的层次上，图中根节点在第1层，2、3节点在第二层。
树的深度：一棵树中节点的最大层数称为树的深度。如中所示的树的深度为4。
二叉树
二叉树是一种特殊的树，特点是每个节点最多有两个子节点。上图中的树去掉节点4就符合二叉树的定义了，如下图：
完全二叉树
除二叉树最后一层外，其他各层的节点数都达到最大个数，且最后一层从左向右的叶节点连续存在，只缺右侧若干节点，就是完全二叉树。
如下图，每一层都是从左向右摆放节点，每个节点都是摆满两个子节点后才向右移动到下一个节点，一层摆满后向下移动一层，直到摆放完所有数字。这样得到的二叉树就是完全二叉树，中间有任何缺失的节点就不能称为完全二叉树。
完全二叉树的一个重要特性就是节点编号的规律，这是理解完全二叉树构建程序的根本。看上图，仍然按照从左到右、从上到下的规律从1开始为节点编号，图中节点上的数字正好与节点编号相同，可以看出：
如果一个父节点的编号是x，那么它左子节点的编号就是2x，右子节点的编号就是2x+1。
在程序中，二叉树通常采用链式结构存储，链中的每一个节点由节点数据、左子节点指针、右子节点指针组成
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
classNode{
NodeleftChild;
NoderightChild;
intdata;
publicNode(intdata){
this.data=data;
}
}
有时候为了查找父节点方便，还可以为节点定义增加一个指向父节点的指针。
假设要用1-9这九个数字构建二叉树，那么先创建好九个节点，然后设置这些节点的左右子节点指针。观察多个节点数不等的完全二叉树可以得出规律，对于x个节点组成的二叉树，只有前x/2(取整)个节点具有子节点，且第x/2个节点可能只有左子节点。
理解了这些后，代码就很简单了
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
importjava.util.LinkedList;
importjava.util.List;
/
Createdbyautfishon2016/9/13.
/
publicclassBinTreeByList{
Listnodes=null;
privateint[]datas=null;
privateintnumber;
publicBinTreeByList(int[]datas){
this.datas=datas;
this.number=this.datas.length;
}
publicvoidcreate(){
nodes=newLinkedList<>();
for(inti=0;i
nodes.add(newNode(datas[i]));
}
//如果父节点编号为x,那么左子节点的编号是2x,右子节点的编号是2x+1
for(intnoteId=1;noteId<=this.number/2;noteId++){
//索引从0开始,需要在节点编号上减1
nodes.get(noteId-1).leftChild=nodes.get(noteId2-1);
if(noteId2
nodes.get(noteId-1).rightChild=nodes.get(noteId2);
}
}
privatestaticclassNode{
NodeleftChild;
NoderightChild;
intdata;
publicNode(intdata){
this.data=data;
}
}
}
接下来的问题是，二叉树是非线性结构，如果拿到一个已经构建好的二叉树结构，如何遍历其全部节点呢。遍历的定义是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。
先看概念：
先序遍历（DLR）：称为先根次序遍历，即先访问根节点，再按先序遍历左子树，最后按先序遍历右子树。
中序遍历（LDR）：称为中根次序遍历，即先按中序遍历左子树，再访问根节点，最后按中序遍历右子树。
后序遍历（LRD）：称为后根次序遍历，即先按后序遍历左子树，再按后序遍历右子树，最后访问根节点。
三种方式遍历的代码如下：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicvoidpreOrder(Nodenode){
if(node==null){
return;
}
System.out.print(node.data+"");
preOrder(node.leftChild);
preOrder(node.rightChild);
}
publicvoidinOrder(Nodenode){
if(node==null){
return;
}
inOrder(node.leftChild);
System.out.print(node.data+"");
inOrder(node.rightChild);
}
publicvoidpostOrder(Nodenode){
if(node==null){
return;
}
postOrder(node.leftChild);
inOrder(node.rightChild);
System.out.print(node.data+"");
}
测试代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{1,2,3,4,5,6,7,8,9};
BinTreeByListtree=newBinTreeByList(numbers);
tree.create();
System.out.print("先序遍历");
tree.preOrder(tree.nodes.get(0));
System.out.println();
System.out.print("中序遍历");
tree.inOrder(tree.nodes.get(0));
System.out.println();
System.out.print("后续遍历");
tree.postOrder(tree.nodes.get(0));
}
输出：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
先序遍历124895367
中序遍历849251637
后续遍历894526371
其实，完全二叉树还有一种更简单的存储方式，即一维数组。也就是说int[]{1,2,3,4,5,6,7,8,9}本身就是一个完全二叉树了。
根据数字在数组中的索引即可以计算出数字的节点位置，而且仍然可以对这个二叉树做三种方式的遍历。
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
/
完全二叉树
Createdbyautfishon2016/9/8.
/
publicclassBinTreeByArray{
privateint[]numbers;
publicBinTreeByArray(int[]numbers){
this.numbers=numbers;
}
/
先序遍历
根节点->遍历左子树->遍历右子树
@paramnodeId
/
publicvoidpreOrder(intnodeId){
if(nodeId<=numbers.length){
System.out.print(numbers[nodeId-1]+"");
preOrder(nodeId2);
preOrder(nodeId2+1);
}
}
/
中序遍历
左子树->父节点->右子树
@paramnodeId
/
publicvoidinOrder(intnodeId){
if(nodeId<=numbers.length){
inOrder(nodeId2);
System.out.print(numbers[nodeId-1]+"");
inOrder(nodeId2+1);
}
}
/
后续遍历
左子树->右子树->父节点
@paramnodeId
/
publicvoidpostOrder(intnodeId){
if(nodeId<=numbers.length){
postOrder(nodeId2);
inOrder(nodeId2+1);
System.out.print(numbers[nodeId-1]+"");
}
}
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{1,2,3,4,5,6,7,8,9};
for(intx=0;x
System.out.print(numbers[x]+"");
}
System.out.println();
BinTreeByArraytree=newBinTreeByArray(numbers);
System.out.print("先序遍历");
tree.preOrder(1);
System.out.println();
System.out.print("中序遍历");
tree.inOrder(1);
System.out.println();
System.out.print("后续遍历");
tree.postOrder(1);
}
}
用数组存储二叉树的一个常见应用就是堆排序，下文分解。
八堆排序
堆是一种特殊的完全二叉树，其特点是所有父节点都比子节点要小，或者所有父节点都比字节点要大。前一种称为最小堆，后一种称为最大堆。
比如下面这两个：
那么这个特性有什么作用？既然题目是堆排序，那么肯定能用来排序。想要用堆排序首先要创建一个堆，如果对4362715这七个数字做从小到大排序，需要用这七个数创建一个最大堆，来看代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassHeapSort{
privateint[]numbers;
privateintlength;
publicHeapSort(int[]numbers){
this.numbers=numbers;
this.length=numbers.length;
}
/
调整二叉树
如果父节点编号为x,那么左子节点的编号是2x,右子节点的编号是2x+1
节点编号从1开始,对应数组中的索引是编号-1
@paramnodeId节点编号,从1开始
/
publicvoidadjust(intnodeId){
intswapId;
intflag=0;//是否需要继续向下调整
while(nodeId2<=this.length&&flag==0){
//首先判断它和左子节点的关系,并用swapId记录值较小的节点编号(最大堆是记录较大的)
intindex=nodeId-1;//节点对应数组中数字的索引
intleftChild=nodeId2-1;//左子节点对应数组中数字的索引
intrightChild=nodeId2;//右子节点对应数组中数字的索引
if(numbers[index]
swapId=nodeId2;
}else{
swapId=nodeId;
}
//如果有右子节点,再与右子节点比较
if(nodeId2+1<=this.length){
if(numbers[swapId-1]
swapId=nodeId2+1;
}
//如果最小的节点编号不是自己,说明子节点中有比父节点更小的
if(swapId!=nodeId){
swap(swapId,nodeId);
nodeId=swapId;
}else{
flag=1;
}
}
}
/
交换两个节点的值
@paramnodeId1
@paramnodeId2
/
publicvoidswap(intnodeId1,intnodeId2){
intt=numbers[nodeId1-1];
numbers[nodeId1-1]=numbers[nodeId2-1];
numbers[nodeId2-1]=t;
}
/
创建最大堆
/
publicvoidcreateMaxHeap(){
//从最后一个非叶节点到第一个节点依次向上调整
for(inti=this.length/2;i>=1;i--){
adjust(i);
}
}
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{4,3,6,2,7,1,5};
for(intx=0;x
System.out.priwww.shanxiwang.netnt(numbers[x]+"");
}
System.out.println();
HeapSortheap=newHeapSort(numbers);
heap.createMaxHeap();
}
}
对本例中的数列，从this.length/2到1，共执行了三轮循环。
调整完成后，当前的二叉树已经符合最大堆的特性，可以用来从小到大排序。堆排序的原理是，交换堆顶和最后一个节点的数字，即把最大的数字放到数组最后，然后对除了最大数的前n-1个数从新执行调整过程，使其符合最大堆特性。重复以上过程直到堆中只剩下一个数字。
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicvoidsort(){
while(this.length>1){
swap(1,this.length);
this.length--;
adjust(1);
}
for(intx=0;x
System.out.print(numbers[x]+"");
}
}
堆排序的时间复杂度和快速排序的平均时间复杂度一样，是O(nlogn)。
九直接插入排序
直接插入排序是最简单的排序算法，也比较符合人的思维习惯。想像一下玩扑克牌抓牌的过程。第一张抓到5，放在手里；第二张抓到3，习惯性的会把它放在5的前面；第三张抓到7，放在5的后面；第四张抓到4，那么我们会把它放在3和5的中间。
直接插入排序正是这种思路，每次取一个数，从前向后找，找到合适的位置就插进去。
代码也非常简单：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
/
直接插入排序法
Createdbyautfishon2016/9/18.
/
publicclassInsertSort{
privateint[]numbers;
publicInsertSort(int[]numbers){
this.numbers=numbers;
}
publicvoidsort(){
inttemp;
for(inti=1;i
temp=this.numbers[i];//取出一个未排序的数
for(intj=i-1;j>=0&&temp
this.numbers[j+1]=this.numbers[j];
this.numbers[j]=temp;
}
}
System.out.print("排序后:");
for(intx=0;x
System.out.print(numbers[x]+"");
}
}
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{4,3,6,2,7,1,5};
System.out.print("排序前:");
for(intx=0;x
System.out.print(numbers[x]+"");
}
System.out.println();
InsertSortis=newInsertSort(numbers);
is.sort();
}
}
测试结果：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
排序前:4362715
排序后:1234567
直接插入排序的时间复杂度，最好情况是O(n)，最坏是O(n^2)，平均O(n^2)。
十希尔排序
希尔排序是插入排序的一种，是直接插入排序的改进版本。
对于上节介绍的直接插入排序法，如果数据原来就已经按要求的顺序排列，则在排序过程中不需要进行数据移动操作，即可得到有序数列。但是，如果最初的数据是按倒序排列的，则在进行插入排序时每次的比较都需要向后移动数据，这样，将导致算法的效率很低。
希尔排序的思想是把数列划分为若干个较小的数列，对每组数列使用直接插入排序算法排序，随着增量逐渐减少，每组包含的数字越来越多，当增量减至1时，整个数列恰被分成一组，最后再使用一次直接插入排序对整个数列进行排序。
例如有4,3,6,2,7,1,5,8八个数字，第一次分成四组，即8/2组。如下图，相同颜色的数字为一组，下标为x的数字和下标为x+4的数字为一组。
对这四个数组分别做直接插入排序，即两两比较，如果大的在前则交换位置，得到：
然后缩小组数，4/2=2，缩小为两组。如下图：
对这两个数组分别做直接插入排序，得到：
再次缩小组数，2/2=1，缩小为一组，那么所有数字都。如下图：
最后，对4,1,5,2,6,3,7,8这个数列执行一次直接插入排序。
总结上面的规律，可以得出：
第一次分组数s=n/2==0?n/2:n/2+1
取数规则是[x]和[x+n/2]为一组
当然，这只是比较简单的分组方式，不一定是最优的。来看代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
publicclassShellSort{
privateint[]numbers;
publicShellSort(int[]numbers){
this.numbers=numbers;
}
/
对数组分组并对每个组做直接插入排序,完成后缩小组的数量,重复插入排序,直到缩小到一个组
第一次分组数:section=n/2==0?n/2:n/2+1,分组规则:每隔n/2挑一个数,即[x]和[x+n/2]为一组
/
publicvoidsort(){
intsection=this.numbers.length/2;
intj;
inttemp;
while(section>=1){
for(inti=section;i
temp=this.numbers[i];
j=i-section;
while(j>=0&&this.numbers[j]>temp){
this.numbers[j+section]=this.numbers[j];
j=j-section;
}
this.numbers[j+section]=temp;
}
section/=2;
}
System.out.print("排序后:");
for(intx=0;x
System.out.print(numbers[x]+"");
}
}
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{4,3,6,2,7,1,5,8};
System.out.print("排序前:");
for(intx=0;x
System.out.print(numbers[x]+"");
}
System.out.println();
ShellSortss=newShellSort(numbers);
ss.sort();
}
}
运行：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
排序前:43627158
排序后:12345678
希尔排序的时间复杂度，最坏是O(n^2)，平均O(n^3/2)。
十一合并排序
天下事，合久必分，分久必合。合并排序的基本思想正是先分再合。
例如对3,1这个数列排序，首先是分，分为3和1两个数列，然后再合并并排序。合并需要额外的辅助空间，即建立一个两个数列长度之和的空数组用于存储合并结果。
合并分为三步：
1）两个数列在起始位置各分配一个"指针"，对比指针位置的数字，取较小的数字存入辅助数组。数字被移出的一侧，指针右移一格，再次比较两个指针位置的数字，直到某一侧的指针移出数组以外结束。
2）把左侧数组剩余的数字按顺序移动到辅助数组中
3）把右侧数组剩余的数字按顺序移动到辅助数组中
过程如下图：
下面把两个数组的长度都增加到2，再看一下合并过程：
观察一下这个流程可以看出，这种合并排序的前提是左右两个数列本身是有序的。所以如果对4,2,3,1排序，拆成4,2和3,1两个数列显然是不行的，需要继续拆分4,2为4和2，然后合并为2,4；拆分右侧为3,1，然后合并成1,3。最后合并2,4和1,3。
以4,3,6,2,7,1,5为例，完整的排序过程如下图：
来看代码：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
importjava.util.Arrays;
/
合并排序法
Createdbyautfishon2016/9/20.
/
publicclassMergeSort{
publicstaticvoidmain(String[]args){
int[]numbers=newint[]{4,3,6,2,7,1,5};
System.out.println("排序前:"+Arrays.toString(numbers));
MergeSortms=newMergeSort();
ms.sort(numbers,0,numbers.length-1);
System.out.println("排序后:"+Arrays.toString(numbers));
}
publicvoidsort(int[]numbers,intfrom,intto){
intmiddle=(from+to)/2;
if(from
sort(numbers,from,middle);
sort(numbers,middle+1,to);
//左侧数列最大值小于右侧数列最小值,不需要通过合并来调整顺序
if(numbers[middle]
return;
merge(numbers,from,middle,to);
}
}
privatevoidmerge(int[]numbers,intfrom,intmiddle,intto){
int[]temp=newint[to-from+1];
intleft=from;
intright=middle+1;
inti=0;
//从拆分到两边数列各剩一个数字开始合并;当数列中有多个数字时,一定是已经排好序的
//从两边数列左侧开始依次取数对比,挑选小的一个放入临时数组
while(left<=middle&&right<=to){
if(numbers[left]
temp[i++]=numbers[left++];
}else{
temp[i++]=numbers[right++];
}
}
//把左边数列剩余的数移入数组
while(left<=middle){
temp[i++]=numbers[left++];
}
//把右边数列剩余的数移入数组
while(right<=to){
temp[i++]=numbers[right++];
}
System.arraycopy(temp,0,numbers,from,temp.length);
}
}
运行：
[java]viewplaincopyprint?在CODE上查看代码片派生到我的代码片
排序前:[4,3,6,2,7,1,5]
排序后:[1,2,3,4,5,6,7]
合并排序平均情况和最坏情况的时间复杂度都是O(nlogn)，因为需要额外的辅助空间，空间复杂度为O(n)。
|
|
