欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

常见内部排序算法之选择排序

程序员文章站 2024-01-25 19:03:34
...
常见内部排序算法
包括选择排序算法,交换排序算法,插入排序算法,基数算法,桶式算法还有归并算法。
其中选择排序算法又包括:简单选择排序算法堆排序
选择算法,顾名思义,就是从中选择需要的,然后再与目标地址进行交换。
简单选择排序算法:
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);
	}
}