排序算法之快速排序

排序算法之快速排序算法

快速排序思想：
选一个基准数将所有的元素都比较一遍，将大于基准数的放到基准
数的右边，小于它的放到基准数的左边。将元素分为两个子区间，
然后比较各个子区间的元素进行排序即可；

快速排序原理：

（以升序为例)
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)));

}