我的Ｃ语言快速排序方法

0hudu

// test0.cpp : 定义控制台应用程序的入口点。 //此教程来源于ChinaUnix論壇（http://bbs.chinaunix.net/） //查看完整的教程请点：http://bbs.chinaunix.net/thread-1296108-1-1.html #include "stdafx.h" #include <stdlib.h> #include <time.h> #include <iostream> #include <algorithm> #include <iterator> //随机选取中间数 template<typename T> int select(T data[], int low, int high) { int middle=low+rand()%(high-low); std::swap(data[middle], data[low]); int i=low+1; int j=high; while ( i<=j ) { &nbsp;&nbsp;while ( data[i]<data[low] ) &nbsp;&nbsp;&nbsp;++i; &nbsp;&nbsp;while ( data[low]<data[j] ) &nbsp;&nbsp;&nbsp;--j; &nbsp;&nbsp;if (i<j) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;std::swap(data[i], data[j]); &nbsp;&nbsp;&nbsp;++i; &nbsp;&nbsp;&nbsp;--j; &nbsp;&nbsp;} &nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;++i; } std::swap(data[low], data[j]); return j; } //快速排序函数 template <typename T> void QuickSorter (T data[], int low, int high) { if ( low<high ) { &nbsp;&nbsp;int n=select(data, low, high); &nbsp;&nbsp;QuickSorter(data, low, n-1); &nbsp;&nbsp;QuickSorter(data, n+1, high); } } //快速排序包装器 template <typename T> void QuickSort(T data[], int size) { srand(time(NULL)); QuickSorter(data, 0, size-1); } //测试例程 int _tmain(int argc, _TCHAR* argv[]) { int data[10000]; for ( int i=0; i<10000; ++i ) { &nbsp;&nbsp;data[i]=rand()%1000; } QuickSort(data, 10000); std::copy(data, data+10000, std::ostream_iterator<int>(std::cout, " ")); return 0; }

[ 本帖最后由 langue 于 2008-10-25 08:02 编辑 ]

gawk

cxx吧，不是c语言

ztz0223

顶了再说

lgfang

我抄来的c++快速排序方法(stl_algo.h):

1. 
   
2.   template<typename _RandomAccessIter>
   
3.     inline void
   
4.     sort(_RandomAccessIter __first, _RandomAccessIter __last)
   
5.     {
   
6.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
   
7. 
   
8.       // concept requirements
   
9.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
   
10.             _RandomAccessIter>)
    
11.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
    
12. 
    
13.       if (__first != __last) {
    
14.         __introsort_loop(__first, __last, __lg(__last - __first) * 2);
    
15.         __final_insertion_sort(__first, __last);
    
16.       }
    
17.     }
    
18. 
    
19.   template<typename _RandomAccessIter, typename _Size>
    
20.     void
    
21.     __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
    
22.                      _Size __depth_limit)
    
23.     {
    
24.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
    
25. 
    
26.       while (__last - __first > _M_threshold) {
    
27.         if (__depth_limit == 0) {
    
28.           partial_sort(__first, __last, __last);
    
29.           return;
    
30.         }
    
31.         --__depth_limit;
    
32.         _RandomAccessIter __cut =
    
33.           __unguarded_partition(__first, __last,
    
34.                                 _ValueType(__median(*__first,
    
35.                                                     *(__first + (__last - __first)/2),
    
36.                                                     *(__last - 1))));
    
37.         __introsort_loop(__cut, __last, __depth_limit);
    
38.         __last = __cut;
    
39.       }
    
40.     }
    
41. 
    
42.   template<typename _RandomAccessIter>
    
43.     void
    
44.     __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
    
45.     {
    
46.       if (__last - __first > _M_threshold) {
    
47.         __insertion_sort(__first, __first + _M_threshold);
    
48.         __unguarded_insertion_sort(__first + _M_threshold, __last);
    
49.       }
    
50.       else
    
51.         __insertion_sort(__first, __last);
    
52.     }
    
53. 
    
54.   template<typename _RandomAccessIter>
    
55.     void
    
56.     partial_sort(_RandomAccessIter __first,
    
57.                  _RandomAccessIter __middle,
    
58.                  _RandomAccessIter __last)
    
59.     {
    
60.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
    
61. 
    
62.       // concept requirements
    
63.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
    
64.             _RandomAccessIter>)
    
65.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
    
66. 
    
67.       make_heap(__first, __middle);
    
68.       for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
    
69.         if (*__i < *__first)
    
70.           __pop_heap(__first, __middle, __i, _ValueType(*__i));
    
71.       sort_heap(__first, __middle);
    
72.     }
    
73. 
    
74.   template<typename _RandomAccessIter, typename _Tp>
    
75.     _RandomAccessIter
    
76.     __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
    
77.                           _Tp __pivot)
    
78.     {
    
79.       while (true) {
    
80.         while (*__first < __pivot)
    
81.           ++__first;
    
82.         --__last;
    
83.         while (__pivot < *__last)
    
84.           --__last;
    
85.         if (!(__first < __last))
    
86.           return __first;
    
87.         iter_swap(__first, __last);
    
88.         ++__first;
    
89.       }
    
90.     }
    

复制代码

[ 本帖最后由 lgfang 于 2008-10-27 15:30 编辑 ]

alexhappy

连c和c++都分不清。。。。。