堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 public void heapSort(int[] a){
    if( a == null || a.length == 0) return;
    int hi = a.length - 1;
    for(int k = hi/2; k >= 0; k--){
        sink(a,k,hi);
    }
    while(hi>0){
      swap(a,0,hi);
      sink(a,0,--hi);
    }
   }
   private void sink(int[] a,int i,int hi){


    <span class="k">while</span><span class="o">(</span><span class="mi">2</span><span class="o">*</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">hi</span><span class="o">){</span>
      <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">2</span><span class="o">*</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span>
      <span class="k">if</span><span class="o">(</span> <span class="n">j</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">hi</span> <span class="o">&amp;&amp;</span> <span class="n">a</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">&lt;</span> <span class="n">a</span><span class="o">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="o">])</span> <span class="n">j</span><span class="o">++;</span>
      <span class="k">if</span><span class="o">(!</span><span class="n">less</span><span class="o">(</span><span class="n">a</span><span class="o">,</span><span class="n">i</span><span class="o">,</span><span class="n">j</span><span class="o">))</span> <span class="k">break</span><span class="o">;</span>
      <span class="n">swap</span><span class="o">(</span><span class="n">a</span><span class="o">,</span><span class="n">i</span><span class="o">,</span><span class="n">j</span><span class="o">);</span>
      <span class="n">i</span> <span class="o">=</span> <span class="n">j</span><span class="o">;</span>
    <span class="o">}</span>


   }