排序--快速排序

快速排序利用分治策略

原理：
取数组中的一个值pivot做为基准值，对数组分治，小于pivot分为一组，大于pivot分为一组
递归对每个分组继续分组，直到分组中只有一个元素
主要包括两个步骤
1： 以一个基准值为中心，把数组分成两组
2： 对每个分组递归分组，直到分组元素只有一个

实现：
 private static int partition(int[] array, int low, int high)
 {
  int pivot = array[low];    //pivot可以为数组中的任何一个，只要将它与第一个交换即可
  while( low < high )
  {
   while( low < high && array[high] > pivot )
    high--;
   if ( low < high )
    array[low++] = array[high];
   while( low < high && array[low] <= pivot)
    low++;
   if ( low < high )
    array[high--] = array[low];
  }
  array[low] = pivot;
  return low;
 }
 public static void quickSort(int[] array, int low, int high)
 {
  int pivotPos;
  if ( low < high )
  {
   pivotPos = partition(array, low, high);
   quickSort(array, low, pivotPos - 1);
   quickSort(array, pivotPos + 1, high);
  }
 }

算法复杂度分析：
复杂度只要依赖于递归树的高度

平均情况下(即分组均匀，每个分组的元素大概为原数组的1/2时）：递归树高度为O(nlogn)
因为对数组分组的操作需要O(n)，此时复杂度为  O(nlogn)

最坏情况（数组有序，此时递归树退化为直线）：树高度为O(n)， 所以复杂度为O(n^2)

空间复杂度：（取决于递归层数）
同时间复杂度
平均： O(logn)
最坏： O(n)

稳定性：
快速排序为非稳定排序

优化：
由于基准值的选取直接关系到分组是否均匀，所以随机选择数组中的一个数做为pivot,然后将其和第一个元素交换
这样随机后，数组分组较为均匀