快速排序算法

package day2;
/*快速排序算法:将一个大数组的排序,分解成2个数组的排序。而每个小数组又可分解成更小的2个数组,这样数组的排序的方式可以一直递归下去
 *           直到数组的大小为2.在第一次划分的时候,选择第一个基准元,然后将它分成左右两个无序的数组,并且,使得左边的所有元素都小于
 *           等于基准元素,而右边的元素都大于等于基准元素,然后对左边和右边的数组做同样的递归操作。通常,选择最左边的俄元素作为基准元素
 *           ,或数组中间的元素作为基准元素。
 */
public class Array4 {

	public static void main(String[] args) {
		
		// TODO Auto-generated method stub
       int arr[]={4,5,8,7,6,9,1,2,0,11,12,15};
       sort(arr);
       for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i]+"\t");
	}
		
	}
	//排序方法
	public static void sort(int[] number){
		
		quickSort(number,0,number.length-1);
	}
	//快速排序方法
	public static void quickSort(int[] number,int left,int right){
		if(left<right){
			int s=number[left];
			int i=left;
			int j=right+1;
			while(true){
				//向右找大于s的数的索引
				while(i+1<number.length&&number[++i]<s)
				  ;
				//向左找小于s的数的索引
				while(j-1>-1&&number[--j]>s)
				  ;
				//如果i>=j,就退出循环
				if(i>=j){
				 
					break;
				}
				//否则交换索引i和j的元素
				swap(number,i,j);
			
			}
			number[left]=number[j];
			number[j]=s;
			//左边进行递归
			quickSort(number,left,j-1);
			//右边进行递归
			quickSort(number,j+1,right);
			
		}
		
	}
	//交换数组number中的索引为i,j的元素
	private static void swap(int[] number,int i,int j){
		
		int t;
		t=number[i];
		number[i]=number[j];
		number[j]=t;
		
	}

}

相关推荐