客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
1 SEED = 6; --随机序列 可任取 2 NUM = 1000; --排序规模 3 4 5 --随机序列 初始数据 6 function GenRnd( seed, n ) --生成随机数 7 data = {}; 8 local r = math.random; 9 10 math.randomseed( seed ); --不同的种子 生成不同的伪序列 11 12 for i = 1, n do 13 data[i] = r( n ); 14 end 15 16 return data; 17 end 18 19 --交换数组元素 20 function Swap( data, i, j ) 21 local tmp = data[i]; 22 data[i] = data[j]; 23 data[j] = tmp; 24 end 25 26 27 28 29 30 -- 31 --堆排示例 32 -- 33 34 --调整单个节点 35 function BuildHeap( data, dlen, idx ) 36 37 --若当前已经为叶子节点，停止循环 38 while (idx << 1) <= dlen do 39 40 --找出左右孩子中哪个大 41 idx1 = idx << 1; 42 if idx1 + 1 <= dlen and data[idx1 + 1] > data[idx1] then 43 idx1 = idx1 + 1; 44 end 45 46 --若最大的孩子比父节点小 堆调整完毕 47 if data[idx1] <= data[idx] then 48 break; 49 end 50 51 --否则交换之 52 tmp = data[idx]; 53 data[idx] = data[idx1]; 54 data[idx1] = tmp; 55 56 idx = idx1; 57 58 end 59 end 60 61 --建堆 62 function HeapSort( data ) 63 --构建初始堆 64 for i = ( #data >> 1 ), 1, -1 do 65 BuildHeap( data, #data, i ); 66 end 67 68 --开始排序 69 for i = #data, 2, -1 do 70 71 BuildHeap( data, i, 1 ); 72 73 tmp = data[1]; 74 data[1] = data[i]; 75 data[i] = tmp; 76 77 end 78 end 79 80 81 82 print("HEAP排序----------------"); 83 --生成初始数据 84 data = GenRnd( SEED, NUM ); 85 86 --打印初始数据 87 for _, v in ipairs( data ) do 88 io.write( ""..v..' ' ); 89 end 90 print( " "); 91 92 --调用 93 HeapSort( data ); 94 95 --打印 96 for _, v in ipairs( data ) do 97 io.write( ""..v..' ' ); 98 end 99 print( "" ); 100 101 102 -- 103 --堆排示例结束 104 -- 105 106 107 108 -- 109 --希尔排序示例 110 -- 111 112 --调整单个增量 113 function ShellPass( data, dt ) 114 115 for i = 1, dt do --增量为N，就有N个子序列 116 for j = i + dt, #data, dt do 117 tmp = data[j]; 118 for k = j - dt, 1, -dt do 119 if data[k] > tmp then 120 data[k + dt] = data[k]; 121 if k == i then 122 data[k] = tmp; 123 end 124 else 125 data[k + dt] = tmp; 126 break; 127 end 128 end 129 130 end 131 end 132 133 end 134 135 --SHELL排序 136 function ShellSort( data, dt ) 137 --对每个增量进行一次排序 138 for i = 1, #dt do 139 ShellPass( data, dt[i] ); 140 end 141 end 142 143 144 145 146 print("SHELL排序----------------"); 147 --生成初始数据 148 data = GenRnd( SEED, NUM ); 149 dt = {7, 5, 3, 1}; 150 151 --打印初始数据 152 for _, v in ipairs( data ) do 153 io.write( ""..v..' ' ); 154 end 155 print( "" ); 156 157 --调用 158 ShellSort( data, dt ); 159 160 --打印 161 for _, v in ipairs( data ) do 162 io.write( ""..v..' ' ); 163 end 164 print( "" ); 165 166 167 -- 168 --希尔排序示例结束 169 -- 170 171 172 173 -- 174 --快速排序示例 175 -- 176 177 178 --一次排序 确定一个位置 左边小 右边大 179 function QSPass( data, low, high ) 180 181 local tmp = data[low]; 182 183 while low < high do 184 185 while low < high and data[high] > tmp do 186 high = high - 1; 187 end 188 189 if low == high then break end 190 Swap( data, low, high ); 191 low = low + 1; 192 193 194 while low < high and data[low] <= tmp do 195 low = low + 1; 196 end 197 198 if low < high then 199 Swap( data, low, high ); 200 high = high - 1; 201 end 202 203 end 204 205 data[low] = tmp; 206 207 return low; 208 end 209 210 --快速排序 211 function QuickSort( data, low, high ) 212 if low < high then 213 pivot = QSPass( data, low, high ); 214 QuickSort( data, low, pivot - 1 ); 215 QuickSort( data, pivot + 1, high ); 216 end 217 end 218 219 220 221 222 print("快速排序----------------"); 223 --生成初始数据 224 data = GenRnd( SEED, NUM ); 225 226 --打印初始数据 227 for _, v in ipairs( data ) do 228 io.write( ""..v..' ' ); 229 end 230 print( "" ); 231 232 --调用 233 QuickSort( data, 1, #data ); 234 235 --打印 236 for _, v in ipairs( data ) do 237 io.write( ""..v..' ' ); 238 end 239 print( "" ); 240 241 242 -- 243 --快速排序示例结束 244 -- 245 246 247 248 -- 249 --归并排序示例 250 -- 251 252 253 function Merge( data, low, gap, _data ) 254 local mid = low + gap; 255 local i = low; 256 local j = mid; 257 local k = i; 258 259 if mid > #data then 260 for i = low, #data do _data[i] = data[i] end 261 return; 262 end 263 264 local high = mid + gap - 1; 265 if #data < high then high = #data end 266 267 while i < mid or j <= high do 268 if i >= mid then 269 _data[k] = data[j]; 270 j = j + 1; 271 elseif j > high or data[i] <= data[j] then 272 _data[k] = data[i]; 273 i = i + 1; 274 else 275 _data[k] = data[j]; 276 j = j + 1; 277 end 278 279 k = k + 1; 280 end 281 282 end 283 284 285 function MergeSort( data ) 286 local _data = {}; 287 local gap = 1; 288 289 while gap <= #data do 290 291 for i = 1, #data, gap << 1 do 292 Merge( data, i, gap, _data ); 293 end 294 295 for i = 1, #data do 296 data[i] = _data[i]; 297 end 298 299 gap = gap << 1; 300 end 301 end 302 303 304 305 print("归并排序----------------"); 306 --生成初始数据 307 data = GenRnd( SEED, NUM ); 308 309 --打印初始数据 310 for _, v in ipairs( data ) do 311 io.write( ""..v..' ' ); 312 end 313 print( "" ); 314 315 --调用 316 MergeSort( data ); 317 318 --打印 319 for _, v in ipairs( data ) do 320 io.write( ""..v..' ' ); 321 end 322 print( "" ); 323 324 325 -- 326 --归并排序示例结束 327 --
---------- Lua ---------- |
请发表评论