登陆 注册

java算法实现之快速排序

守望者 2020-04-08 170人围观 ,发现0个评论 java

      所谓快速排序就是将数组分成a, b两个数组,使得a数组的所有元素都小于b数组的所有元素,此为完成一轮排列,

然后再将数组a,b各自再分成两个更小数组,使得两个更小数组之间的关系同a和b两个数组的关系一样,此为又完成一轮排列,

然后再对更小数组进行同样的划分,如此往复循环,多次细分数组,最终实现整个数组的所有元素实现有序排列。


在每一轮排列过程中需要三个变量:


key变量:一般初始化为arr[0], 即为后面被比较的关键值;

left变量:数组左边的下标,后面left++不断右移;

right变量:数组右边的下标,后面right--不断左移;


每轮排序过程如下:


  步骤一:从数组下标right开始,自右向左(right--),逐一与key值比较,

               如果发现arr[right]<key值,则arr[left]与arr[right]元素互换位置;

  步骤二:从数组下标left开始,自左向右(left++),逐一与key值比较,

                如果发现arr[left]>key值,则arr[left]与arr[right]元素互换位置;

  步骤三:重复以上两个步骤,直至left=right, 退出循环;


      此时已完成一轮排序,并且分成a,b两个数组(小于key值的元素划分为a数组,大小key值的元素划分为b数组),

并且a数组的所有元素都小于b数组的所有元素。


     重复以上排序过程(递归调用),直至所划分数组元素个数为1时退出循环,此时整个数组排序完成。


快速排序函数代码如下:

public static void quikeSort(int arr[],int start,int end) {   
		// 快速排序函数
		
	    int key = arr[start];        
	    int left = start;        
	    int right = end;        
	    while (left<right) {            
	        while ((left<right)&&(arr[right]>key)) {                
	        	right--;            
	        }     
	       
	        while ((left<right)&&(arr[left]<key)) {                
	        	left++;            
	        }            
	        if ((arr[left]==arr[right])&&(left<right)) {                
	        	left++;            
	        } else {                
	            int temp = arr[left];                
	            arr[left] = arr[right];                
	            arr[right] = temp;            
	        }        
	    }        
	    for (int i:arr) {            
	        System.out.print(i+" ");        
	    }    
	    System.out.println();
	    
	    if (left-1>start)quikeSort(arr,start,left-1);        
	    if (right+1<end) quikeSort(arr,right+1,end);        
//	    return (arr);    
	}    
	 
	public static void main(String[] args) {        
	    int arr[] = {15,8,3,9,21,28,19,12};     
	    int len = arr.length-1;        
	    quikeSort(arr,0,len);        
	    for (int i:arr) {            
	        System.out.print(i+" ");        
	    }    
	}


   转发请附上本文链接:https://tufeng.xyz/java/43.html,谢谢合作!

请发表您的评论
请关注微信公众号
微信二维码