选择排序和堆排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
---维基百科
选择排序有两个鲜明的特点：

1. 运行时间和输入无法。在一个数组中找到最小项的过程，对于下一个查找过程并不能提供很多有效的信息。
2. 数据移动是最小的。

public class SelectSort {
    
    public static void main(String [] args){
        Integer a[] = {1,9,8,3,4,5} ;
        sort(a) ;
        for(int i = 0 ; i < a.length ; i++){
            System.out.print(a[i]+", ");
        }
    }
    
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w)<0 ;
    }
    
    private static void exch(Comparable [] a, int i , int j){
        Comparable t = a[i] ;
        a[i] = a[j] ; a[j] = t ;
    }
    
    /**
     * 1. 运行时间和输入数据没有关系。本次的比较结果对下次比较并没有什么帮助<p>
     * 2. 数据移动是最少的。数据交换发生N次
     * @param a 要进行比较的数组
     */
    private static void sort(Comparable [] a){
        int N = a.length ;
        for( int i =0 ; i< N  ; i++){
            int min = i ;
            for(int j = i+1 ; j<N ; j++){
                if(less(a[j],a[min])) min = j ;
            }
            exch(a,i,min) ;
        }   
    }
}

堆排序是对选择排序的一种改进。弥补了选择排序不带有“记忆性”的缺失。
堆是具有下列性质的完全二叉树：每个结点的值大于或者等于其左右孩子节点，称为大顶堆；或者每个节点的值小于或者等于左右孩子结点的值，称为小顶堆。
根据完全二叉树性质：如果i=1，则结点i是二叉树的根，无双亲；如果i>1,其双亲是节点 ⌊i/2⌋。

public class HeapSort 
{
    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;
    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }
    
    public static void maxheap(int[] a, int i){ 
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
        
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            exchange(i,largest);
            maxheap(a, largest);
        }
    }
    
    public static void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t; 
        } 
    
    public static void sort(int []a0){
        a=a0;
        buildheap(a);  //初始化大顶堆
        for(int i=n;i>0;i--){
            exchange(0, i); //将最大数交换到最后
            n=n-1;
            maxheap(a, 0); // 建立大顶堆
        }
    }
    
    public static void main(String[] args) {
        int []a1={5,4,3,2,1};
        sort(a1);
        for(int i=0;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
    }
}

可视化过程：
http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
http://jsdo.it/norahiko/oxIy/fullscreen
http://zh.visualgo.net/zh