排序算法之快速排序算法
快速排序思想：
选一个基准数将所有的元素都比较一遍，将大于基准数的放到基准
数的右边，小于它的放到基准数的左边。将元素分为两个子区间，
然后比较各个子区间的元素进行排序即可；
快速排序原理：
（以升序为例)
1.首先从数组中取出一个数作为基准数
2.将大于基准数的元素放置基准数的右边，小于或者等于基准数
的放置基准数的左边。
3.对两个字区间重复以上操作，知道各个区间只有一个元素
话不多说，上干货
public static int[] quickSort(int arr[],int begin,int end){
//设置跳出方法的地方
if(begin>end){
return arr;
}
//获取到基准数
int key=arr[begin];
int i=begin;
int j=end;
while(i<j){
//先从右边寻找第一个小于基准数的元素
while(i<j&&arr[j]>key){
j--;
}
//从左边寻找第一个大于基准数的元素
while(i<j&&arr[i]<=key){
i++;
}
//将两个元素交换
if(i<j){
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=arr[i];
}
//继续从交换元素的位置寻找 直到i=j
//这时的j下标所对应的位置是key所应当在的位置
}
//交换下标为j的元素和key
arr[begin]=arr[j];
arr[j]=key;
return arr;
}
public static void main(String[] args){
int arr[]=new int []{5,9,6,7,8,4,3,1,2};
System.out.println(Arrays.toString(quickSort(arr, 0, arr.length-1)));
}
