选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
---维基百科
选择排序有两个鲜明的特点：
- 运行时间和输入无法。在一个数组中找到最小项的过程，对于下一个查找过程并不能提供很多有效的信息。
- 数据移动是最小的。
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
