排序算法--快速排序

快速排序是最经典，最常用的高效排序算法之一。快排和归并排序算法一样，采用的是分治的思想。具体步骤如下：

分：从未排序数组中选择一个数组作为关键字，对序列进行一次排序，是的关键词左侧的数的数都比关键字小，右侧的数都比关键字大。
治：不用操作，分完已经是有序的了。

• 平均时间复杂度O(nlogn)
• 空间复杂度：快排空间复杂度主要消耗在递归调用。
  最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
  最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

class Solution
{
      int quickSortPartition(vector<int> & array, int start, int end)
      {
          int pivot = array[start];
          int i = start, j = end;
          while(i < j)
          {
              while((array[j] >= pivot) && (i < j)) //这里必须加上 i < j的判断
                      j--;
              while((array[i] < pivot) && (i < j))
                     i++;
              swap(array[i],array[j]);
          }
          swap(array[start], array[i]); 
          return i;  //最后返回partition的位置
      }
      void quickSortHelper(vector<int> & array, int start, int end)
      {
          if(start < end)
          {
               int mid = quickSortPartition(array,start,end);
               quickSortHelper(array,start,mid);
               quickSortHelper(array,mid+1,end);
          }
          return;
      }
      void quickSort(vector<int> & array)
      {
            int num = array.size();
            quickSortHelper(array,0,array.size()-1);
            return;
      }
}