常见内部排序算法之选择排序_JAVA_编程开发_程序员俱乐部

class="java">package test.aglorith;

public class SelectSort {
	
	//从小到大
	public void sort(int[] data) {
		int data_len=data.length;
		for (int i = 0; i < data_len; i++) {
			int big=0;
			for (int j=1;j<data_len-i;j++) {
				if (data[big]<data[j]) {
					big=j;
				}
			}
			int point=data_len-1-i;
			if (big!=point) {
				int temp=data[point];
				data[point]=data[big];
				data[big]=temp;
			}
			print(data);
			System.out.println("");
		}
	}
	public static void print(int[] data) {
		for(int d:data){
			System.out.print(d+",");
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{1,10,2,5,3,6,9};
		System.out.println("排序之前！");
		print(data);
		System.out.println("");
		System.out.println("开始排序！");
		new SelectSort().sort(data);
	}
}

package test.aglorith;

public class HeapSort {
	//排序入口
	public void sort(int[] data) {
		int lastIndex=data.length-1;
		for (int i = 0; i < data.length; i++) {
			buildHeap(data, lastIndex-i);
			swap(data, 0,lastIndex-i);
			print(data);
			System.out.println(i);
		}
	}
	//建堆过程
	public static void buildHeap(int[] data,int lastIndex) {
		for(int i=((lastIndex-1)/2);i>=0;i--){
			int k=i;
			while(2*k+1<lastIndex){
				int biggerIndex=2*k+1;
				//判断是否有右子节点
				if (biggerIndex<lastIndex) {
					//选择左右子节点中相对较大的
					if (data[biggerIndex]<data[biggerIndex+1]) {
						biggerIndex++;
					}
				}
				if (data[k]<data[biggerIndex]) {
					swap(data, k, biggerIndex);
					k=biggerIndex;//need？有根没有相差不多
				}else {
					break;
				}
			}
		}
	}
	//交换目标
	public static void swap(int[] data,int i,int j) {
		int temp=data[i];
		data[i]=data[j];
		data[j]=temp;
	}
	//打印
	public static void print(int[] data) {
		for(int d:data){
			System.out.print(d+",");
		}
	}
	public static void main(String[] args) {
		int[] data=new int[]{1,10,2,5,3,6,9,19,15};
		System.out.println("排序之前！");
		print(data);
		System.out.println("");
		System.out.println("开始排序！");
		long pre=System.currentTimeMillis();
		for (int i = 0; i < 30000; i++) {
			new HeapSort().sort(data);
		}
		long end=System.currentTimeMillis();
		System.out.println((end-pre)/300);
	}
}