lua堆排

 1 math.randomseed( 1 );          --固定序列 便于调试 可改为os.time()
 2 
 3 function GenRnd( n )           --生成随机数
 4     data = {};
 5     r = math.random;
 6     for i = 1, n do
 7         data[i] = r( n );
 8     end
 9     return data;
10 end
11 
12 --调用
13 data = GenRnd( 30 );
14 
15 --打印
16 for i, v in ipairs(data) do
17     io.write(""..v..‘ ‘);
18 end
19 print("");
20 
21 
22 --[[
23     堆排示例
24 --]]
25 
26 --调整单个节点
27 function BuildHeap( data, dlen, idx )
28 
29     --若当前已经为叶子节点，停止循环
30     while (idx << 1) <= dlen do
31 
32         --找出左右孩子中哪个大
33         idx1 = idx << 1;
34         if idx1 + 1 <= dlen and data[idx1 + 1] > data[idx1] then
35             idx1 = idx1 + 1;
36         end
37 
38         --若最大的孩子比父节点小 堆调整完毕
39         if data[idx1] <= data[idx] then
40             break;
41         end
42 
43         --否则交换之
44         tmp = data[idx];
45         data[idx] = data[idx1];
46         data[idx1] = tmp;
47 
48         idx = idx1;
49 
50     end
51 end
52 
53 --建堆
54 function HeapSort( data )
55     --构建初始堆
56     for i = ( #data >> 1 ), 1, -1 do
57         BuildHeap( data, #data, i );
58     end
59 
60     --开始排序
61     for i = #data, 2, -1 do
62         
63         BuildHeap( data, i, 1 );
64 
65         tmp = data[1];
66         data[1] = data[i];
67         data[i] = tmp;
68 
69     end
70 end
71 
72 
73 
74 
75 --调用
76 HeapSort( data );
77 
78 --打印
79 for i, v in ipairs(data) do
80     io.write(""..v..‘ ‘);
81 end
82 print("");