排序

常见的排序

• 时间复杂度O(n^2): 插入, 冒泡, 交换
• 时间复杂度O(n lgn): 快速, 希尔, 堆栈, 并归

关于快速排序

void quickSort(int[] arr,int low,int hight){
      int pivot = getPivot(arr,low,hight);
      int pivotVal = arr[pivot];
      int i=low;
      int j=hight;
  
      while(i<j)
      {
             while(i<j&&int[i]<pivotVal ){
                   i++;
              }
               while(i<j&&int[j]>pivotVal ){
                   j--;
              }
          
            if(i>=j){
                break;
           }else{
                swap(arr,i,j);
             }
       }
      swap(arr,i,pivot );
      quickSort(arr,i,pivot -1);
      quickSort(arr,pivot +1,j);
}

空间复杂度 lg(n); 最差的空间复杂度(n)

解决空间复杂度的getPivot() 方法的实现.
比如随机选三个数, 去中间的数作为 pivot