Tenie Blog

//数组转阵型

int array[][] = {

{11,12,13,14,15},

{16,17,18,19,20},

{21,22,23,24,25},

{26,27,28,29,30},

{31,32,33,34,35}

};

for(int k =0;k<4;k++) //转几次

{

int[][] tempArray =new int[5][5]; //存入临时数组

//core

for(int i = 0; i<5;i++){

for(int j =0; j<5;j++){

tempArray[i][j]=array[(4-j)][i] ; //第一行第一个,改为第5行,第一个;

//第一行第2个,改为第4行,第一个;

}

array = tempArray;

}

//algs.jar API

edu.princeton.cs.algs4.In("str") //通过参数String 可以读取本地文件，http；如果不传参读取标准输入流

1.4 算法分析

1.4.3 增长数量级的分类

表1.4.7 对增长数量级的常见假设的总结

----------------------------------------------------------------------------------

描述增长数量级典型代码说明举例

----------------------------------------------------------------------------------

常数级别 1 a = b + c 普通语句将两个数相加

对数级别 logN 二分查找二分策略二分查找

线性级别 N 单循环循环找出最大元素

线性对数级别 NlogN 算法2.4 分治归并排序

平方级别 N²(n的平方) 双层循环双层循环查找所有元素对

立方级别 N³ 三层循环三层循环

指数级别 (2的幕) 第六章讲穷举查找检查所有子集

|指数最接近y

|立方其次 /

|平方再次 /

运 | /

行 | / 线性对数和线性级别在y和x之间45度

| /

时 | /

间 | /

| / 常数最接近x,对数级别靠近常数级别

| ------------------- x

问题规模

1.4.5 设计更快的算法

书中例子找出3个数相加和为零的;3个数有多少对(比较粗糙,使用了3层循环立方级)

3-sum:

public static int count(int[] a)

{

int N = a.length;

int cnt = 0;

for(int i =0;i<N;i++)

for(int j=i+1;j<N;j++)

for(int k=j+1;k<N;k++)

if(a[i]+a[j]+a[k] ==0)

cnt++;

return cnt;

}

1.4.5.1 热身运动2-sum

public static int count(int[] a)

{

Arrays.sort(a); //在开始前先给数组排序

int N = a.length;

int cnt = 0;

for(int i =0;i<N;i++)

if(BinarySearch.rank(-a[i],a) > i ) //取i下标的值取反后,在a数组中二分查询,大于i,为了防止重复

cnt++;

return cnt;

}

1.4.5.2 3-sum 问题的快速算法

public static int count(int[] a)

{

Arrays.sort(a); //数组排序

int N = a.length;

int cnt = 0;

for(int i =0;i<N;i++)

for(int j=i+1;j<N;j++)

if(BinarySearch.rank(-a[i]-a[j],a)> j) //道理一样,前面2个数相加后取反,能在数组中二分查找找到,说明有3-sum; 之所以快因为少了一层循环

cnt++;

return cnt;

}

1.4.6 倍率实验

就是对计算规模加倍测试;如第一输入100,获取计算时间, 第二次输入量加倍如200,获取计算时间,有了2个时间后就能计算倍率, 第一个时间为分母第二时间为分子,计算倍率值;

依次类推等倍率值会规定一个值后, 通过该值就能计算更大规模的计算大概需要的时间了, 而不一定真的直接去计算大规模的运算

在有性能压力的情况下,应该考虑对编写过的所有程序进行倍率实验----这是一种估计运行时间的增长数量级的简单方法.

例子:

main()

{

double prev = timeTrial(125); //该方法运行程序,结束会返回运行时间(秒);刚开始的运行规模

//程序运行规模加倍(循环加倍运算)

for(int n=250; true; n+=n) //这里n的运算系数是2, 就是每次计算量是前一次量乘2

{

double time = timeTrial(n); //加倍运算

StdOut.printf("计算量:%d ; 运行时间:%f ; 倍率:%f \n",n,time,time/prev); //输出运算结果

prev = time;

}

评估程序解决大型问题的可行性

计算更大规模的运算, 只要把循环中运算系数2,增大,比如10

评估使用更快的计算机所产生的价值

相同运算规模,如果用一台更快的计算机能够加快多少?

一般来说新计算机比老计算机快x倍,远行时间也将为原来的x分之一. (如快了2倍,一样的运行时间为time/2)

1.5 案例研究:union-find算法 <union 联合>

1.5.1 动态连通性

下面都是围栏这个话题展开的,例子是:输入2个对象, 如果他们之间没有连接, 就建立连接;2个对象,分别可以和其他对象连接,

此时,如果这些对象中2个对象并没有直接连接, 对象想连接, 可以通过以连接的对象来路由, 不要自己直接建立连接!

图1.5.2

案例中

一个p对象称为:触电, q对象和p相等(对称的) 称为:连接, 把其他的和p或q相等的(对称的对象)称为:连通分量(or分量,也就是有多少个独立的连接)

案例的目录是找到有多少个连接网络(连通分量);从图片中用肉眼很容易找到这些连通分量, 但是在一堆数据中找到这些连通分量是困难的.

表1.5.1 union-find算法的API

-----------------------------------------------------

public class UF

----------------------------------------------------

UF(int N) 以整数标识(0到N-1)初始化N个触点

void union(int p, int q) 在p和q之间添加一条连接

int find(int p) p所在的分量的标识符(0到N-1)

boolean connected(int p ,int q) 如果p和q存在于同一个分量中则返回true.//就是说它们在一个连接网中就返回true

int count() 连通分量的数量 //有多少个连接网络

--------------------------------------------------------

成员变量

private int[] id; //分量id(以触点作为索引)

private int count; //分量数量

说明:

该类初始化时,初始化一个有多少个触点(对象)的数组

然后接受p和q 触电对! 如果他们不在一个连接分量中, 就在他们之间建立连接;

//第一次输出,肯定是没有连接的,给他们建立连接,

//之后他们,又可以和其他触电建立连接,(在建立连接的时候要判断,新的触点是不是在一个连通分量中,在一个连通分量中就不用连接了)

UF算法目的: 计算N个触电之间最后建立了多少个连接分量, 建立了多少条连接

//测试代码

main()

{

int N = StdIn.readInt(); //获取触电的数量

UF uf = new UF(N); //初始化N个分量

while(!StdIn.isEmpty() //循环获取输入

{

int p = StdIn.readInt();

int p = StdIn.readInt(); //读取整数对

if(uf.connected(p,q)) continue; //判断它们是不是在一个分量中,在的话忽略

uf.union(p,q); //归并分量(给p,q 建立连接)

StdOut.println(p +" "+ q); //打印连接;打印出p,q 说明它们之间建立的连接

}

StdOut.println(uf.count()+ "components"); //程序最后打印有多少个连通分量

}

1.5.2.1 quick-find 算法

//p所在的分量的标识符

public int find(int p)

{

//quick-find 算法

return id[p];

}

//给2个触点建立连接, 也就是把2个分量连接(等于是把2个连通分量建立连接,一个触点后面有多个连通的触点,等于把所有的触点都连通了)

public void union(int p,int q)

{

//quick-find 算法 ;

int pID = find(p); //找到p,q对应id[]数组下标中的值, 下面对值比较,相等说明是一个分量,不相等,不是同分量,建立连接(建立连接就是把p,q的给赋值层相等的(包括分量中所有的触点))

int qID = find(q);

//如果p和q已经在相同的分量中则不需要建立连接

if(pID == qID) return;

//下面是建立连接的思路, 就是把p,q 上的值赋值成相等的

for(int i =0 ; i < id.length; i++) //总结:

{ // 建立的id[]里面的值是相对于的触点的p,q的值, 如:id[0] -> 0 ; id[1]

if(id[i] == pID) //分量连接(触点连接),建立连接就是把数组中值和p相等的值全都改为q的值,

{ //连通分量中的值都是一样的!

id[i] = qID; //p,q要不要建立连接就是比较2个p,q下标对应的值是不是相等,不相等,建立连接(这里的做法是吧所有p下标下的"P值",在数组中所有"p值", 都赋值成"q值")

} //把"p值"赋值层"q值",和把"q值"赋值成"p值也可以";计算量是一样的

} //最后把连通分量的数量减1,

count --;

}

quick-find算法分析:

find()操作很快, 只要访问一次数组; 但union()方法每次建立连接都要扫描整个数组,给分量赋值的次数又是在1~(N-1)此的操作, 如果数组很大,会比较慢

如果使用quick-find算法来解决动态连通性问题并最后只得到一个连通分量的话,就需要N-1次的union(),即至少(N+3)(N-1)~N的二次方次的数组访问(这个访问次数是find()2次,循环数组N次,赋值时再一次)

1.5.2.3 quick-union 算法

该算法思路:合并两个连通分量的时候, 刚开始的时候,把p作为q的父节点(反之也一样); 后面是根节点直接的操作

union()方法的逻辑变的简单了, 操作也少了,只要该一个值就行了,但在判断p,q是不是在一个分量中需要使用的find()操作就多了,

find()通过传入的值,找到对象的父节点,直到根节点, 如果当前的值是一个值没有父节点,也就没有根, 自己就是一个分量

union()在合并两个分量的时候,首先使用find()找到p,q的根节点, 如果他们的根节点不同, 就不把q根节点作为p的根节点的一个子节点;这样2个分量有了一个根节点,表示他们在同一个分量中

代码:

//找到根

private int find()

{

while(p != id[p]) p = id[p]; //如果[p]下标中的值和 p的值不等;就把下标中的值取出来,把取出的值赋值给p, 继续获取新p值[下标]下的值

return p

}

//合并分量 ;合并根

public void union(int p,int q)

{

int pRoot = find(p);

int qRoot = find(q);

if(pRoot == qRoot) return;

id[pRoot] = qRoot; //把q根(下标),赋值成p下标下的值

count --;

}

总结:

把分量的父节点存入分量下标的值里

find() 根据这个值找到他的父(根)节点的下标;如下标的值和元素值相等就是根,初始时每个触点都是根

union() 操作就简单了,合并就是把2个分量的根节点,1个变成了另一个的子节点

1.5.2.7 加权quick-union-find算法分析

该算法在前一个算法上做了一个小改动, 在合并2个分量时,判断哪个分量的树更小, 把小的合个大的,

好处就是最终的树层次不会很深, 减少了find()方法的循环次数. 复杂度仅仅加了一个数组来记录分量上有多少个触点

class WeightedQuickUnionUF{

private int[] id;

private int[] sz; //记录对应根节点下有多少个分量

private int count;

//构造

public UF_weightedQuickUnion(int N){

count = N;

id = new int[N];

for(int i = 0; i < N; i++)

id[i] = i;

//初始化记录数量的数组, 初始时, 每个触点就是一个分量,

sz = new int[N];

for(int i = 0; i < N; i++)

sz[i] = 1; // 赋值为1;

}

//查找根节点

public int find(int p)

{

while( p != id[p]) p = id[p]; //如果p 的值和数组下标[p]的值不同 ,就把该下标的值赋值给p, 然后接着用p做为下标取值和p值比较

return p;

}

//合并分量

public void union(int p,int q)

{

int pRoot = find(p);

int qRoot = find(q);

if(pRoot == qRoot) return; //

//加权qunick-union;重点在合并的时候,判断哪个树小, 小的合并给大树; 然后记录大树下有多少分量在sz数组中

if(sz[pRoot] > sz[qRoot]){

id[qRoot] = pRoot;

sz[pRoot] += sz[qRoot] ; //把原本2颗树的分量数相加后,就是合并树下有多少个分量

}else{

id[pRoot] = qRoot;

sz[qRoot] += sz[pRoot] ;

}

count --;

}

总结:

weighted-quick-union 算法通过小树合并给大树, 降低了树的深度,减少了find()方法访问数组的次数;让程序已经很快了!

还有一种完全扁平化子节点的方式;(所有子节点都只有一个父节点)代码如下

public int find(int p) {

int root = p;

while (root != id[root])

root = id[root]; //获取根节点

//把一个树上的所有子节点都直接连到根节点上

while (p != root) {

int newp = id[p];

id[p] = root;//将触点连接到根节点 ,(把深层次的触点连接到根节点)

p = newp;

}

return root;

}

进find()后, 所有的子节点都挂载到根节点了。

还有一种路径减半的

public int find(int p) {

while (p != id[p]) { //树的深度减半的方式

id[p] = id[id[p]]; // path compression by halving

p = id[p];

}

return p;

}

在weighted-quick-union算法中 ,用路径压缩这些, 没什么效果

在quick-union算法中, 用路径压缩后, 和weighted-quick-union的效率相似了

第二章排序

排序要用到的比较方法less(v,w),v小于等于w返回true;代码如下:

protected boolean less(Comparable v, Comparable w){

return v.compareTo(w)<0; //compareTo()返回0 相等,1 大于,-1小于

}

2.1.2 选择排序

逻辑最简单的排序

首先在内循环中找到最小的元素, 找到后在外循环中把最小元素和第一个元素交换位置, 外循环进入下次循环找剩下的元素中最小给给第二个元素交换位置;

它的效率最低下,因为内循环每次都要和剩余的元素做比较找最小元素, 哪怕他已经是最小的元素了.代码如下:

public void sort(Comparable[] a){

System.out.println("selection");

int N = a.length;

for(int i =0 ; i <N; i++){

//将a[i] 和a[i+1..N] 中最小的元素交换

int min = i;

for(int j = i +1;j<N; j++){ //初始时,但第一个值为min, min 后后面的元素对比, 谁小把谁赋值给min,然后接着往后比较,

if(less(a[j],a[min])){ //比较方法

min = j;

}

exch(a,i,min); //交换方法

}

2.1.3 插入排序

该算法可抽象的认为打牌是整理牌的时候, 每拿一张牌就把该张牌插入到目前有序的牌中适当位置.

在计算机的实现中, 为了给要插入的元素腾出空间,我们需要将其余所有元素在插入之前都向右移动一位.

和选择排序比较

类似的是,

排到一定程度,前面的元素的是有序的,但却是不固定,选择排序前面的选项一定是固定的.

不同的是,

选择排序刚开始会遍历所有元素,

插入排序不是偏离元素是移动元素,在极端情况下如果最后一个元素是最小的, 那么整个数组都要移动N-1次

选择排序的排序时间是固定的,

而插入排序如果其中的元素是相对有序的话, 元素的移动量会很少,时间是不固定的,最坏情况下,2个算法时间是接近的

代码如下:

public void sort(Comparable[] a){

int N = a.length;

for(int i = 1; i<N; i++)

{ //将a[i] 插入到 a[i-1],a[i-2],a[i-3]...之中

for(int j = i; j>0 && less(a[j],a[j-1]); j--){ //如循环到中间; 当前元素和前面的元素做比较,如果小了,就交换,

//因为前面的元素都是有有序的,如果第一次比较失败,那么就直接进入外层循环,移动到下一个元素,开始和前面的元素比较

exch(a,j,j-1);

}

优化版;

//插入排序的优化;在内循环中没有使用到exch()方法,exch()方法每次交换都要利用到一个临时变量缓存才能做交换,

//该优化版中自己做了一次缓存,主要就是缓存的次数少了,就一次, 速度就快在这个上面

public void sort(Comparable[] a){

int N = a.length;

for(int i=1;i<N; i++){

Comparable t = a[i];

int j = i;

while( (j>0) && (a[j-1].compareTo(t))>0 ){

a[j] = a[j-1];

--j;

}

a[j] = t;

}

2.1.6 希尔排序

希尔排序的思想是, 使数组中任意间隔数为h 的元素间都是有序的, 这样的数组被称为h有序数组;

换言之: h有序的数组相对于整个原数组,h数组就是,元素中的元素于元素之间间隔h个元素

代码:

public void sort(Comparable[] a){

int N = a.length;

int h = 1;

while(h<N/3) h = 3*h + 1; //计算该数组可以产生的最大h值 (比较远"的一个元素)

while(h>=1)

{//将数组变为h有序

for(int i = h; i<N; i++)//把i初始为h的值

{//将a[i] 插入到a[i-h],a[i-2*h],a[i-3*h] ...之中

for(int j=i; j>=h && less(a[j],a[j-h]); j-=h)

{

exch(a,j,j-h);

}

h = h/3;

}

* 代码解释

*从第一个元素和 "比较远"的一个元素对比-> 交换 ; //初始时:其实分为2个数组; 对数组各种相同下标的元素比较, 如果前面的元素和后面的比小的话,互换

*初始的时候,是用一个公式算出一个h值,作为"比较远"的元素

*(可是认为,h值是间隔原数组元素之间的距离的);

*初始时比较的是2个元素的各自第一个;通过比较就交换, // [h] 比较 [0]? //0是用i变量替换的;

*然后进入下次循环 h+1 ; [h+1]的元素和 [1] //[h++] 比较 [1]? //这里可以写出[h+1] 比较[i++]

*等h和的值++ 到N 后 ;第一次循环结束, 但此时h值之前的很多元素都还没比较到呢;

*第二次循环前 h值再次/3 得到一个新的h值;

*此时刚开始和第一次循环类似,2个元素相同下标的值对比交换

*但是h值变的小了, 以h值来对原数组来说可以分好几个h间隔的子数组了,(也就是初始时,中间的元素没比较到,因为间隔的减少,中间的开始比较到了)

*比较的方式是: 第一个数组和第二个数组,对应下标比较, 完了后, 第2个数组和第3个数组对应下标值的比较;此时第2个数组有和第一个数组对于的值比较

*也就是说; 比到第3个数组时,第3个数组和第2个数组比较一次后, 第2个数组和第一个数组对于下标也会比较一次.

总之: 间隔系数h的值是 while(h<N/3) h = 3*h + 1; 计算而来, 一般应用已经够用,不需要去研究这个系数值来提升性能了

希尔排序, 因为是原地排序,不需要额外空间,对于中等数组它色速度是可以接受的, 如希尔排序不满足了, 才去考虑在去换更复杂的排序

2.2 归并排序

归并的发明:

在把2个已经有序的数组,合并成一个有序的大数组的时候,很快人们根据这个操作发明了一个简单的递归排序算法:归并排序.

开始对一个数组排序的时候;

首先,将他们分成两半分别排序(递归进行);

然后,将结果归并起来.(2个有序的数组,每次取各自的元素出来比较, 大的或小的元素放入临时数组中,接着取一个元素,和但那个小(大)的比较)

归并的优点是,排序的时间是非常稳定的, 任意长度N的数组,所需要的时间和NlogN成正比; 缺点就是需要额外空间和N成正比

代码如下:

归并2个数组成一个数组的方法(归并排序的核心)

/**

*归并排序; 把一个原数组,分2成2个, 遍历

* @param a 原数组

* @param lo 起始位置

* @param mid 数组的中间位置

* @param hi 数组最后的位置

public void merge(Comparable[] a, int lo, int mid, int hi)

{//将a[lo..mid] 和啊[mid+1 .. hi] 归并

int i = lo , j = mid+1;

for(int k = lo; k <= hi ; k++){ //将啊[lo..hi] 复制给aux

aux[k] = a[k];

}

for(int k = lo; k <= hi ; k++){ //归并回到a[lo .. hi]

if (i > mid) a[k] = aux[j++];//i 大于 mid 说明前半个数组没有值了

else if(j > hi) a[k] = aux[i++];

else if(less(aux[j],aux[i])) a[k] = aux[j++];//初始时,会进入这里,2个子数组每个元素对比后加入原数组

else a[k] = aux[i++];

}

sort()方法就相对简单了,如下:

private void sort(Comparable[] a ,int lo, int hi)

{//将数组a[lo..hi]排序

if(hi <= lo) return ;

int mid = lo+(hi-lo)/2;

sort(a,lo,mid); //把原数组分割后,递归的对他们排序

sort(a,mid+1,hi);

merge(a,lo,mid,hi); //经过递归后, 原数组前半部分的数组和后半部分的数组已经有序了, 将他们合并

}

归并排序的优化

1.在递归的sort()中拆分数组归并, 最终会把数组拆分成到一个数组一个元素为止, 显然数组到了这样的细颗粒度的拆分是没有效率可言的.

此时在子数组在小于15时使用插入排序(或选择排序)来对子数组排序,显然比递归的拆分下去效率要高(因为这类简单的排序作用在小数组上速度比归本更快)

思路就是在归并排序时检测下子数组的长度(如小于15),就不用归并了,直接调用插入对子数组排序; 一般而言此时的远行时间缩短10%~15%

自己实现了下,发现没有提升代码如下:

private void sort(Comparable[] a ,int lo, int hi){

//小数组用插入排序;

if(hi<lo+LENGTH){

int k = lo;

//System.out.println(a.length);

Comparable arr[] = new Comparable[hi-lo+1];

for(int i = 0 ;i < arr.length; i++){

arr[i] = a[k];

k++;

}

new Instertion().sort(arr);

int j = 0;

for(int i = lo ;i <=hi; i++){

a[i] = arr[j];

j++;

}

return;

}

//将数组a[lo..hi]排序

if(hi <= lo) return ;

int mid = lo+(hi-lo)/2;

sort(a,lo,mid); //把原数组分割后,递归的对他们排序

sort(a,mid+1,hi);

if(a[mid].compareTo(a[mid+1])>0)

merge(a,lo,mid,hi); //经过递归后, 原数组前半部分的数组和后半部分的数组已经有序了, 将他们合并

}

2.还可以加一个判断条件来优化, 如果a[mid] 小于a[aid+1],就认为该数组已经是有序的就跳过merge()方法,不影响sort()方法的递归调用,但是任意

有序的子数组算法的运行时间就变成线性的了;性能的提升只有在数组非常庞大时才有点效果, 因为该判断只有在数组中只有2个元素的子元素是才会有优化;代码如下:

private void sort(Comparable[] a ,int lo, int hi)

{//将数组a[lo..hi]排序

if(hi <= lo) return ;

int mid = lo+(hi-lo)/2;

sort(a,lo,mid); //把原数组分割后,递归的对他们排序

sort(a,mid+1,hi);

if(a[mid].compareTo(a[mid+1])>0)

merge(a,lo,mid,hi); //经过递归后, 原数组前半部分的数组和后半部分的数组已经有序了, 将他们合并

}

2.2.3 自底向上的归并排序

从小数组(一个元素的数组)开始归并;先22归并,在44,在88, 循环到x N-1;

最后一次的归并的时候第2个数组可能比第1个数组要小,实现在MergeBU

效率没有递归的从上往下拆分来的快, 代码如下:

public void sort(Comparable[] a)

{//进行lgN次两两归并

int N = a.length;

aux = new Comparable[N];

for(int sz = 1; sz < N; sz = sz+sz){

for(int lo = 0; lo < N-sz ;lo +=sz+sz){

merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1, N-1));

}

不过自底向上的归并可以使用链表来实现,这样就不需要临时数组了,只需要把链表连接改变下即可

2.3 快速排序

属于原地排序的算法,不像归并算法需要额外的空间, 归并还是比快排快一点,快排优点就是不需要额外空间的排序算法中,速度是最快的

思路:

1. 打乱数组中元素的顺序(为了防止出现极端情况)

2. 使用数组第一个元素作为分割元素,循环的从数组2端查找小于分割元素和大于分割元素的元素;

3. 从第二个元素开始往后扫描,找到比分割元素大的(包括等于的)元素(a),

3-1. 从数组末尾开始向前扫描,找到比分割元素小的(包括等于的)元素(b),

3-2. 交换a,b的位置,

3-3. 如果a>=b,那么不用交换a,b的位置了, 分割元素直接和b元素交换,此时的分割元素的前面的元素都比其小,后面的比其大

4. 返回分割元素当前的位置, 递归的对其分割的前后数组排序

代码:

//排序算法

private void sort(Comparable[] a,int lo,int hi){

if(hi <= lo) return;

int j = partition(a,lo,hi);

sort(a,lo,j-1); //将左半部分排序a[lo .. j-1]

sort(a,j+1,hi); //将右半部分排序a[j+1 .. hi]

}

//分割数组的方法,返回分割元素的下标

private static int partition(Comparable[] a,int lo,int hi)

{//将数组切分为a[lo..i-1], a[i+1..hi]

int i = lo;

int j = hi+1;

Comparable v = a[lo]; //切分元素,初始是在数组的第一个元素的位置, 但和前后元素比较后, 得到2个子数组后,返回该切分元素的位置

while(true)

{ //扫描左右, 检查扫描是否结束并交换元素

while(less(a[++i],v)) //从第二个元素开始,找大于(包括相等)分割元素的元素下标 i值,找到退出循环

if(i == hi)break; //越界判断

while(less(v,a[--j])) //从最后一个元素开始, 找小于(等于)分割元素的下标j值, 找到退出循环

if(j == lo)break; //越界判断

if(i >= j)break; //如果大于v的元素下标>= 小于v元素的下标, 就退出大循环; 在大循环外面直接把v和j交换

exch(a,i,j);

}

exch(a,lo,j); //v 和当前j的位置对换,经过内循环,已经知道了, j的值小于v的值

return j; //返回 j这个下标值

}

快排的性能改进

1. 在递归过程中,子数组变成较小是如5~15的长度是;可以切换为插入排序;在sort()方法中加判断如下:

原来的判断:

if(hi<=lo) return; 如果第一个元素就是最后一个元素,就结束排序

改成如下:

if(hi<=lo+M){Insertion.sort(a,lo,hi);return;}//M为要改为插入排序时,子数组的长度

2. 三取样切分

3. 熵最优的排序

在有大量重复元素的数组中,使用该算法能提高效率,比归并排序还能快一点,归并的时间则是固定的.

但是重复的元素要足够多.

思路:

本来数组分为前后2部分,前部分比切分元素小,后面的比切分大,现在分为3部分,增加中间部分,和分割元素一样大的.

原本的实现是那分割元素从前半部分找大于它的元素,后半部分找小于它的元素, 然后交换找到的元素,直到半部分的扫描指针大于等于后半部的扫描指针;

然后把切分元素插入到后半部分扫描的指针的位置;

三向切分: 记录一个后半部分的指针, 前半部分的指针, 2个指针之间的等于切分元素

步骤:

1.第一个元素为切分元素(v),小于切分元素的指针也在第一个元素上(lt)

1.1 比切分元素大的指针在最后一个元素上gt,

1.2 要进行比较的元素(i),初始时在第2个元素上;

2. 切分元素(v) 和比较元素(i) 做比较;

2.1 如果i < v ; 那么小于切分元素的指针lt和i 交换位置; (初始状态的话就是切分元素和第2个元素交换位置,如果不是初始状态,就另外一回事了)

然后lt++; i++;(i++很好理解,比较元素指针移到下一个元素,lt++也不男理解,lt指针前的元素比切分元素小)

2.2 如果i > v ; 那么大于切分元素的指针gt和i 交换位置;(初始状态的话就是把第2个元素和最后一个元素换位置)

然后gt--;(gt指针后面的元素比v小)//才是进入下一次循环(步骤2),比较元素i的值是之前在最后的那个元素

2.3 如果i = v ; 那么不用交换,(初始时是这样的话,第2个元素和v 相等;)

i++(比较元素的位置加1,就是下次循环时用这个元素了);

c,b,d,c,b,a //v=c ; lt = [0]; gt = [5] ; i = [1];

第一次:i[1]<v; b,c,d,c,b,a lt = [1]; gt = [5] ; i = [2]; //[0][1]交换 gt和i交换后lt++ ; i++

第二次:i[2]>v; b,c,a,c,b,d lt = [1]; gt = [4] ; i = [2]; //[2][5]交换 i>v 后,gt和i交换; g--

第三次:i[2]<v; b,a,c,c,b,d lt = [2]; gt = [4] ; i = [3]; //[1][2]交换 i<v 后,gt和i交换; lt++ ; i++

第四次:i[3]=v; b,a,c,c,b,d lt = [2]; gt = [4] ; i = [4]; //不交换, i=v 后,不做交换,比较元素i指针++

第五次:i[4]<v; b,a,b,c,c,d // lt = [3]; gt = [4] ; i = [5]; //[2][4],此时 i++ 后大于gt; 退出循环(步骤2,进入步骤3)

3.此时递归的对小于和大于v的前后2个子数组进行排序

总结:

该三向切分对大量重复的数组有效, 因为其重复的元素多的话, 前后2个子数组会比较短小了

2.4 优先队列

与队列(先进先出),栈(后进先出),一样是一种数据类型;它实现了最大(小)的值先出队列的一种数据结构;

就是当前队列中的值是有序的,插入新值,会插入到他的对应位置;比如插入的值是所有当前元素的最大值,那么它会在队列的最前面,如果是做小值,那么会在所有元素的最后面

下面会实现2中最大值的优先队列MaxPQ和MinPQ;按最大值排序和按最小子排序.

定义MaxPQ的API:(MinPQ类似)

构造器3个;默认;制定队列大小, 把一个数组转换为队列

其他方法:

Insert(key v) 向优先队列插入一个元素

max() 返回最大元素

delMax() 删除并返回最大元素

isEmpty() 返回队列是否为空

size() 返回优先队列中的元素个数

下面使用MinPQ实现了一个TopM的应用,用来对大量输入的应用统计大量输入排名前M名,如前10名的一个队列;

该TopM也是比较灵活的,因为当遇到大量的输出时,不可能对大量的输入数据做缓存后,再进行排序,再获取前M名的元素, 这在空间和时间上都是浪费,因为只需要M个值(如10个值),确要缓存整个数据和对整个数据排序

TopM的实现

class TopM

{

main(String[] args)

{

int M = Integer.parseInt(args[0]);

MinPQ<Transcation> pq = new MinPQ<Transcation>(M+1);//构造一个指定长度的优先队列(M+1,多预留了一个位置)

while(StdIn.hasNextLine()){ //循环获取输入

pq.insert(new Transcaion(StdIn.readLine())); //把获取的输入插入队列

if(pq.size()>M ); //判断队列的长度是不是大于M;大于M了就删除其中最小的值,便于下一个输入的值能插入

pd.delMin();

}

Stack<Transaction> stack = new Stack<Transaction>();//构建一个栈,

while(!pq.isEmpty()){ //从优先队列中输出一个最小的元素,加入栈, 这样从栈中取元素的时候是按从小到大的顺序

stack.push(pq.delMin());

}

for(Transaction t : stack){ //遍历栈,

StdOut.println(t); //顺序打印,刚输入的元素中前M名的最大元素

}

2.4.2 初级实现

1. 数组实现(无序)

就是把元素先放入数组中, 等到要删除最大元素时,再对数组进行选择排序的内循环找到最大元素,让把最大元素和边界元素交换,然后删除掉

2. 数组实现(有序)

该方法是在insert()方法中每次插入元素时对数组进行操作,将所有较大的元素向右移动一格以使数组保持有序,然后插入元素(和插入排序一样),

这样,最大的元素总会在数组的一边

总结, 使用链表也能实现上面的这些初级实现, 无序的实现方式属于惰性方法,在删除最大元素时才去查找, 有序的实现属于积极的方法,插入的时候就已经准备好了当前的最大元素, 删除时只有直接取就行了

他们的效率都非常低,现在要介绍另一种数据结构堆

2.4.3 堆的定义(二叉堆,简称为堆)

数据结构二叉堆(一个父节点可以有2个子节点);在二叉堆的数组中,每个元素都要保证等于等于另外两个特定位置的元素,也就是父(根)节点,必须大于等于它的2个子节点.

定义: 但一颗二叉树的每个结点都大于等于它的两个子结点时, 它被称为堆有序. 根结点是堆有序的二叉树中最大的结点!

二叉堆表示法

如果用指针来表示二叉树的话, 每个结点需要2个指针, 一个指向父结点,2个指向子节点.这样好像满复杂的.如果使用完全二叉树,表达就会变得特别方便,

可以先定下根节点, 然后一层一层地由上向下,从左至右,在每个结点的下方连接2个更小的节点,直到将N个结点全部连接完毕,完全二叉树只需要数组而不需要指针就可以表示.

具体方法是按照层次顺序放入数组中,根结点的位置为[1], 它的子结点的位置[2]和[3],而子结点的子结点则分别在位置[4],[5],[6],[7],以此类推.

定义: 二叉树是一组能够用堆有序的完全二叉树排序的元素, 并在数组中按照层级存储(不使用数组的第一个位置[0],位置技术更方便).

在数组表示的堆中,位置k的结点的父结点的位置为看k/2,而它的两个子结点的位置则分别为2k和2k+1 ,这样不使用指针,我们可以根据这个公式在树中上下移动.找父结点和子结点都很快和方便

2.4.4 堆的算法

上面说了使用数组来构建这个二叉堆, 使用一个长度为N+1 的私有数组pq[]来表示一个大小为N堆,因为数组的[0]下标不使用,为了便于计算,堆的元素在数组的pq[1]~pq[N]之间

在加入新元素或者删除最大(小)元素时,需要对堆进行有序化;

有序化2种情况,如下:

1. 在堆低加入一个新元素时, 需要由下至上恢复堆的顺序,(上浮)

2. 当根结点替换为一个较小的元素(根节点被取走), 需要由下至上恢复推的顺序(下沉)

2种操作下面学习

2.4.4.1 由下至上的堆有序化(上浮)

新元素加入到堆,在堆的底部加入新元素后, 新元素可能比它的父结点大,此时堆的有序性被打破,需要进行有序化,

由下至上的堆有序化,可以称为上浮,就是把新元素(K)和父节点(K/2)比较,如果比他的父节点大,那么把父节点和新元素互换位置

上浮的方法取名swim(),代码如下:

private void swim(int k){

while(k > 1 && less(k/2,k)){ //判断:1. k的下标大于根的下标(已经是根也不比去上浮了),2.k/2(父) 小于 K 的话进入循环

exch(k/2,k); // 子结点比父结点的判断成,交换2个的位置,K成为父节点

k = k/2; //获取K当前的位置(原来父结点的位置)

}

2.4.4.2 由上至下的堆有序化(下沉)

当最大(小)元素(根元素)被取走后, 最合适的方式是从堆的末尾(数组末尾)的元素放在根元素原来的位置上,

这样一来,堆顺序被打破, 使用下沉的方式将该元素(临时根元素),和它2个结点([2k], [2k+1]),进行比较如果子结点比他大那么就交换位置,

然后循环这个操作,直到它比它的子结点大,或到达底部位置

下沉的方法为sink(),代码如下:

private void sink(int k){

while(2*k <= N){ // 获取K的子结点,如果有的话,进入循环

int j = 2*k; //获取子节点的下标

if(j < N && less(j,j+1) ) j++; //判断是不是有2个子节点和 2个子结点比较谁大,下面用大的子节点和k比较

if(!less(k,j)) break; //如果k 比j 大, 那么结束下沉,k的位置是正确的,

exch(k,j); //否则, k 和 j 交换位置,

k = j; //获取k当前的下标值;进入下一次循环

}

基于堆的优先队列代码如下:

public class MaxPQ<Key extends Comparable<Key>>

{

private Key[] pq; //基于堆的完全二叉树

private int N = 0; //存储于pq[1~N] 中, pq[0] 不使用

//构造器

public MaxPQ(int MaxN){ pq = (Key[])new Comparable[MaxN+1]; }

/** 插入*/

public void insert(Key v){

pq[++N] = v;

swim(N);

}

/**删除最大的元素(根),并返回 */

public Key delMax(){

Key max = pq[1];

exch(1,N--);

pq[N+1] = null; //把数组最后一个位置的引用赋予null

sink(1);

return max;

}

//辅助方法

public boolean isEmpty(){return N == 0; }

public int size(){return N; }

private boolean less(int i,int j){ return pq[i].compareTo(pq[j]) < 0;} //比较方法

private void exch(int i,int j){ Key temp = pq[i]; pq[i] = pq[j]; pq[j] = temp;} //交换方法

private void swim(int k){..} //上浮

private void sink(int k){..} //下沉

}

总结:

基于堆的完全二叉树表示的优先队列,存储于数组pq[1~N]中,

insert()时N加1,把新元素加入到数组最后,让后用swim() 恢复堆的秩序

delMax()时,从pq[1]中得到需要的返回元素,然后把pq[N]移动到pq[1],N减1,使用sink()恢复堆的秩序.还要把pq中最后一个位置的值赋null

该实现类省略了动态调整数组大小的代码.

2.4.4.3 多叉堆

基于完全二叉树构建的堆的思路也可以构建完全三叉树的堆, 位置k的结点的3个子结点在[3k-1],[3k],[3k+1],父结点在[(k+1)/3],

根据这个思路,不管要实现d叉的树都可以实现,要权衡的是增加树高还是增加树叉,那个性能根优而已.其实是一样的性能

2.4.4.4 调整数组大小

可以添加一个没有参数的构造函数, 在insert()中添加将数组长度加倍的代码,在delMax()中添加将数组长度减半的代码,(类似前面栈的实现那样).

这样使用这个优先队列的时候, 使用者就不用关注队列大小的限制了

2.4.4.5 元素的不可变性

优先队列存储的对象,应该是不可变的,要是一个对象的引用在其他地方的代码中被改变了,那就乱套了!使用优先队列要自觉!

喜欢