快速排序--Java实现

快速排序：

方法一：以第一个数为基数，定义两个数，一个记录从后往前遍历的下标，一个记录从前往后遍历的下标，先从后往前遍历，找到一个数比基数小的值，记录下标，在从前往后遍历，找到一个比基数大的数，记录下标，交换两个数的位置，再继续遍历，先从后往前，再从前往后，一直到两个记录下标的数相等，则交换基数和该下标对应的数的位置，即该下标的数变成了第一个数（因为是先从后往前的，所以该下标对应的数肯定是小于基数的，自己可以举例），这样就是一轮排序，然后再递归排序基数左边和右边的子数组（基数的下标为最后的下标记录）

方法二：选第一个数为基数，先从后往前遍历，找到一个数比基数小的，交换基数和该数的位置，再从前往后遍历，找到一个数比基数大，交换基数和该数的位置，以此类推，直到前后连个记录下标相等，这样为一次遍历，再递归基数左边和右边的子数组

package Sort;
/*
 * 快速排序
 */
public class SortTest1 {

	public static void main(String[] args) {
		int[] arr={3,1,2,5,6,1,3,8,4,9,2,-1,5,-6,0};
//		int[] arr={2,1,1,1,1,1,1,1};
		for(int i:arr){
			System.out.print(i+" ");
		}
		System.out.println();
//		new SortTest1().quickSort(arr, 0, arr.length-1);
		new SortTest1().quickSort2(arr, 0, arr.length-1);
		for(int i:arr){
			System.out.print(i+" ");
		}
	}

	//方法一
	public void quickSort(int[] arr,int start,int end){
		if(arr==null||start>=end){
			return;
		}
		int temp=arr[start];
		int i=start;
		int j=end;
		while(j>i){
			while(j>i&&arr[j]>=temp){
				j--;
			}
			while(j>i&&arr[i]<=temp){
				i++;
			}
			if(j>i){
				int t=arr[j];
				arr[j]=arr[i];
				arr[i]=t;
			}
		}
		arr[start]=arr[i];
		arr[i]=temp;
		quickSort(arr, start, i-1);
		quickSort(arr, i+1, end);
	}

	//方法二
	public void quickSort2(int[] arr,int start,int end){
		if(arr==null||start>=end){
			return;
		}
		int key=arr[start];
		int low=start;
		int high=end;
		while(high>low){
			while(high>low&&arr[high]>=key){
				high--;
			}
			if(arr[high]<key){
				int temp=arr[low];
				arr[low]=arr[high];
				arr[high]=temp;
			}
			while(high>low&&arr[low]<=key){
				low++;
			}
			if(arr[low]>key){
				int temp=arr[low];
				arr[low]=arr[high];
				arr[high]=temp;
			}
		}
		
		if(low>start)
			quickSort2(arr, start, low-1);
		if(low<end){
			quickSort2(arr, low+1, end);
		}
	}
	
}