排序算法整理

这里把以前写的排序算法分享出来,主要的排序对象设定为(整型数组):
主要有以下排序算法:冒泡排序,梳排序,堆排序,插入排序,计数排序,归并排序,快速排序,选择排序,希尔排序;

为了显示排序效果,我做了点小设计,主要是:
SortBoss负责提供排序数组,调用所有排序实现,并显示算法时间;
算法实现均实现Sort接口,(我弄了个AbstractSort做了基础的事情);

接口Sort,如下:

public interface Sort {
	/**
	 * 标记算法名称
	 * @return
	 */
	public String algorithm();
	/**
	 * 具体实现算法
	 * @param input 待排序数组
	 * @param n 对前n个数进行排序
	 */
	public void sort(int input[],int n);
}

SortBoss很简单,如下:

public class SortBoss {
	public static void main(String a[]){
		int src[]={29,10,39,10,35,8,93,8,47,53,82,91,65,12,79,35,48,32,9,12,67,30,39,40,15,8,93,8,47,5,92,94,60,14,78,3,58,3,9,12,67,40};		
//		int src[]={2,1};
		printArray(src);
		
		Sort sort=new InsertionSort();
		testSort(sort, src);
		sort=new QuickSort();
		testSort(sort, src);
		sort=new SelectionSort();
		testSort(sort, src);
		sort=new ShellSort();
		testSort(sort, src);
		sort=new MergeSort();
		testSort(sort, src);
		sort=new BubbleSort();
		testSort(sort, src);
		sort=new HeapSort();
		testSort(sort, src);
		sort=new CombSort();
		testSort(sort, src);
		sort=new CountingSort();
		testSort(sort, src);
	}
	
	public static void testSort(Sort sort,int src[]){
		int input[]=Arrays.copyOf(src, src.length);
		TestTime.start();
		sort.sort(input,input.length);
		TestTime.end();
		System.out.format("*************************\n%s,耗时%d,结果:\n", sort.algorithm(),TestTime.time());
		printArray(input);
		System.out.println("*************************");
	}
	public static void printArray(int []input){
		for (int i = 0; i < input.length; i++) {
			System.out.print(input[i]+",");
		}
		System.out.println();
	}
}

抽象AbstractSort,如下:

public abstract class AbstractSort implements Sort {
	/**
	 * 具体实现算法
	 * @param input 待排序数组
	 * @param n 对前n个数进行排序
	 */
	public abstract void doSort(int []input,int n);
	@Override
	public final void sort(int[] input,int n) {
		if (input!=null //&& input.length>1
				&& n>1 && n<=input.length) {
			doSort(input,n);
		}
	}
}

排序算法的各自实现,有点多,弄在一起了,还好以前有写注释,现在省了很多时间:

/**
 * 冒泡排序
 * @author kime
 *简单概括就是每次找到序列中最大或最小的元素排到最后面去,循环知道每个元素都处于正确位置
 */
public class BubbleSort extends AbstractSort implements Sort {
	@Override
	public String algorithm() {
		// TODO Auto-generated method stub
		return "冒泡排序";
	}
	/**
	 * 从头到尾遍历,把大的数向后移动,直到所有数满足从小到大为止
	 */
	@Override
	public void doSort(int[] input, int n) {
		int temp=0;
		while(--n>0){
			for (int i = 0; i < n; i++) {
				if (input[i]>input[i+1]) {
					temp=input[i];
					input[i]=input[i+1];
					input[i+1]=temp;
				}
			}
		}
	}
}


/**
 * 希尔排序
 * @author kime
 *该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。
 */
public class ShellSort extends AbstractSort implements Sort {
	@Override
	public String algorithm() {
		// TODO Auto-generated method stub
		return "希尔排序";
	}
	/**
	 * 每次取特定的步长,用于分组比较,
	 * 每个组内都采用插入排序进行排序(具体见InsertionSort)
	 * 直到步长为0时结束
	 * 
	 * 
	 */
	@Override
	public void doSort(int[] input, int n) {
		for (int step = n/2; step>0; step/=2) {//步长递减  
			for (int i = step; i < n; i++) {//从第step个开始判断
				//对分组进行插入排序
				if (input[i]=0 && input[j]>temp){
						input[j+step]=input[j];
						j-=step;
					}
					input[j+step]=temp;
				}				
			}
		}
	}
	
}


/**
 * 选择排序
 * @author kime
 *
 *直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完
 *
 */
public class SelectionSort extends AbstractSort implements Sort {
	@Override
	public String algorithm() {
		// TODO Auto-generated method stub
		return "选择排序";
	}
	/**
	 * 每次遍历余下的元素,取出最小值,填充到前面的位置上
	 */
	@Override
	public void doSort(int[] input, int n) {
		int temp=0;
		int index=0;//最小数的索引
		for (int i = 0; i < n; i++) {
			index=i;
			//取最小值
			for (int j = i+1; j < n; j++) {
				if(input[j]=0 && end-start>0 && end0 && input[j-1]>temp){
				input[j]=input[j-1];
				j--;
			}
			input[j]=temp;
		}
	}

}




/**
 * 堆排序
 * @author kime
 *1. 建立一个最大或最小堆
2. 用根元素与最后一个元素交换位置,将根元素从堆中移除,堆大小减小1。
3. 修复堆,回到上一步,直到堆中不剩元素。
 */
public class HeapSort extends AbstractSort implements Sort {
	@Override
	public String algorithm() {
		// TODO Auto-generated method stub
		return "堆排序";
	}

	@Override
	public void doSort(int[] input, int n) {
		createMaxHeap(input, n);
		int temp=0;
		for (int i = n-1; i>=0; i--) {
			temp=input[i];
			input[i]=input[0];
			input[0]=temp;
			
			maxHeapRemoveFixed(input, 0, i);
		}
	}
	/**
	 * 初始化堆
	 * @param input
	 * @param n 节点数
	 */
	private void createMaxHeap(int input[],int n){
		for (int i = n/2 -1; i>=0; i--) {
			maxHeapRemoveFixed(input, i, n);
		}
	}
	/**
	 * 删除根节点
	 * @param input
	 * @param n
	 */
	private void maxHeapRemove(int input[],int n){
		input[0]=input[n-1];
		maxHeapRemoveFixed(input, 0, n-1);
	}
	/**
	 * 删除节点后的 调整
	 * @param input
	 * @param i 节点
	 * @param n 总节点数目
	 */
	private void maxHeapRemoveFixed(int input[],int i,int n){
		int j=(2*i)+1;
		int temp=input[i];
		while (j=0 && i!=0 && input[i]>input[j];
				i=j,j=(i-1)/2) {
			temp=input[i];
			input[i]=input[j];
			input[j]=temp;
		}
	}
}




/**
 * 计数排序
 * @author kime
 *计数排序是一个类似于桶排序的排序算法,其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C,C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由 Harold H. Seward 提出。
 *
 *计数排序对输入的数据有附加的限制条件:
1、输入的线性表的元素属于有限偏序集S;
2、设输入的线性表的长度为n,|S|=k(表示集合S中元素的总数目为k),则k=O(n)。
在这两个条件下,计数排序的复杂性为O(n)。
 *
 */
public class CountingSort extends AbstractSort implements Sort {
	@Override
	public String algorithm() {
		// TODO Auto-generated method stub
		return "计数排序";
	}
	/**
	 * 
	 */
	@Override
	public void doSort(int[] input, int n) {
		int max=input[input.length-1];
		for (int i = input.length-2; i >=0 ; i--) {//取得最大值
			if (max 0) {
				input[z++] = i;
			}
		}
	}
}




/**
 * 梳排序
 * @author kime
 *它是冒泡排序的一种变体,就像希尔排序一样,也是利用一个间隔值来堆其进行分组,只不过希尔排序内部嵌套的是插入排序,而梳排序嵌套的是冒泡排序。
 *类似希尔排序取间隔的方法,只不过梳排序每次取间隔为n/1.3,下一次再除以1.3,知道间隔为1
 */
public class CombSort extends AbstractSort implements Sort {
	@Override
	public String algorithm() {
		// TODO Auto-generated method stub
		return "梳排序";
	}

	@Override
	public void doSort(int[] input, int n) {
		combSort2(input, n);
	}
	/**
	 * 网上的一个实现
	 * @param input
	 * @param n
	 */
	private void otherSort(int[] input, int n) {
		int swap;
		int i,step=n;
		boolean swaped=false;
		while(step>1 || swaped){
			if (step>1) {
				step=(int) (step/1.3);
			}
			swaped=false;
			for (i = 0; step+i  input[i+step]) {
					swap=input[i];
					input[i]=input[i+step];
					input[i+step]=swap;
					swaped=true;
				}
			}
		}
	}
	/**
	 * 自己的实现,改进的实现
	 * @param input
	 * @param n
	 */
	private void combSort2(int input[],int n){
		int step=(int) (n/1.3);
		int temp=0;
		while (step>1) {
			if (step>1) {
				step=(int) (step/1.3);
			}
			//按特定步长冒泡排序
			for (int i = 0; i+step < n; i++) {				
				if (input[i]>input[i+step]) {//交换
					temp=input[i];
					input[i]=input[i+step];
					input[i+step]=temp;
				}
			}
		}
	}
	/**
	 * 我自己实现的,与系尔排序差不多的实现
	 * @param input
	 * @param n
	 */
	private void combSort(int[] input, int n) {
		for (int step = (int) (n/1.3); step >0; step/=1.3) {//步长递减1.3
			for (int i = step; i < n; i++) {
				//对分组进行冒泡排序,从后向前,取最小值
				int temp=input[i];
				int j=i-step;
				while(j>=0){
					if(input[j]>input[i]){
						temp=input[j];
						input[j]=input[i];
						input[i]=temp;
					}
					j-=step;
				}
			}
		}
	}

}

PS:刚整理时,单看算法的名称,还真想不起是什么,不过,还好看文字描述说明之后,还是可以实现算法的

» 转载保留版权:《排序算法整理》
» 本文链接地址:https://www.xidige.com/903

打开支付宝扫一扫,即可进行扫码打赏哦

扫码支持
扫码打赏,你说多少就多少

标签:

分享到:

扫一扫 在手机阅读、分享本文

上一篇: 下一篇:
评论区0人评论399人参与

电子邮件地址不会被公开。 必填项已用*标注

*

loading

赞助商广告