手机
当前位置:查字典教程网 >编程开发 >Java >JAVA算法起步之快速排序实例
JAVA算法起步之快速排序实例
摘要:快速排序一听这个名字可能感觉很快,但是他的算法时间复杂度最坏情况却跟插入排序是一样的。之所以成为快速排序是因为他的平均效率比堆排序还要快,快...

快速排序一听这个名字可能感觉很快,但是他的算法时间复杂度最坏情况却跟插入排序是一样的。之所以成为快速排序是因为他的平均效率比堆排序还要快,快速排序也是基于分治思想与归并排序差不多,但是快速排序是原址的,直接在原数组操作不需要再开辟新的存储空间。快速排序的思想很简单,就是选定一个关键字k将原数组分成两份g1与g2,g1中所有的元素都比k小或者相等,而g2中所有的数据都比k大或者等于,这样对g1与g2分别进行快速排序,最终我们得到的就是一个有序的数组。代码中的sort方法就是对刚才语句的描述。而关键的算法就是去寻找k的位置将原数组分为大小两部分的过程。方法getPlocation就是快速排序的核心。他的实现原理有点像插入排序只是有点像。每次都把map中end位置的元素作为关键字,通过与end元素对比将数组分成大小两部分,而i与j则是两个分割线,i与j之间的数都是比core大的元素,i与j就像一条贪吃蛇,当j的下一个数比core大的时候j+1,i到j的长度增大了,而如果比core小的话,i与j都向前走一下,并将那个小数放在i的前面。这样循环一遍后,start到end-1之间就是按大小分开的,最后将core放在中间,将core的位置返回就是分界线了。

复制代码 代码如下:

public class QuickSort {

public int getPlocation(int[] map,int start,int end){

int core=map[end];

int i=start-1;

for(int j=start;j<=end-1;j++){

if(map[j]<=core){

i++;

int cache=map[j];

map[j]=map[i];

map[i]=cache;

}

}

i++;

map[end]=map[i];

map[i]=core;

return i;

}

public void sort(int[] map,int start,int end){

if(start<end){

int p=getPlocation(map, start, end);

sort(map, start, p-1);

sort(map,p+1,end);

}

}

public static void main(String[] args) {

int[] map=new int[]{4,1,5,3,7,12,65,7};

QuickSort qs=new QuickSort();

qs.sort(map, 0, map.length-1);

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

System.out.println(map[i]);

}

}

}

【JAVA算法起步之快速排序实例】相关文章:

JAVA计算两个日期相差的实例

十种JAVA排序算法实例

java实现MD5加密算法的实例代码

java实现合并两个已经排序的列表实例代码

JAVA读取文件夹大小的几种方法实例

Java通过接口实现匿名类的实例代码

Java泛型的简单实例

Java冒泡排序(Bubble Sort)实例讲解

JAVA应用系统工具快捷托盘实例代码

Java 快速排序(QuickSort)原理及实现代码

精品推荐
分类导航