20130504-堆排序

wiki中的算法，改用了list做

package com.lee.sort;

import java.util.ArrayList;
import java.util.List;

public class HeapSort2List2 {
	
	
	private static List<Integer> sort = new ArrayList<Integer>();

	public static void main(String[] args) {
		
		sort.add(3);
		sort.add(1);
		sort.add(4);
		sort.add(10);
		sort.add(5);
		sort.add(9);
		sort.add(4);
		sort.add(8);
		sort.add(2);
		sort.add(11);
		sort.add(0);
		sort.add(15);
		
		
		buildMaxHeapify(sort);
		heapSort(sort);
		print(sort);
		//printArr(sort);
	}

	private static void print(List<Integer> sort) {
		System.out.println();
		for(int s : sort){
			System.out.print(s + "  ");
		}
		
	}

	private static void buildMaxHeapify(List<Integer> data) {
		int len = data.size();
		// 没有子节点的才需要创建最大堆，从最后一个的父节点开始
		int startIndex = getParentIndex(len - 1);
		// 从尾端开始创建最大堆，每次都是正确的堆
		for (int i = startIndex; i >= 0; i--) {
			maxHeapify(data, len, i);
			
		}
	}

	/**
	 * 创建最大堆
	 * 
	 * @param data
	 * @param heapSize
	 *            需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
	 * @param index
	 *            当前需要创建最大堆的位置
	 */
	private static void maxHeapify(List<Integer> data, int heapSize, int index) {
		// 当前点与左右子节点比较
		int left = getChildLeftIndex(index);
		int right = getChildRightIndex(index);

		int largest = index;
		if (left < heapSize && data.get(index) < data.get(left)) {
			largest = left;
		}
		if (right < heapSize && data.get(largest) < data.get(right)) {
			largest = right;
		}
		// 得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
		if (largest != index) {
			swap(data, index, largest);
			maxHeapify(data, heapSize, largest);
		}
		
	}
	
	private static void swap(List<Integer> list, int one, int two) {
		list.set(one, list.get(one) ^ list.get(two));
		list.set(two, list.get(one) ^ list.get(two));
		list.set(one, list.get(one) ^ list.get(two));
	}
	

	/**
	 * 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
	 * 
	 * @param data
	 */
	private static void heapSort(List<Integer> data) {
		// 末尾与头交换，交换后调整最大堆
		for (int i = data.size() - 1; i > 0; i--) {
			swap(data, 0, i);
			maxHeapify(data, i, 0);
			System.out.println();
			print(data);
		}
	}

	/**
	 * 父节点位置
	 * 
	 * @param current
	 * @return
	 */
	private static int getParentIndex(int current) {
		return (current - 1) >> 1;
	}

	/**
	 * 左子节点position 注意括号，加法优先级更高
	 * 
	 * @param current
	 * @return
	 */
	private static int getChildLeftIndex(int current) {
		return (current << 1) + 1;
	}

	/**
	 * 右子节点position
	 * 
	 * @param current
	 * @return
	 */
	private static int getChildRightIndex(int current) {
		return (current << 1) + 2;
	}

	private static void print(int[] data) {
		int pre = -2;
		for (int i = 0; i < data.length; i++) {
			if (pre < (int) getLog(i + 1)) {
				pre = (int) getLog(i + 1);
				System.out.println();
			}
			System.out.print(data[i] + " |");
		}
	}
	
	private static void printArr(int [] data){
		for(int i : data){
			System.out.print(i + " ");
		}
	}

	/**
	 * 以2为底的对数
	 * 
	 * @param param
	 * @return
	 */
	private static double getLog(double param) {
		return Math.log(param) / Math.log(2);
	}
}

输出结果
11  10  9  8  5  4  4  3  2  1  0  15  
10  8  9  3  5  4  4  0  2  1  11  15  
9  8  4  3  5  1  4  0  2  10  11  15  
8  5  4  3  2  1  4  0  9  10  11  15  
5  3  4  0  2  1  4  8  9  10  11  15  
4  3  4  0  2  1  5  8  9  10  11  15  
4  3  1  0  2  4  5  8  9  10  11  15  
3  2  1  0  4  4  5  8  9  10  11  15  
2  0  1  3  4  4  5  8  9  10  11  15  
1  0  2  3  4  4  5  8  9  10  11  15  
0  1  2  3  4  4  5  8  9  10  11  15  
0  1  2  3  4  4  5  8  9  10  11  15  

另一种方式：

package com.lee.sort;

import java.util.Date;

public class HeapSortTest {
	/*
	 * 将数组调整为小根堆，即由小到大排序
	 */
	public static int[] heap = new int[100];
	
	public static void main(String[] args) {
		for(int i = 0; i < 100; i++){
			int j = (int)(Math.random()*100);  
			heap[i] = j;
		}
		
		System.out.println(new Date());
		int temp;
		/*
		 * 创建堆（对该堆进行简单的排序）
		 */
		CreateHeap();
		int out = 0;
		for (int i = heap.length - 1; 0 < i; i--) {
			temp = heap[0];
			heap[0] = heap[i];
			heap[i] = temp;
			/*
			 * 展示每次排序后的结果
			 */
			for (int j = 0; j < heap.length; j++) {
				System.out.print(heap[j] + " ");
			}
			System.out.println();// 换行
			/*
			 * 从堆顶进行调整，使未排序堆中最大关键字到堆顶
			 */
			AdjustHeap(0, i);
			out++;
			if(out > 10){
				break;
			}
		}
		System.out.println(new Date());
	}

	/*
	 * 调整堆使其堆顶为未排序堆中最大关键字
	 */
	public static void AdjustHeap(int location, int unSortlength) {
		int temp;
		int tempLoc;
		/*
		 * 确保左右节点存在
		 */
		if ((tempLoc = (location + 1) << 1 ) < unSortlength) {
			/*
			 * 判断左右节点大小
			 */
			if (heap[tempLoc] >= heap[tempLoc - 1]) {
				/*
				 * 判断父节点与子节点的大小，若父节点小，则与大的子节点换位
				 */
				if (heap[location] < heap[tempLoc]) {
					temp = heap[location];
					heap[location] = heap[tempLoc];
					heap[tempLoc] = temp;
					/*
					 * 递归法对换位后的子节点及其子节点进行调整
					 */
					AdjustHeap(tempLoc, unSortlength);
				}
			} else {
				/*
				 * 左节点大于右节点
				 */
				if (heap[location] < heap[tempLoc - 1]) {
					temp = heap[location];
					heap[location] = heap[tempLoc - 1];
					heap[tempLoc - 1] = temp;
					/*
					 * 递归法对换位后的子节点及其子节点进行调整
					 */
					AdjustHeap(tempLoc - 1, unSortlength);
				}
			}
		}
		/*
		 * 确保左节点存在
		 */
		else if ((tempLoc = ((location + 1) << 1) - 1) < unSortlength) {
			/*
			 * 与左节点进行比较
			 */
			if (heap[location] < heap[tempLoc]) {
				/*
				 * 左子节点大于父节点，将两者进行换位
				 */
				temp = heap[location];
				heap[location] = heap[tempLoc];
				heap[tempLoc] = temp;
				AdjustHeap(tempLoc, unSortlength);
			}
		}
	}

	/*
	 * 创建堆（对该堆进行简单的排序）
	 */
	public static void CreateHeap() {
		for (int i = heap.length - 1; i >= 0; i--) {
			AdjustHeap(i, heap.length);
		}
	}
}

输出结果：

8 97 97 96 96 88 85 93 91 87 95 80 82 85 58 87 90 90 77 58 85 81 94 74 52 65 63 74 81 54 31 65 74 83 84 37 90 30 40 51 51 80 76 62 73 67 90 69 68 31 19 21 39 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 82 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 69 4 32 47 21 98 
21 97 88 96 96 82 85 93 91 87 95 80 65 85 58 87 90 90 77 58 85 81 94 74 52 39 63 74 81 54 31 65 74 83 84 37 90 30 40 51 51 80 76 62 73 67 90 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 82 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 69 4 32 47 97 98 
47 96 88 96 95 82 85 93 91 87 94 80 65 85 58 87 90 90 77 58 85 81 90 74 52 39 63 74 81 54 31 65 74 83 84 37 90 30 40 51 51 80 76 62 73 67 69 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 82 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 21 4 32 97 97 98 
32 96 88 93 95 82 85 90 91 87 94 80 65 85 58 87 84 90 77 58 85 81 90 74 52 39 63 74 81 54 31 65 74 83 82 37 90 30 40 51 51 80 76 62 73 67 69 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 62 21 4 96 97 97 98 
4 95 88 93 94 82 85 90 91 87 90 80 65 85 58 87 84 90 77 58 85 81 69 74 52 39 63 74 81 54 31 65 74 83 82 37 90 30 40 51 51 80 76 62 73 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 29 8 49 23 32 21 96 96 97 97 98 
21 94 88 93 90 82 85 90 91 87 81 80 65 85 58 87 84 90 77 58 85 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 90 30 40 51 51 80 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 82 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 49 23 32 95 96 96 97 97 98 
32 93 88 91 90 82 85 90 90 87 81 80 65 85 58 87 84 90 77 58 85 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 82 30 40 51 51 80 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 49 23 94 95 96 96 97 97 98 
23 91 88 90 90 82 85 90 90 87 81 80 65 85 58 87 84 82 77 58 85 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 32 30 40 51 51 80 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 49 93 94 95 96 96 97 97 98 
49 90 88 90 87 82 85 90 90 85 81 80 65 85 58 87 84 82 77 58 80 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 32 30 40 51 51 23 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 8 91 93 94 95 96 96 97 97 98 
8 90 88 90 87 82 85 90 82 85 81 80 65 85 58 87 84 49 77 58 80 73 69 74 52 39 63 74 81 54 31 65 74 83 82 37 32 30 40 51 51 23 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 58 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 4 90 91 93 94 95 96 96 97 97 98 
4 90 88 90 87 82 85 87 82 85 81 80 65 85 58 74 84 49 77 58 80 73 69 74 52 39 63 74 81 54 31 65 58 83 82 37 32 30 40 51 51 23 76 62 29 67 62 69 68 31 19 21 8 13 42 48 47 22 64 2 45 0 16 15 20 23 8 2 71 34 47 1 9 21 32 27 4 13 30 37 47 51 29 7 10 63 46 60 5 90 90 91 93 94 95 96 96 97 97 98 

另一种可以选择升序降序的方式

package com.lee.sort;


public class HeapSort2  {

	public static void main(String[] args) {
		HeapSort2 heapSort = new HeapSort2();
		int[] A = new int[] { 1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12,
				17, 34, 11 };
		boolean isInc = false;
		heapSort.sort(A, isInc);
		printIntArray(A);
	}
	
	 private static void printIntArray(int[] A){
		 for(int a : A){
			 System.out.print(a + "   ");
		 }
     }
	
    private IntArray A = null;

    public HeapSort2() {
        A = new IntArray();
    }

    private class IntArray {
        public int[] aArray = null;
        public int heapSize = 0;
    }

    public void sort(int[] A) {
        maxHeapSort(A);
    }

    public void sort(int[] A, boolean isInc) {
        if (isInc) {
            maxHeapSort(A);
        } else {
            minHeapSort(A);
        }
    }

    /**
     * 最大堆排序，升序
     * 
     * @param A
     *            int数组
     */
    private void maxHeapSort(int[] A) {
        this.A.aArray = A;
        this.A.heapSize = A.length;
        buildMaxHeap(this.A);
        for (int i = A.length; i >= 2; i--) {
            exchange(1, i);
            this.A.heapSize = this.A.heapSize - 1;
            maxHeapify(this.A, 1);
        }
    }

    /**
     * 最小堆排序，降序
     * 
     * @param A
     *            int数组
     */
    private void minHeapSort(int[] A) {
        this.A.aArray = A;
        this.A.heapSize = A.length;
        buildMinHeap(this.A);
        for (int i = A.length; i >= 2; i--) {
            exchange(1, i);
            this.A.heapSize = this.A.heapSize - 1;
            minHeapify(this.A, 1);
        }
    }

    /**
     * 使得以index为根的子树成为最大堆
     * 
     * @param A
     *            int数组
     * @param index
     *            以index为根，从1开始
     */
    private void maxHeapify(IntArray A, int index) {
        while (index < A.heapSize / 2 + 1) {
            int left = left(index);
            int right = right(index);
            int largest = 0;
            if (left <= A.heapSize && A.aArray[left - 1] > A.aArray[index - 1]) {
                largest = left;
            } else {
                largest = index;
            }
            if (right <= A.heapSize
                    && A.aArray[right - 1] > A.aArray[largest - 1]) {
                largest = right;
            }
            if (index != largest) {
                exchange(index, largest);
                index = largest;
            } else {
                index = A.heapSize / 2 + 1;
            }
        }
    }

    /**
     * 使得以index为根的子树成为最小堆
     * 
     * @param A
     *            int数组
     * @param index
     *            以index为根，从1开始
     */
    private void minHeapify(IntArray A, int index) {
        while (index < A.heapSize / 2 + 1) {
            int left = left(index);
            int right = right(index);
            int smallest = 0;
            if (left <= A.heapSize && A.aArray[left - 1] < A.aArray[index - 1]) {
                smallest = left;
            } else {
                smallest = index;
            }
            if (right <= A.heapSize
                    && A.aArray[right - 1] < A.aArray[smallest - 1]) {
                smallest = right;
            }
            if (index != smallest) {
                exchange(index, smallest);
                index = smallest;
            } else {
                index = A.heapSize / 2 + 1;
            }
        }
    }

    /**
     * 建最大堆
     * 
     * @param A
     *            int数组
     */
    private void buildMaxHeap(IntArray A) {
        for (int i = A.aArray.length / 2; i >= 1; i--) {
            maxHeapify(A, i);
        }
    }

    /**
     * 建最小堆
     * 
     * @param A
     *            int数组
     */
    private void buildMinHeap(IntArray A) {
        for (int i = A.aArray.length / 2; i >= 1; i--) {
            minHeapify(A, i);
        }
    }

    private int left(int index) {
        return 2 * index;
    }

    private int right(int index) {
        return 2 * index + 1;
    }

    private void exchange(int i, int j) {
        int temp = A.aArray[i - 1];
        A.aArray[i - 1] = A.aArray[j - 1];
        A.aArray[j - 1] = temp;
    }

}