七大基本排序算法之堆排序

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;
				}
			}	
		}
	}
}

 

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);
		}	
	}
}

 

七大基本排序算法之冒泡排序

七大基本排序算法之选择排序

七大基本排序算法之插入排序

七大基本排序算法之希尔排序

七大基本排序算法之堆排序

七大基本排序算法之快速排序

七大基本排序算法之归并排序

评论

2 楼 xiaomijsj 2012-04-07  

xiaocanxccc 写道

哈哈，不错啊。都自己实现了一遍。

最近看了一些，都是些基本的东西

1 楼 xiaocanxccc 2012-04-06  

哈哈，不错啊。都自己实现了一遍。