[算法]快排-快速排序

关于排序算法：对大学时老师讲的冒泡法、直接插入法、交换法等印象深刻，但工作后都是直接调用java的工具类的sort方法。

快排的思想：分而治之。

• 随意选取一个元素，以此元素为基准将所有元素分为两区，所有小于此元素的为一区，所有大于此元素的为另一区。
• 继续对两区分别进行如此的操作，直到分区内只剩一个元素
• 也可以理解为每轮分区最终会将所有元素分为三个区，左区为所有小于基准元素的元素，中区为等于基准元素的元素，右区为大于基准元素的元素。
• 每轮分区后，每个分区内的元素并非有序的，而是逐渐细分后，当每个分区内只有一个元素时，其自然有序。

快排代码实现：

import static java.lang.System.out;
import java.util.*;

public static void main(String[] args){
		int [] a = new int[10];
		
		// 随机生成10个100以内的整数
		Random  r = new Random();  
		for(int i=0;i<a.length;i++){
			a[i] = r.nextInt(100);	
		}
		// 排序前，输出查看一下
		out.println(Arrays.toString(a));
		
		//排序
		partition(a,0,a.length-1);
		
		//排序后，输出查看一下
		out.println(Arrays.toString(a));
		
	}

    // 分区，分而治之的排序
	static void	partition(int [] a,int low,int high){
		
		if(low>=high) return;
		
		int base = a[low];
		int i= low+1;
		int j =high;


		// 先从前向后找一个大于base的元素，而后从后往前找一个小于base的元素，
		// 如果前者的下标比后者的下标更小,那么就交换这两个元素
		// 继续这种比较和交换，直到前者的下标比后者的位置大(说明大于base的元素全都在小于base的元素之后的位置了)
		while(i<j){
			while(i < high && a[i] < base){
				i++;
			}
			while(j > low && a[j]> base){
				j--;
			}
			if(i<j) swap(a,i,j);

		}

		// 最后，将base与从后往前找到的第一个比它base的元素交换位置。
		// 经过上边的一轮比较和交换后，j就是第一个比base小的元素的位置
		// 因为下标比j大且数值比base小的元素，经过之前的比较和交换后，都被交换到小于j位置上去了
		swap(a,low,j);

		// 经过以上一轮的选择和交换，已经将low~high间的所有元素以base为基准，完成分区了，
		// 下边继续对分区进行分区，直到分区中只有一个元素
		partition(a,low,j-1);
		partition(a,j+1,high);
	
	}
		
	public static void swap(int [] a,int i,int j){
		if(i!=j){
			int tmp = a[i];
			a[i]=a[j];
			a[j]=tmp;
		}
		
	}