快速排序

快速排序的思想：选第一个元素为标杆元素，大小分站两边，然后进行递归，直至不再可以分区

Q1：为什么先指向尾部+1？

A：因为先--,为了防止错过最后一个元素，所以加1。

Q2：为什么和从尾部过来的 j 交换？

A：只能和指向低半区的j交换，如果和高半区的 i 交换，则 i 去了低半区

和向标杆趋近的 j 交换

  

   

    

     

    
    

     

      package com;
     
    
   

    

     

    
    

     

      import static java.lang.System.out;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class QuickSort {
     
    
   

    

     

    
    

     
	//a为待排序的数组，s为开始索引，e为结束索引
     
    
   

    

     

    
    

     
	static int p(int[] a ,int s,int e){
     
    
   

    

     

    
    

     
		
     
    
   

    

     

    
    

     
		int temp;
     
    
   

    

     

    
    

     
		int i=s;
     
    
   

    

     

    
    

     
		int j =e+1;//因为先--,为了防止错过最后一个元素，所以加1。
     
    
   

    

     

    
    

     
		//将开头元素作为标杆 
     
    
   

    

     

    
    

     
		int x = a[s];
     
    
   

    

     

    
    

     
		while(true){
     
    
   

    

     

    
    

     
			//找到第一个比标杆大的元素 ，大于停
     
    
   

    

     

    
    

     
			while(a[++i]<x&&i<e);
     
    
   

    

     

    
    

     
			//找到第一个比标杆小的元素 ，小于停
     
    
   

    

     

    
    

     
			while(a[--j]>x);
     
    
   

    

     

    
    

     
			//如果两个索引交叉，则结束循环 
     
    
   

    

     

    
    

     
 //7,2,3,4,9,15,16,如果当前i,j指针指向4，9， 
     
    
   

    

     

    
    

     
 //最后一次i,j 的位置分别指向9，4,j指向低区最后一个元素的位置，所以把标杆放在j位置
     
    
   

    

     

    
    

     
 //只能和指向低半区的j交换，如果和高半区的j交换，则9去了低半区
     
    
   

    

     

    
    

     
			if(i>=j){
     
    
   

    

     

    
    

     
 break;	
     
    
   

    

     

    
    

     

      			} 
     
    
   

    

     

    
    

     

      			temp = a[i];
     
    
   

    

     

    
    

     

      			a[i]= a[j];
     
    
   

    

     

    
    

     

      			a[j] = temp;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		temp = a[j];
     
    
   

    

     

    
    

     

      		a[j]= a[s];
     
    
   

    

     

    
    

     

      		a[s]= temp;
     
    
   

    

     

    
    

     
		return j;
     
    
   

    

     

    
    

     
		
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	static void quick(int[] a ,int s,int e){
     
    
   

    

     

    
    

     
		if(s<e){
     
    
   

    

     

    
    

     
			int q = p(a,s,e);
     
    
   

    

     

    
    

     

      			quick(a,s,q-1);  
     
    
   

    

     

    
    

     

      			quick(a,q+1,e); 
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	public static void main(String[] args) {
     
    
   

    

     

    
    

     
		int a[] ={1,8,2,5,4,7,6,3};  
     
    
   

    

     

    
    

     

       quick(a,0,7);  
     
    
   

    

     

    
    

     
 for(int i =0;i<8;i++){
     
    
   

    

     

    
    

     

       out.println(a[i]);
     
    
   

    

     

    
    

     

       }  
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: gamwatcher.blog.csdn.net，作者：香菜聊游戏，版权归原作者所有，如需转载，请联系作者。

原文链接：gamwatcher.blog.csdn.net/article/details/7463526