快速排序

该方法的基本思想是：

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。 

  package PaiXu;
   
  import java.util.Scanner;
   
  public class KuaiSuPaiXu {
      public static void main(String[] args) {
          Scanner sc=new Scanner(System.in);
          int n=sc.nextInt();
          int arr[]=new int [n];
          for(int i=0;i<arr.length;i++){
              arr[i]=sc.nextInt();
          }
          paixu(arr,0,arr.length-1);
          for (int i = 0; i < arr.length; i++) {
              System.out.print(arr[i]+" ");
          }
      }
   
      public static void paixu(int arr[], int low, int high){
          //temp保存基准数的数据，i基准数开始向后遍历，j从数组最后一位往前遍历
          int i,j,temp;
          if(low>high){
              return ;
          }
          i=low;
          j=high;
          temp=arr[low];
          while(i<j){
              //先看右边，找出比基准数小的数的下标j
              while(arr[j]>=temp&&i<j){
                  j--;
              }
              //在看左边，找出比基准数大的下标i
              while(arr[i]<=temp&&i<j){
                  i++;
              }
              //交换arr[i],arr[j]的位置
              if(i<j){
                  int t=arr[j];
                  arr[j]=arr[i];
                  arr[i]=t;
              }
          }
          arr[low]=arr[i];
          arr[i]=temp;
          //基准数左边快排
          paixu(arr,low,j-1);
          //基准数右边快排
          paixu(arr,j+1,high);
      }
   
  }