Jun 22 2006

快速排序

Category: 技术ssmax @ 18:01:24

我所理解的快速排序算法(加上黄金分割就完美啦~)
      快速排序是在实践中最快的已知排序算法,它的平均运行时间是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);
      }
}

Leave a Reply