欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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.聚集相同元素法

    经常会出现一个数组中有很多个相同的元素,为了方便和加速递归,相同的元素我

们可以不用再次递归,直接放在基准的左右位置。

 java中快速排序的优化

以如图为例,我们发现第一次的基准12,有很多相同的元素,那我们遍历的时候可以

将12放在他的周围,然后从除12的数字遍历

java中快速排序的优化

然后就是代码实现:

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轮播原理及实现

下一篇: