探讨一下快速排序:
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序动态图:
使用快速排序法对一列数字进行排序的过程 |
分类
排序算法 |
数据结构
Varies |
最差时间复杂度
Θ(n2) |
最优时间复杂度
Θ(nlogn) |
平均时间复杂度
Θ(nlogn) comparisons |
最差空间复杂度
根据实现的方式不同而不同 |
最佳算法
有时是 |
首先构造了基本的数据结果如下,这两个算作工具吧,一个是用于标记尚未排序区间的Pointer,另一个是基本栈结构。
/* 栈元素,用于记录尚未排序的区间*/
class Pointer
{
int start,end;
public Pointer(int x,int y)
{
this.start = x;
this.end = y;
}
}
/* 栈,用于存放Pointer的静态数组,不可动态自增维度*/
class Stack
{
private final static int MAX =20;
private static Pointer [] container;
static int place = -1;
public Stack()
{
container = new Pointer[MAX];
}
public void Push(Pointer element)
{
if(place>=-1 && place<MAX-1)
container[++place] = element;
}
public boolean isEmpty()
{
if(place ==-1)
return true;
else
return false;
}
public Pointer Pop()
{
if(place == -1 || place>=20)
return null;
else
{
return container[place --];
}
}
}
算法如下:
public class QuickSort
{
public static void main(String [] arg)
{
int [] src ={83 ,19 ,3 ,62 ,27 ,56 ,9 ,24 ,60 ,88 };
//BubbleSort.createRandom(10, 0, 100);
stack = new Stack();
stack.Push(new Pointer(0,src.length -1));
while(!stack.isEmpty())
{//递归开始
Pointer p = (Pointer)stack.Pop();
int index = sortOnce(src,p.start,p.end);
if(index - p.start >=1)
stack.Push(new Pointer(p.start,index-1));
if(p.end - index-1 >=1)
stack.Push(new Pointer(index+1,p.end));
}
System.out.println("\nend:");
for(int elements : src)
{
System.out.print(elements+" ");
}
System.out.println("");
}
static Stack stack ;
public static int sortOnce(int [] quene, int start , int end)
{
//当quene是整个的时候,start = 0 , end = quene.length -1
int pivot;//基准
pivot = quene[start];
int i = start,j=end;
while(i<j)
{
while(quene[j] > pivot && i<j)
j--;
if(i<j)
quene[i++] = quene[j];
while(quene[i] < pivot && i<j)
i++;
if(i<j)
quene[j--] = quene[i];
}
quene[i] = pivot;
for( int element:quene)
{
System.out.print(element+ " ");
}
System.out.println(" index="+i);
return i;
}
}
结果:
60 19 3 62 27 56 9 24 83 88 index=8
24 19 3 9 27 56 60 62 83 88 index=6
9 19 3 24 27 56 60 62 83 88 index=3
9 19 3 24 27 56 60 62 83 88 index=4
3 9 19 24 27 56 60 62 83 88 index=1
3 9 19 24 27 56 60 62 83 88 index=0
end:
3 9 19 24 27 56 60 62 83 88
分享到:
相关推荐
快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表) 插補搜尋法 費氏搜尋法 矩陣 稀疏矩陣 多維矩陣轉一維矩陣 上三角、下三角、...
Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实不多,因此这个Java文件传输实例不可错过,Java网络编程技能的提升很有帮助。 Java聊天程序,包括服务端和...
八大排序java实现源代码,有非常完整的注释,非常适合初学者。...八大排序:冒泡排序、插入排序、选择排序、归并排序、堆排序、快速排序、希尔排序和基数排序。真的是非常完整的资料。工程直接导入eclipse即可。
Java 源码包 Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来...
无水印! !!!!原创这是基于gif动画实现的快速排序无水印的动画演示,无需任何积分,欢迎大家下载使用!好的东西就是要共享
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表) 插補搜尋法 費氏搜尋法 稀疏矩陣 多維矩陣轉一維矩陣 上三角、下...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于【自动提示】的需要(如:Google搜索), 而开发的架构无关的公共控件, 以满足该类...
快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表) 插補搜尋法 費氏搜尋法 矩陣 稀疏矩陣 多維矩陣轉一維矩陣...