goal00001111

我所理解的快速排序算法
      快速排序是在實踐中最快的已知排序算法，它的平均運行時間是O（NlogN）。該算法之所以特別快，主要是由于非常精練和高度優化的內部循環。在隊列中尋找合適的樞點元素，并按樞點元素劃分序列，是快速排序算法的關鍵。
      為簡單起見，我這里數組的第一個元素作為樞點元素，重新排列數組，使得樞點元素之前的元素都小于樞點元素，而樞點元素之后的元素都大于或等于樞點元素。
      在這里我提供算法的兩種實現：
第一種：
template <class T>
int Parttion(T a[], int low, int high)
{
      T x = a[low];

      while (low < high)
      {
            while (low < high && a[high] >=  x)
                  high--;
            a[low] = a[high];

            while (low < high && a[low] <  x)
                  low++;
            a[high] = a[low];
      }

      a[low] = x;
      return low;
}
第二種：
template <class T>
int Parttion(T a[], int low, int high)
{
      T x = a[low];
      int i = low;
     
      for (int j=low+1; j<=high; j++)
      {
            if (a[j] <= x)
            {
                  i++;
                  if (i != j)
                        Swap(a[i], a[j]);
            }
      }
     
      Swap(a[low], a[i]);
      return i;
}

template <class T>
void Swap(T & a, T & b)
{
      T t = a;
      a = b;
      b = t;
}

快速排序的驅動程序：
template <class T>
void QuickSort(T a[], int len)
{
      Qsort(a, 0, len-1);
}

template <class T>
void Qsort(T a[], int low, int high)
{
      if (low < high)
      {
            int k = Parttion(a, low, high);
            Qsort(a, low, k-1);
            Qsort(a, k+1, high);
      }
}