快速排序（java）

快速排序的基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分的值均比另一部分的值小，再分别对两部分继续进行排序，直到整个序列有序。

稳定性：由于关键字的比较和交换是跳跃进行的， 快速排序不是一种稳定的排序方法。

public class Sort {
  public static void quickSort(int arr[], int low, int high){
    int pivot;
     if (low < high) {
       pivot = partition(arr, low, high);
       quickSort(arr, low, pivot -1); //对左半部分递归排序
       quickSort(arr, pivot + 1, high); //对右半部分递归排序
    }
  }

  public static int partition(int arr[], int low, int high){
    int pivotValue = arr[low];
    while(low < high) {
      while(low < high && arr[high] > pivotValue) high--;
      swap(arr, low, high);
      while(low < high && arr[low] < pivotValue) low++;
      swap(arr, low, high);
    }
    return low;
  }

  public static void swap(int  arr[], int index_1, int index_2){
    int temp = arr[index_ 1];
    arr[index_1] = arr[index_2];
    arr[index_2] = temp;
  }

   public static void main(String[] args) {
        int[] sortArray = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        Sort.quickSort(sortArray， 0， sortArray.length - 1);
        for(int num: sortArray) {
            System.out.println(num + " ");
        }
   }
}

时间复杂度：最优O(nlogn)， 最差O(n^2), 平均O(nlogn)
空间复杂度：对栈的空间的使用，最优O(logn)， 最差O(n), 平均O(l**ogn)

快速排序优化：

1.优化选取枢轴： 随机选取， 对小数组三数取中，对大数组九数取中

//三数取中
int pivotValue;
int m = low + (high - low) / 2
if (arr[low] > arr[high]) {
  swap(arr, low, high);
}
if(arr[m] > arr[high]) {
  swap(arr, m, high);
}
if(arr[low] > arr[m]) {
  swap(arr, low, m);
}

2.优化不必要的交换
直接将枢轴移到最终位置

  public static int partition(int arr[], int low, int high){
    int pivotValue = arr[low];
    while(low < high) {
      while(low < high && arr[high] > pivotValue) high--;
      arr[low] = arr[high]
      while(low < high && arr[low] < pivotValue) low++;
      arr[high] = arr[low]
    }
    arr[low] = pivotValue;
    return low;
  }

3.优化小数组时的排序
数组非常小时，直接插入排序更好

public static void quickSort(int arr[], int low, int high){
  if(arr.length > 50) {
    int pivot;
    if (low < high) {
      pivot = partition(arr, low, high);
      quickSort(arr, low, pivot -1); //对左半部分递归排序
      quickSort(arr, pivot + 1, high); //对右半部分递归排序\
    } 
  } else {
    Insertsort(arr, low, high)
  }
}

4.优化递归操作
减少递归次数

public static void quickSort(int arr[], int low, int high){
  if(arr.length > 50) {
    int pivot;
    while (low < high) {
      pivot = partition(arr, low, high);
      quickSort(arr, low, pivot -1); //对左半部分递归排序
      low = pivot + 1;
    } 
  } else {
    Insertsort(arr, low, high)
  }
}