iqsort_8h-source.html
来自「最新版本！fastdb是高效的内存数据库系统」· HTML 代码 · 共 286 行
HTML
286 行
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>iqsort.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.2.18 -->
<center>
<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Compound Members</a> </center>
<hr><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> < <span class="keyword">class</span> e_type >
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 > 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) > *(first))) {
00025 middle = first;
00026 }
00027 }
00028 <span class="keywordflow">if</span> ((*(array) > *(middle))) {
00029 ((void) ((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) > *(array))) {
00035 middle = array;
00036 temp = *middle;
00037 <span class="keywordflow">do</span> {
00038 *middle-- = *first--;
00039 } <span class="keywordflow">while</span> ((*(first) > *(&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> < <span class="keyword">class</span> e_type >
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 ((void) ((temp) = *(array), *(array) = *(array + k), *(array + k) = (temp)));
00057 <span class="keywordflow">if</span> ((*((array + 1)) > *((array)))) {
00058 (temp) = *(array + 1);
00059 <span class="keywordflow">if</span> ((*((array + n)) > *((array)))) {
00060 *(array + 1) = *(array);
00061 <span class="keywordflow">if</span> ((*(&(temp)) > *((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)) > *((array + n)))) {
00073 <span class="keywordflow">if</span> ((*((array + 1)) > *((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 ((void) (((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> < <span class="keyword">class</span> e_type >
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 > 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) > *(first)));
00112 <span class="keywordflow">do</span> {
00113 --last;
00114 } <span class="keywordflow">while</span> ((*(last) > *(array)));
00115 <span class="keywordflow">while</span> (last > first) {
00116 ((void) ((temp) = *(last), *(last) = *(first), *(first) = (temp)));
00117 <span class="keywordflow">do</span> {
00118 ++first;
00119 } <span class="keywordflow">while</span> ((*(array) > *(first)));
00120 <span class="keywordflow">do</span> {
00121 --last;
00122 } <span class="keywordflow">while</span> ((*(last) > *(array)));
00123 }
00124 ((void) ((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> < <span class="keyword">class</span> e_type >
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 > 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) > (child)) {
00150 <span class="keywordflow">if</span> ((*((array) + (child) + 1) > *((array) + (child)))) {
00151 ++(child);
00152 }
00153 <span class="keywordflow">if</span> ((*((array) + (child)) > *(&(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) && (*((array) + (child)) > *(&(temp)))) {
00163 (array)[(parent)] = (array)[(child)];
00164 (parent) = (child);
00165 }
00166 (array)[(parent)] = (temp);
00167 }
00168 } <span class="keywordflow">while</span> (i--);
00169 ((void) ((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) > (child)) {
00176 <span class="keywordflow">if</span> ((*((array) + (child) + 1) > *((array) + (child)))) {
00177 ++(child);
00178 }
00179 <span class="keywordflow">if</span> ((*((array) + (child)) > *(&(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) && (*((array) + (child)) > *(&(temp)))) {
00189 (array)[(parent)] = (array)[(child)];
00190 (parent) = (child);
00191 }
00192 (array)[(parent)] = (temp);
00193 }
00194 ((void) ((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> < <span class="keyword">class</span> e_type >
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) > *(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> < <span class="keyword">class</span> e_type >
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) > *(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> < <span class="keyword">class</span> e_type >
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 > array; ++array) {
00241 ((void) ((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> < <span class="keyword">class</span> e_type >
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 > 1 && !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><address style="align: right;"><small>Generated on Thu Feb 14 12:42:30 2008 for FastDB by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0
width=110 height=53></a>1.2.18 </small></address>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?