文档库

最新最全的文档下载
当前位置:文档库 > java-二叉树实现快速排序-遁地龙卷风

java-二叉树实现快速排序-遁地龙卷风

(-1)写在前面

在一次面试中被问及快速排序,回来后又看了一次以前做过的案例,说来惭愧,时至今日还需要读好长时间,才能明白自己代码的意思,主要是缺少注释和图解,深有感慨,决定好好记录一下。

之所以使用二叉树,是因为用递归实现当数据量过大时会报栈溢出的错误,我试了一下别人的电脑也是这个问题。当然使用二叉树也会报内存不足,原因是无法创建那么长的数组,堆区内存溢出。个人感觉要比递归实现好的多。

(0)算法详解

程序随机产生数据,将其放在数组里。

a.将最小索引到最大索引之间的数据看做一个整体,程序已最小索引代表的数A为准

b.调换A的位置,使得A左边是比A大的数,A右边是比A小的数,此时A的索引被称为中间索引

c.最小索引到中间索引-1被看为左孩子,中间索引+1 到最大索引被看做右孩子

java-二叉树实现快速排序-遁地龙卷风

已此图为例,说明程序流程:

每个节点代表一个数组片段,1是根节点,代表整个数组,每个片段都要经历a、b的操作

顺序为操作1,创建2,3,操作2,创建4,5,操作4,回到2,操作5,回到2,回到1,操作3,创建6,操作6,回到3,回到1,完事。

以下面这个数组为例,说明程序流程

int[] oop = {510, 107,948, 659, 955,438, 283,822};

第一次

a 步骤最小索引0,最大索引7 A –>510

b步骤 [822, 955, 948, 659, 510, 438, 283, 107]

c 步骤左孩子0-3 右孩子5-7

第二次

a 步骤最小索引0,最大索引3 A –>822

b步骤 [948, 955, 822,659]

c 步骤左孩子0-1 右孩子没有

第三次

a 步骤最小索引0,最大索引1 A –>948

b步骤 [955, 948]

c 步骤左孩子没有、右孩子没有

第四次

a 步骤最小索引5,最大索引7 A –>438

b步骤[438, 283, 107]

c 步骤左孩子没有、,右孩子6-7

第五次

a 步骤最小索引6,最大索引7 A –>283

b步骤[283, 107]

c 步骤左孩子没有、右孩子没有

(2)具体实现

class Test

{

public static void main(String[] args)

{

int len = 8000000;

int[] oop = new int[len];

for(int i=0;i

oop[i] = (int)(Math.random()*1000);

Calendar c1 = Calendar.getInstance();

Sort.quick_sort(oop);

Calendar c2 = Calendar.getInstance();

System.out.println(c2.getTimeInMillis()-c1.getTimeInMillis());

}

}

class Binary

{

private int left,//最小索引

right;//最大索引

private Binary beforeBinary,//父节点

rightBinary,//左孩子

leftBinary;//右孩子

public Binary(int left,int right)

{

this.left= left;

this.right = right;

}

public void setLeft(int left)

{

this.left = left;

}

public void setRight(int right)

{

this.right = right;

}

public void setBefore(Binary beforeBinary) {

this.beforeBinary = beforeBinary;

}

public void setRightBinary(Binary rightBinary) {

this.rightBinary = rightBinary;

}

public void setLeftBinary(Binary leftBinary) {

this.leftBinary = leftBinary;

}

public int getLeft()

{

return this.left;

}

public int getRight()

{

return this.right;

}

public Binary getBeforeBinary()

{

return this.beforeBinary;

}

public Binary getRightBinary()

{

return this.rightBinary;

}

public Binary getLeftBinary()

{

return this.leftBinary;

}

}

class Sort

{

public static void quick_sort(int[] oop)

{

Binary headBinary = new Binary(0,oop.length-1),

tempBinary = headBinary;

int right,

left,

tempNumber;

boolean flag = true;

headBinary.setBefore(null);

do

{

left = tempBinary.getLeft();

right = tempBinary.getRight();

tempNumber = oop[left];

while(left

{

while(left=oop[right])//从右边找到比tempNumber大的数

right--;

if(left

{

oop[left] = oop[right];//将右边的数赋值给左边的

left++;//缩减范围

}

while(left

left++;

if(left

{

oop[right] = oop[left];//将左边的数赋值给右边

right--;//缩减范围

}

}

//此时left==right

oop[left] = tempNumber;

if(right

{

Binary c1 = new Binary(right+1,tempBinary.getRight());

tempBinary.setRightBinary(c1);

c1.setBefore(tempBinary);

}

if(left-1>tempBinary.getLeft()) //创建右孩子

{

Binary c1 = new Binary(tempBinary.getLeft(),left-1);

tempBinary.setLeftBinary(c1);

c1.setBefore(tempBinary);

}

flag = true;

do//操作A:(遍历左孩子、右孩子,如果左孩子、右孩子都被遍历,返回上次节点)重复A操作,直到遍历到跟节点

{

if(tempBinary.getLeftBinary() != null)//如果左孩子被创建了,就先遍历左孩子

{

Binary c1 = tempBinary.getLeftBinary();;

tempBinary.setLeftBinary(null);//最为重要,只要被遍历的左孩子就将起在上层节点的引用设为null,

tempBinary = c1;

flag = false;

}

else if(tempBinary.getRightBinary() != null)//右孩子总是左兄弟节点遍历后才被遍历

{

Binary c1 = tempBinary.getRightBinary();

tempBinary.setRightBinary(null);

tempBinary = c1;

flag = false;

}

else //左孩子。右孩子都被遍历返回父节点

{

if(tempBinary == headBinary) break;

tempBinary = tempBinary.getBeforeBinary();

}

}while(flag);

}while(tempBinary != headBinary);//当回溯到根节点时,说明排序完毕

}

}

(3)简单测试

80000000 内存溢出

8000000 66607ms

800000 1027ms