AI时代，找源码已成为过去式，纪念我过去的十年0(回)
76天前
还有人吗2(回)
93天前会python真的可以为所欲为0(回)
573天前
这里还有人吗2(回)
758天前这里还有人吗0(回)
758天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
983天前package org.rut.util.algorithm.support; |
import org.rut.util.algorithm.SortUtil; |
/** |
* @author treeroot |
* @since 2006-2-2 |
* @version 1.0 |
*/ |
public class HeapSort implements SortUtil.Sort{ |
/* (non-Javadoc) |
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) |
*/ |
public void sort(int[] data) { |
MaxHeap h=new MaxHeap(); |
h.init(data); |
for(int i=0;i<data.length;i++) |
h.remove(); |
System.arraycopy(h.queue,1,data,0,data.length); |
} |
private static class MaxHeap{ |
|
|
void init(int[] data){ |
this.queue=new int[data.length+1]; |
for(int i=0;i<data.length;i++){ |
queue[++size]=data[i]; |
fixUp(size); |
} |
} |
|
private int size=0; |
private int[] queue; |
|
public int get() { |
return queue[1]; |
} |
public void remove() { |
SortUtil.swap(queue,1,size--); |
fixDown(1); |
} |
//fixdown |
private void fixDown(int k) { |
int j; |
while ((j = k << 1) <= size) { |
if (j < size && queue[j]<queue[j+1]) |
j++; |
if (queue[k]>queue[j]) //不用交换 |
break; |
SortUtil.swap(queue,j,k); |
k = j; |
} |
} |
private void fixUp(int k) { |
while (k > 1) { |
int j = k >> 1; |
if (queue[j]>queue[k]) |
break; |
SortUtil.swap(queue,j,k); |
k = j; |
} |
} |
} |
} |
