java中快速排序的优化
程序员文章站
2024-03-25 13:08:16
...
接上节讲的快速排序,我们来了解一下几种它的优化。
1.随机取基准
上节我们采取的是以开头为基准,然后进行一次快速排序,但是如果原数组相对有
序的话,那么就会出现每次找基准,原数组顺序不变,时间复杂度相当的高,为了处
理这种情况我们采用随机选取基准,就是
public static void new_Quick(int[] array,int low,int high){
swap(array,low,rand.nextInt(high-low+1)+low); //因为不知道起始位置,所以后面加上low
int par = partion(array,low,high);
if(par > low+1){
Quick(array,low,par);
}
if(par < high-1){
Quick(array,par+1,high);
}
}
public static void swap(int[] array,int start,int end){
int tmp = array[start];
array[start] = array[end];
array[end] = tmp;
}
2.当前数组中的值过少可以采取直接快速排序法
这种方法我们就不多做介绍了,我们可以自己确定一个数,比如十,少于十的时
候,直接调用快速排序的方法。
3.聚集相同元素法
经常会出现一个数组中有很多个相同的元素,为了方便和加速递归,相同的元素我
们可以不用再次递归,直接放在基准的左右位置。
以如图为例,我们发现第一次的基准12,有很多相同的元素,那我们遍历的时候可以
将12放在他的周围,然后从除12的数字遍历
然后就是代码实现:
public static int [] fun(int []array,int right,int left,int start,int end,int par){
int parRight = par-1;
int parleft = par+1;
int tmp = 0;
for(int i = parleft;i>=start;i--){
if(array[par] == array[i]){
if(i != parleft){
tmp = array[parleft];
array[parleft] = array[i];
array[i] = tmp;
parleft--;
}
}else{
parleft--;
}
}
left = parleft;
for(int j = parRight;j<=end;j++){
if(array[par] == array[j]){
if(j != parleft){
tmp = array[parRight];
array[parRight] = array[j];
array[j] = tmp;
parRight++;
}
}else{
parRight++;
}
}
right = parRight;
int a[] = {left,right};
return a;
}
如有错误,请多多指教。
上一篇: jq轮播原理及实现
推荐阅读
-
java中快速排序的优化
-
Java中的快速排序算法
-
java中各种流的应用场景 博客分类: java基础 java流区别inputstreamOutputStreamWriter
-
java类中读取xxx.properties文件的内容 博客分类: java
-
命令行下面编译运行eclipse中编写的带有包名的java文件
-
JAVA学习中的知识点
-
2012/4/9----二叉查找树(二叉排序树)的各种操作 博客分类: 算法 算法java二叉查找树二叉排序树akon405
-
java中的内存分析 博客分类: java java内存堆栈常量池
-
Java中volatile关键字的效果 博客分类: Java基础 Java多线程thread工作JVM
-
Java中volatile关键字的效果 博客分类: Java基础 Java多线程thread工作JVM