七大基本排序算法之堆排序
package Sort;
import java.io.IOException;
import Input.InputString;
public class HeapSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
String str = InputString.getString();
String[] s = str.split(" ");
int[] a = new int[s.length+1];
for(int i = 1; i<=s.length;i++){
a[i] = Integer.parseInt(s[i-1]);
}
heapSort(a);
for(int i = 1; i<a.length;i++){
System.out.print(a[i]+" ");
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public static void heapAdjust(int[] a, int begin,int end){
int temp = a[begin];
for(int i = 2*begin; i <= end; i = 2*i){
if(i < end && a[i] < a[i+1]){
i++;
}
if(temp >= a[i]){
break;
}
a[begin] = a[i];
begin = i;
}
a[begin] = temp;
}
public static void heapSort(int[] a){
for(int i = a.length/2; i > 0; i--){
heapAdjust(a, i, a.length-1);
}
for(int i = a.length-1; i > 1; i--){
int temp = a[1];
a[1] = a[i];
a[i] = temp;
heapAdjust(a, 1, i-1);
}
}
}
import java.io.IOException;
import Input.InputString;
/**
* 堆排序
* @author xiaomi
* 2012.4.1
*/
public class HeapSort {
private static int[] heap;
public static void main(String[] args) throws IOException{
String s = InputString.getString();
String[] str = s.split(" ");
heap = new int[str.length+1];//从下标1开始算起
for(int i = 0;i < str.length;i++){
heap[i+1] = Integer.parseInt(str[i]);
}
heapSort();
for(int i = 1;i < heap.length;i++){
System.out.print(heap[i]+" ");
}
}
public static void heapSort(){
createHeap();
for(int i = 1;i < heap.length;i++){
ajustHeap(i);
}
}
//每加入一个节点就要向上筛选一次
public static void createHeap(){
for(int i = 2; i < heap.length;i++){
for(int j = i; j/2>=1;j/=2){
if(heap[j]>heap[j/2]){
int temp = heap[j];
heap[j] = heap[j/2];
heap[j/2] = temp;
}
}
}
}
//每移走一个节点就要向下调整一次
public static void ajustHeap(int k){
int temp = heap[1];
heap[1] = heap[heap.length-k];
heap[heap.length-k] = temp;
int i = 1;
while((2*i) < heap.length-k){
if((2*i+1) < heap.length-k){
if(heap[i] > heap[2*i] && heap[i] > heap[2*i+1]){
break;
}
else{//与较大的一个子节点交换
if(heap[2*i] < heap[2*i+1]){
int a = heap[i];
heap[i] = heap[2*i+1];
heap[2*i+1] = a;
i = 2*i+1;
}else{
int a = heap[i];
heap[i] = heap[2*i];
heap[2*i] = a;
i = 2*i;
}
}
}else{//不存在右节点的时候
if(heap[i] > heap[2*i]){
break;
}
else{
int a = heap[i];
heap[i] = heap[2*i];
heap[2*i] = a;
i = 2*i;
}
}
}
}
}