快速排序是最經(jīng)典，最常用的高效排序算法之一?？炫藕蜌w并排序算法一樣，采用的是分治的思想。具體步驟如下：

分：從未排序數(shù)組中選擇一個(gè)數(shù)組作為關(guān)鍵字，對(duì)序列進(jìn)行一次排序，是的關(guān)鍵詞左側(cè)的數(shù)的數(shù)都比關(guān)鍵字小，右側(cè)的數(shù)都比關(guān)鍵字大。
治：不用操作，分完已經(jīng)是有序的了。

• 平均時(shí)間復(fù)雜度O(nlogn)
• 空間復(fù)雜度：快排空間復(fù)雜度主要消耗在遞歸調(diào)用。
  最優(yōu)的情況下空間復(fù)雜度為：O(logn) ；每一次都平分?jǐn)?shù)組的情況
  最差的情況下空間復(fù)雜度為：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;
      }
}