快速排序

快速排序

　　快速排序：快速排序是冒泡排序的升级版

• 其核心思想是：在每次排序中选择一个基准数，从待排序数组两段分别查找数，左端查找大于基准数的数，右端查找小于基准数的数，找到了就交换左右两个位置数的值，直到两个查找的指针相遇于同一个数，即停止交换。
• 我们将这个找到的重合位置的值和一开始的基准数的值交换位置，然后由这个值将数组分为两部分
• 对由这个基准值确定的“中间值”来将数组分成左右两部分，分别递归使用快速排序算法，直到所有的数据都有序。

java代码如下：

/**
 * 快速排序：快速排序是冒泡排序的升级版
 * 其核心思想是：在每次排序中选择一个基准元素，从待排序数组两段分别查找元素，左端查找大于基准元素的元素
 * 右端查找小于基准元素的元素，找到了就交换左右两个位置元素的值，直到两个查找的指针相遇于同一个元素，即停止交换。
 * 我们将这个找到的重合位置的值和一开始的基准元素的值交换位置，然后由这个值将数组分为两部分
 * 分别递归使用快速排序算法，直到所有的数据都有序。
 * @author 1
 *
 */
public class QuickSort {
	public static void QuickSort(int [] arr) {
		int left=0;
		int right=arr.length-1;
		sortHelper(arr, left, right);
	}
	private static void sortHelper(int [] arr, int left, int right) {
		if(left>right) {
			return;
		}
		
		int temp=arr[left]; //temp中存放的是基准数
		int i=left;
		int j=right;
		
		while(i!=j) {
			//先从右往左找，因为我们的基准数选择的是左边
			while(arr[j]>=temp && i<j) {
				j--;
			}
			//再从左往右找
			while(arr[i]<=temp && i<j) {
				i++;
			}
			//找到了就交换两个数
			if(i<j) {
				int t=arr[i];
				arr[i]=arr[j];
				arr[j]=t;
			}
		}
		//将基准数交换到我们找到的那个最“中间”的位置
		arr[left]=arr[i];
		arr[i]=temp;
		//递归调用
		sortHelper(arr, left, i-1);
		sortHelper(arr, i+1, right);
	}
	
	public static void main(String[] args) {
		int [] arr= {7,6,5,4,3,2,1};
		QuickSort(arr);
		for(int i:arr) {
			System.out.print(i+" ");
		}
	}
}