SGI STL中的list::sort是快速排序算法吧？

dzbjet

re
只是把快速排序的递归算法改成非递归的了。是吧？

[ 本帖最后由 dzbjet 于 2006-8-12 20:03 编辑 ]

dzbjet

看了一下代码，好巧妙~
确实是快速排序算法，而且是非递归实现，主要思想是.......懒得写了
我仿照写了一个验证思路的：

1. 
   
2. #include <iostream>
   
3. #include <math.h>
   
4. 
   
5. using namespace std;
   
6. 
   
7. void qsort(int array[], size_t size)
   
8. {
   
9.         // 3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, 3^7, 3^8, 3^9; for convenience, counter[0] not used.
   
10.         list<int> counter[10];
    
11.         int index = 0;
    
12.         while( index < size )
    
13.         {
    
14.                 int v = array[index];
    
15. 
    
16.                 int i = 1;
    
17.                 list<int> temp; temp.push_back(v);
    
18.                 counter[i].merge(temp);
    
19. 
    
20. 
    
21.                 if( counter[i].size() % 3 == 0 && counter[i].size() / 3 == i )
    
22.                 {
    
23.                         // need to up to the next level
    
24.                         int j = i + 1;
    
25.                         do {
    
26.                                 counter[j].merge(counter[j-1]);
    
27.                         } while ( counter[j].size() > pow(3,j++) );
    
28.                 }
    
29.                 ++index;
    
30.         }
    
31. 
    
32.         for( int k = 1; k < 10; ++k )
    
33.         {
    
34.                 counter[k].merge(counter[k-1]);
    
35.         }
    
36. 
    
37.         copy(counter[k-1].begin(), counter[k-1].end(), ostream_iterator<int>(cout, " "));
    
38. }
    
39. 
    
40. 
    
41. int main(int argc, char* argv[])
    
42. {
    
43.         int array[] = { 1, 5, 8, 3, 2, 9, 4, 41, 32, 0, 7, 6, 37};
    
44. 
    
45.         qsort(array, sizeof(array)/sizeof(array[0]));
    
46.        
    
47.     return 0;
    
48. }
    

复制代码

[ 本帖最后由 dzbjet 于 2006-8-13 13:53 编辑 ]

phoneix

template< typename T, typename Allocator >
void list<T, Allocator>::sort()
{
    if( empty() || m_header->next->next == m_header )
        return;

    self result[ 64 ];
    self carry;
    size_type fill = 0;

    while( !empty() )
    {
        carry.splice( carry.begin(), *this, begin() );
        size_type i = 0;
        while( (i < fill) && (!result[i].empty()) )
        {
            result[i].merge( carry );
            carry.swap( result[i] );
            ++i;
        }
        carry.swap( result[i] );
        if( i == fill )
            ++fill;
    }

    for( size_type j = 1; j < fill; ++j )
        result[j].merge( result[j - 1] );

    swap( result[fill - 1] );
}

dzbjet

请不要贴STL的代码，这个网上可以找到，你贴在这里，有什么意义吗？