[原创]我所理解的快速排序算法

主题：[原创]我所理解的快速排序算法

goal00001111 [专家分：4030] 发布于 2006-06-12 22:04:00

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

本帖地址： http://bbs.pfan.cn/post/174475.html

回复列表（共12个回复）

11 楼

bpttc [专家分：8790] 发布于 2007-05-30 22:30:00

仔细观察，发现快速排序实际上是一个二叉树的先序遍历。
拿出套路，先序遍历递归该非递归，将快排改成非递归形式。
代码如下：

#include <stdlib.h>

void InsertionSort( int* start, int* end )
{
        int* p = NULL;
        int* q = NULL;
        int tmp;

        ++end;
        for ( p = start; p != end; ++p )
        {
                tmp = *p;
                for ( q = p; ( q != start ) && ( tmp < *(q - 1) ); --q )
                {
                        *q = *(q - 1);
                }
                *q = tmp;
        }
        return;
}

void swap( int* x, int* y)
{
        int tmp = *x;
        *x = *y;
        *y = tmp;
}

/* make that *a <= *b <= *c */
void Sort3( int* a, int* b, int* c)
{
        if ( *b < *a )
        {
                swap( a, b );
        }
        if ( *c < *a )
        {
                swap( a, c );
        }
        if ( *c < *b )
        {
                swap( b, c );
        }
        return;
}

/* partition A and return the postion of pivot */
int Partition( int A[], int start, int end )
{
        int pivot;
        int i, j;
        int center = ( start + end ) / 2;

        Sort3( A + start, A + center, A + end );
        pivot = A[center];
        --end;   /* because now A[end] >= pivot */
        swap( A + center, A + end ); /* hide pivot */
        i = start;
        j = end;
        for ( ; ; )
        {
                for ( ++i; A[i] < pivot; ++i )
                {}
                for ( --j; A[j] > pivot; --j )
                {}
                if ( i < j )
                {
                        swap( A + i, A + j );
                }
                else
                {
                        break;
                }
        }
        swap( A + i, A + end ); /* restore pivot */
        return i;
}

#define  CUT_OFF  ( 10 )

void QuickSort( int A[], int n )
{
        if ( n <= 1 )
        {
                return;
        }

        int start = 0;
        int end = n - 1;
        int pos_pivot; /* position of pivot */

        typedef int StackElem;
        StackElem* stack = ( StackElem* )malloc( n * sizeof( StackElem ) );
        StackElem* top = stack;

        while ( ( start + CUT_OFF <= end ) || ( stack != top ) )
        {
                while ( start + CUT_OFF <= end )
                {
                        pos_pivot = Partition( A, start, end );
                        *top++ = pos_pivot + 1;
                        *top++ = end;
                        end = pos_pivot - 1;
                }
                InsertionSort( A + start, A + end );
                end = *--top;
                start = *--top;
        }
        InsertionSort( A + start, A + end );
        free( stack );
        return;
}

改成非递归后再改写成快速查找求第k个数也近在咫尺了

12 楼

goal00001111 [专家分：4030] 发布于 2007-05-31 07:38:00

不错,很善于观察啊!我咋就没发现呢,呵呵!

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创]我所理解的快速排序算法

回复列表（共12个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]我所理解的快速排序算法

回复列表 （共12个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共12个回复）