我所理解的快速排序算法      快速排序是在实践中最快的已知排序算法，它的平均运行时间是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);      }}

评论