快速排序

介绍:

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

代码

代码将基准变成最左边的值，左边都比中间值小，右边都比中间值大

import java.util.Arrays;
public class QuickSort {
  public static void main(String[] args) {
    int[] arr = {9,2,1,10,34,12,0,-9,100};
    quickSort(arr, 0, arr.length - 1);
    System.out.println("arr=" + Arrays.toString(arr));
  }
  public static void quickSort(int[] arr, int left, int right) {
    int i, j, t, temp;
    if (left > right)
      return;
    temp = arr[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while (i != j) { //顺序很重要，要先从右边开始找
      while (arr[j] >= temp && i < j)
        j--;
      while (arr[i] <= temp && i < j)//再找右边的
        i++;
      if (i < j)//交换两个数在数组中的位置
      {
        t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
      }
    }
    //最终将基准数归位
    arr[left] = arr[i];
    arr[i] = temp;
    quickSort(arr, left, i - 1);//继续处理左边的，这里是一个递归的过程
    quickSort(arr, i + 1, right);//继续处理右边的 ，这里是一个递归的过程
  }
}