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);
      }
}