快速排序解决方案

2012-03-17

快速排序下面分别是两个快速排序的实现。对于第二个（红色标志部分），实在想不通为什么最外层需要一个循环。C/

快速排序
下面分别是两个快速排序的实现。对于第二个（红色标志部分），实在想不通为什么最外层需要一个循环。

C/C++ code

void _qsort( int v[], int left, int right ){    int  i, last;    void swap( int v[], int i, int j );    if  ( left >= right )    /* 若数组所包含的元素数少于两个，则什么也不做 */        return;    swap( v, left, (left + right)/2 );    /* 把分区元素移到v[0] */    last = left;    for  ( i = left+1; i <= right; i++ )    /* 分区 */        if  ( v[i] < v[left] )            swap( v, ++last, i );    swap( v, left, last );    /* 恢复分区元素 */    _qsort( v, left, last-1 );    _qsort( v, last+1, right );}

C/C++ code

//快速排序:从小到大排序 void quickSort(int v[], int left, int right){     if(left >= right)         return;          int flag = v[left], i = left, j = right;     [color=#FF0000]     while(i < j)  [/color]    //为何需要for循环呢？      {         while (j > i && v[j] > flag)               j--;         v[i++] = v[j];                         while(j > i && v[i] < flag)                 i++;         v[j--] = v[i];         v[i] = flag;            quickSort(v, left, i -1);                                   quickSort(v, i+1, right);     }}

[解决办法]
lz可以参考一下：

C/C++ code

template<typename _Ty>int quick_partition(_Ty* ptr, int begin, int end, int length/*for debug*/){    typedef _Ty type;    typedef type* ptr_type;    type pivot = ptr[end];        // compare value.    int section1 = begin-1;        // first section index.#ifdef _DEBUG    cout << "----------------------------------------------" << endl;    cout << "Pivot is = " << pivot << endl;    cout << "Before partition : ";    for (int i(0); i<length; i++) cout << ptr[i] << " ";    cout << endl;#endif    for (int idx = begin; idx<end; idx++)    {        if (ptr[idx]<=pivot)    //逆序排序，改为ptr[idx]>=pivot        {            section1++;            swap( ptr[section1], ptr[idx] );#ifdef _DEBUG            cout << "Swap : " << section1 << " " << idx << endl;#endif        }    }    swap( ptr[section1+1], ptr[end] );    #ifdef _DEBUG    cout << "After partition : ";    for (int i(0); i<length; i++)         if (i==section1+1) cout << "{" << ptr[i] << "}" << " ";        else    cout << ptr[i] << " ";    cout << endl;    cout << "----------------------------------------------" << endl;#endif    return section1+1;}template<class _Ty>void quick_sort(_Ty* ptr, int begin, int end, int length/*for debug*/){    if (begin>end)        return;    int size = sizeof(ptr)/sizeof(ptr[0]);    int pos = quick_partition(ptr, begin, end, length);    quick_sort(ptr, begin, pos-1, length);    quick_sort(ptr, pos+1, end, length);}
[解决办法]
写错了吧,那个while应该是if
[解决办法]
[code=C/C++][/code]void _qsort( int v[], int left, int right )
{
   int  i, last;
   void swap( int v[], int i, int j );
   if  ( left >= right )    /* 若数组所包含的元素数少于两个，则什么也不做 */
       return;
   swap( v, left, (left + right)/2 );    /* 把分区元素移到v[0] */
   last = left;
   for  ( i = left+1; i <= right; i++ )    /* 从v[1]开始到v[right]的每个元素逐一与分区元素比较，小于者换位，从v[1]开始，完成循环后，v[0]是分区元素，v[2]到v[last]的元素小于分区元素，而v[last+1]到v[right]都大于分区元素*/
       if  ( v[i] < v[left] ) 
 
           swap( v, ++last, i );
   swap( v, left, last );    /* 恢复分区元素 */
   _qsort( v, left, last-1 );
   _qsort( v, last+1, right );
}

[解决办法]
应该是if
[解决办法]
C/C++ code这种是最古老的快排,不要使用了.绿色高效不易出错的快排可以参考算法导论的单循环partition()函数的实现,而且它保证如果当前的数列里有与key重复的数字,则划分后,与key相同的数字全部在middle的左侧. 利用这个partition可以保证nth_element的实现是可靠的.

热点排行

C语言

快速排序解决方案