第三课 选择排序

引用

笔记--选择排序

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号）
• ......
• 以此类推，知道全部数据有序