📄 iqsort_8h-source.html

📁 FastDb是高效的内存数据库系统
💻 HTML
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>FastDB: iqsort.h Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><div class="qindex"><a class="qindex" href="index.html">Main&nbsp;Page</a> | <a class="qindex" href="hierarchy.html">Class&nbsp;Hierarchy</a> | <a class="qindex" href="annotated.html">Class&nbsp;List</a> | <a class="qindex" href="files.html">File&nbsp;List</a> | <a class="qindex" href="functions.html">Class&nbsp;Members</a></div><h1>iqsort.h</h1><div class="fragment"><pre>00001 <span class="comment">/*</span>00002 <span class="comment">** Sorting stuff by Dann Corbit and Pete Filandr.</span>00003 <span class="comment">** (dcorbit@connx.com and pfilandr@mindspring.com)</span>00004 <span class="comment">** Use it however you like.</span>00005 <span class="comment">*/</span>00006 00007 <span class="comment">//</span>00008 <span class="comment">//  The insertion sort template is used for small partitions.</span>00009 <span class="comment">//  Insertion sort is stable.</span>00010 <span class="comment">//</span>00011 00012 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00013 <span class="keywordtype">void</span> insertion_sort(e_type * array, size_t nmemb)00014 {00015     e_type temp,00016           *last,00017           *first,00018           *middle;00019     <span class="keywordflow">if</span> (nmemb &gt; 1) {00020         first = middle = 1 + array;00021         last = nmemb - 1 + array;00022         <span class="keywordflow">while</span> (first != last) {00023             ++first;00024             <span class="keywordflow">if</span> ((*(middle) &gt; *(first))) {00025                 middle = first;00026             }00027         }00028         <span class="keywordflow">if</span> ((*(array) &gt; *(middle))) {00029             ((<span class="keywordtype">void</span>) ((temp) = *(array), *(array) = *(middle), *(middle) = (temp)));00030         }00031         ++array;00032         <span class="keywordflow">while</span> (array != last) {00033             first = array++;00034             <span class="keywordflow">if</span> ((*(first) &gt; *(array))) {00035                 middle = array;00036                 temp = *middle;00037                 <span class="keywordflow">do</span> {00038                     *middle-- = *first--;00039                 } <span class="keywordflow">while</span> ((*(first) &gt; *(&amp;temp)));00040                 *middle = temp;00041             }00042         }00043     }00044 }00045 00046 <span class="comment">//</span>00047 <span class="comment">// The median estimate is used to choose pivots for the quicksort algorithm</span>00048 <span class="comment">//</span>00049 00050 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00051 <span class="keywordtype">void</span> median_estimate(e_type * array, size_t n)00052 {00053     e_type          temp;00054     <span class="keywordtype">long</span> <span class="keywordtype">unsigned</span>   lu_seed = 123456789LU;00055     <span class="keyword">const</span> size_t    k = ((lu_seed) = 69069 * (lu_seed) + 362437) % --n;00056     ((<span class="keywordtype">void</span>) ((temp) = *(array), *(array) = *(array + k), *(array + k) = (temp)));00057     <span class="keywordflow">if</span> ((*((array + 1)) &gt; *((array)))) {00058         (temp) = *(array + 1);00059         <span class="keywordflow">if</span> ((*((array + n)) &gt; *((array)))) {00060             *(array + 1) = *(array);00061             <span class="keywordflow">if</span> ((*(&amp;(temp)) &gt; *((array + n)))) {00062                 *(array) = *(array + n);00063                 *(array + n) = (temp);00064             } <span class="keywordflow">else</span> {00065                 *(array) = (temp);00066             }00067         } <span class="keywordflow">else</span> {00068             *(array + 1) = *(array + n);00069             *(array + n) = (temp);00070         }00071     } <span class="keywordflow">else</span> {00072         <span class="keywordflow">if</span> ((*((array)) &gt; *((array + n)))) {00073             <span class="keywordflow">if</span> ((*((array + 1)) &gt; *((array + n)))) {00074                 (temp) = *(array + 1);00075                 *(array + 1) = *(array + n);00076                 *(array + n) = *(array);00077                 *(array) = (temp);00078             } <span class="keywordflow">else</span> {00079                 ((<span class="keywordtype">void</span>) (((temp)) = *((array)), *((array)) = *((array + n)), *((array + n)) = ((temp))));00080             }00081         }00082     }00083 }00084 00085 00086 <span class="comment">//</span>00087 <span class="comment">// This is the heart of the quick sort algorithm used here.</span>00088 <span class="comment">// If the sort is going quadratic, we switch to heap sort.</span>00089 <span class="comment">// If the partition is small, we switch to insertion sort.</span>00090 <span class="comment">//</span>00091 00092 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00093 <span class="keywordtype">void</span> qloop(e_type * array, size_t nmemb, size_t d)00094 {00095     e_type temp,00096           *first,00097           *last;00098     <span class="keywordflow">while</span> (nmemb &gt; 50) {00099         <span class="keywordflow">if</span> (sorted(array, nmemb)) {00100             <span class="keywordflow">return</span>;00101         }00102         <span class="keywordflow">if</span> (!d--) {00103             heapsort(array, nmemb);00104             <span class="keywordflow">return</span>;00105         }00106         median_estimate(array, nmemb);00107         first = 1 + array;00108         last = nmemb - 1 + array;00109         <span class="keywordflow">do</span> {00110             ++first;00111         } <span class="keywordflow">while</span> ((*(array) &gt; *(first)));00112         <span class="keywordflow">do</span> {00113             --last;00114         } <span class="keywordflow">while</span> ((*(last) &gt; *(array)));00115         <span class="keywordflow">while</span> (last &gt; first) {00116             ((<span class="keywordtype">void</span>) ((temp) = *(last), *(last) = *(first), *(first) = (temp)));00117             <span class="keywordflow">do</span> {00118                 ++first;00119             } <span class="keywordflow">while</span> ((*(array) &gt; *(first)));00120             <span class="keywordflow">do</span> {00121                 --last;00122             } <span class="keywordflow">while</span> ((*(last) &gt; *(array)));00123         }00124         ((<span class="keywordtype">void</span>) ((temp) = *(array), *(array) = *(last), *(last) = (temp)));00125         qloop(last + 1, nmemb - 1 + array - last, d);00126         nmemb = last - array;00127     }00128     insertion_sort(array, nmemb);00129 }00130 00131 <span class="comment">//</span>00132 <span class="comment">// This heap sort is better than average because it uses Lamont's heap.</span>00133 <span class="comment">//</span>00134 00135 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00136 <span class="keywordtype">void</span> heapsort(e_type * array, size_t nmemb)00137 {00138     size_t i,00139            child,00140            parent;00141     e_type temp;00142     <span class="keywordflow">if</span> (nmemb &gt; 1) {00143         i = --nmemb / 2;00144         <span class="keywordflow">do</span> {00145             {00146                 (parent) = (i);00147                 (temp) = (array)[(parent)];00148                 (child) = (parent) * 2;00149                 <span class="keywordflow">while</span> ((nmemb) &gt; (child)) {00150                     <span class="keywordflow">if</span> ((*((array) + (child) + 1) &gt; *((array) + (child)))) {00151                         ++(child);00152                     }00153                     <span class="keywordflow">if</span> ((*((array) + (child)) &gt; *(&amp;(temp)))) {00154                         (array)[(parent)] = (array)[(child)];00155                         (parent) = (child);00156                         (child) *= 2;00157                     } <span class="keywordflow">else</span> {00158                         --(child);00159                         <span class="keywordflow">break</span>;00160                     }00161                 }00162                 <span class="keywordflow">if</span> ((nmemb) == (child) &amp;&amp; (*((array) + (child)) &gt; *(&amp;(temp)))) {00163                     (array)[(parent)] = (array)[(child)];00164                     (parent) = (child);00165                 }00166                 (array)[(parent)] = (temp);00167             }00168         } <span class="keywordflow">while</span> (i--);00169         ((<span class="keywordtype">void</span>) ((temp) = *(array), *(array) = *(array + nmemb), *(array + nmemb) = (temp)));00170         <span class="keywordflow">for</span> (--nmemb; nmemb; --nmemb) {00171             {00172                 (parent) = (0);00173                 (temp) = (array)[(parent)];00174                 (child) = (parent) * 2;00175                 <span class="keywordflow">while</span> ((nmemb) &gt; (child)) {00176                     <span class="keywordflow">if</span> ((*((array) + (child) + 1) &gt; *((array) + (child)))) {00177                         ++(child);00178                     }00179                     <span class="keywordflow">if</span> ((*((array) + (child)) &gt; *(&amp;(temp)))) {00180                         (array)[(parent)] = (array)[(child)];00181                         (parent) = (child);00182                         (child) *= 2;00183                     } <span class="keywordflow">else</span> {00184                         --(child);00185                         <span class="keywordflow">break</span>;00186                     }00187                 }00188                 <span class="keywordflow">if</span> ((nmemb) == (child) &amp;&amp; (*((array) + (child)) &gt; *(&amp;(temp)))) {00189                     (array)[(parent)] = (array)[(child)];00190                     (parent) = (child);00191                 }00192                 (array)[(parent)] = (temp);00193             }00194             ((<span class="keywordtype">void</span>) ((temp) = *(array), *(array) = *(array + nmemb), *(array + nmemb) = (temp)));00195         }00196     }00197 }00198 00199 <span class="comment">// </span>00200 <span class="comment">// We use this to check to see if a partition is already sorted.</span>00201 <span class="comment">// </span>00202 00203 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00204 <span class="keywordtype">int</span> sorted(e_type * array, size_t nmemb)00205 {00206     <span class="keywordflow">for</span> (--nmemb; nmemb; --nmemb) {00207         <span class="keywordflow">if</span> ((*(array) &gt; *(array + 1))) {00208             <span class="keywordflow">return</span> 0;00209         }00210         ++array;00211     }00212     <span class="keywordflow">return</span> 1;00213 }00214 00215 <span class="comment">// </span>00216 <span class="comment">// We use this to check to see if a partition is already reverse-sorted.</span>00217 <span class="comment">// </span>00218 00219 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00220 <span class="keywordtype">int</span>             rev_sorted(e_type * array, size_t nmemb)00221 {00222     <span class="keywordflow">for</span> (--nmemb; nmemb; --nmemb) {00223         <span class="keywordflow">if</span> ((*(array + 1) &gt; *(array))) {00224             <span class="keywordflow">return</span> 0;00225         }00226         ++array;00227     }00228     <span class="keywordflow">return</span> 1;00229 }00230 00231 <span class="comment">// </span>00232 <span class="comment">// We use this to reverse a reverse-sorted partition.</span>00233 <span class="comment">// </span>00234 00235 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00236 <span class="keywordtype">void</span> rev_array(e_type * array, size_t nmemb)00237 {00238     e_type          temp,00239         *end;00240     <span class="keywordflow">for</span> (end = array + nmemb - 1; end &gt; array; ++array) {00241         ((<span class="keywordtype">void</span>) ((temp) = *(array), *(array) = *(end), *(end) = (temp)));00242         --end;00243     }00244 }00245 00246 <span class="comment">// </span>00247 <span class="comment">// Introspective quick sort algorithm user entry point.</span>00248 <span class="comment">// You do not need to directly call any other sorting template.</span>00249 <span class="comment">// This sort will perform very well under all circumstances.</span>00250 <span class="comment">// </span>00251 00252 <span class="keyword">template</span> &lt; <span class="keyword">class</span> e_type &gt;00253 <span class="keywordtype">void</span> iqsort(e_type * array, size_t nmemb)00254 {00255     size_t d,00256            n;00257     <span class="keywordflow">if</span> (nmemb &gt; 1 &amp;&amp; !sorted(array, nmemb)) {00258         <span class="keywordflow">if</span> (!rev_sorted(array, nmemb)) {00259             n = nmemb / 4;00260             d = 2;00261             <span class="keywordflow">while</span> (n) {00262                 ++d;00263                 n /= 2;00264             }00265             qloop(array, nmemb, 2 * d);00266         } <span class="keywordflow">else</span> {00267             rev_array(array, nmemb);00268         }00269     }00270 }00271 </pre></div><hr size="1"><address style="align: right;"><small>Generated on Thu Feb 12 13:04:48 2004 for FastDB by<a href="http://www.doxygen.org/index.html"><img src="doxygen.png" alt="doxygen" align="middle" border=0 > </a>1.3.5 </small></address></body></html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -