【转】第三课 选择排序

1.选择排序类

package com.flysnow.chap03;   
  
/**  
 * 选择排序  
 * @author 飞雪无情  
 * @since:2010-3-25  
 */  
public class ArraySel {   
    private long[] a;   
    private int nElems;   
    public ArraySel(int max){   
        a=new long[max];   
        nElems=0;   
    }   
    /**  
     * 插入元素  
     * @param value  
     */  
    public void insert(long value){   
        a[nElems]=value;   
        nElems++;   
    }   
    /**  
     * 打印元素  
     */  
    public void display(){   
        for(int i=0;i<nElems;i++){   
            System.out.print(a[i]+" ");   
        }   
        System.out.println();   
    }   
    /**  
     * 选择排序  
     */  
    public void selectionSort(){//性能交换O(N) 比较 O(N^2)   
        int out,min,in;   
        for(out=0;out<nElems-1;out++){   
            min=out;//默认第一个最小   
            for(in=out+1;in<nElems;in++){   
                if(a[in]<a[min]){   
                    min=in;   
                }   
            }   
            swap(out, min);   
        }   
    }   
    /**  
     * 交换  
     * @param one 数组索引  
     * @param two 数组索引  
     */  
    private void swap(int one, int two) {   
        long temp=a[one];   
        a[one]=a[two];   
        a[two]=temp;   
    }   
} 

2.选择排序测试

package com.flysnow.chap03;

import java.util.Random;

/**
 * 选择排序测试
 * @author 飞雪无情
 * @since:2010-3-25
 */
public class SelectSortApp {
	public static void main(String[] args){
		ArraySel sel=new ArraySel(100);
		Random random=new Random();
		for(int i=0;i<10;i++){//添加10个随机数
			sel.insert((long)(random.nextFloat()*100));
		}
		sel.display();//未排序
		sel.selectionSort();//排序
		sel.display();//排序后
	}
}

3.总结
算法思想：

把所有数据扫描一遍，找出最小的数据，把他放在第一个位置（0号）
从第二个数据开始，扫描数据，找出最小的数据，把他放在第二个位置（1号）
从第三个数据开始，扫描数据，找出最小的数据，把他放在第三个位置（2号）
......
以此类推，知道全部数据有序