我所理解的快速排序算法      快速排序是在实践中最快的已知排序算法，它的平均运行时间是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);      }}   补充一个五数(你可以设置任意大于2的整数)中值分割法选取枢纽元.    Mark Allen Weiss在其著作<<数据结构与算法分析--c语言描述>>中对枢纽元的选取进行了分析.他认为使用第一个元素作为枢纽元是绝对糟糕的主义----我前面就是这样做的,呵呵.比较安全的做法是随机选取枢纽元,但是随机数的生成太"昂贵"了,会使效率降低.比较实用的是多元中值分割法(书上举了三数中值分割法的例子),枢纽元的最好位置是数组的中值,这样把数组分成两个相等的部分是最佳的.但是要寻找数组的中值可不是一件容易的事,我们只好折中一下,使用左端,右端和中心位置的三个元素的中值作为枢纽元.    对于很小的数组(N<=20),快速排序不如插入排序好.所以我们可以设置一个长度上限max,当数组的长度大于max时,递归快速排序,否则使用插入排序.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){      const int max = 5;//确定是否采用插入排序的数组长度上限           if (high-low >= max)      {            int k = Parttion(a, low, high);            Qsort(a, low, k-1);            Qsort(a, k+1, high);      }      else    //如果数组的元素很少（小于5个 ），使用折半插入排序           HalfInsertSort(a+low, high-low+1);    }template <class T>void Swap(T &a, T &b){    T temp = a;    a = b;    b = temp;}template <class T>T Median(T a[], int low, int high)//取中间元素的值作为枢纽元素，同时对两端的元素排序 {    int mid = (low + high) / 2;    if (a[low] > a[mid])        Swap(a[low], a[mid]);    if (a[low] > a[high])        Swap(a[low], a[high]);    if (a[mid] > a[high])        Swap(a[mid], a[high]);            Swap(a[mid], a[low+1]);//把枢纽元素放到数组的第2个位置     return a[low+1];}template <class T>int Parttion(T a[], int low, int high)//根据枢纽元素分割数组 {    T pivot = Median(a, low, high);     int i = low + 1;    int j = high;    while (i < j)    {        while (a[++i] < pivot) {}        while (a[--j] > pivot) {}        if (i < j)            Swap(a[i], a[j]);    }            Swap(a[j], a[low+1]);     return j;}template <class T>void HalfInsertSort(T a[], int len)//折半插入排序 {      int i, j;      int low, high, mid;      T temp;      for (i=1; i<len; i++)      {            temp = a[i];            low = 0;            high = i - 1;            while (low <= high) //在a[low。。。high]中折半查找有序插入的位置            {                  mid = (low + high) / 2;                  if (a[mid] > temp)                        high = mid - 1;                  else                        low = mid + 1;            } //while            for (j=i-1; j>high; j--)//元素后移                  a[j+1] = a[j];            a[high+1] = temp; //插入      }//for}

评论