几种稳定排序算法_JAVA_编程开发_程序员俱乐部

class="java">
package com.study.sort;

import java.util.LinkedList;

public class StableSort {
	
	/**
	 * 生成一个随机数组
	 * @param length 数组长度
	 * @return 生成的数组
	 */
	public static int[] init(int length){
		int [] before=new int[length];
		Random rand=new Random(47);
		for(int i=0;i<length;i++){
			before[i]=rand.nextInt(100);
		}
		return before;
	}
	
	/**
	 * 插入排序
	 * @param before 待排序数组
	 * @return 排序后数组
	 */
	public static int[] insertSort(int[] before){
		for(int j=1;j<before.length;j++){
			int i=j-1;
			int key=before[j];
			while(i>=0&&key<before[i]){
				before[i+1]=before[i];
				i--;
			}
			before[i+1]=key;
		}
		
		return before;
	}
	
	/**
	 * 冒泡排序
	 * @param before 待排序数组
	 * @return 排序后数组
	 */
	public static int[] bubbleSort(int[] before){
		int temp=0;
		for(int i=before.length-1;i>0;i--){
			for(int j=0;j<i;j++){
				if(before[j+1]<before[j]){
					temp=before[j+1];
					before[j+1]=before[j];
					before[j]=temp;
				}
			}
		}
		
		return before;
	}
	
	/**
	 * 鸡尾酒排序（双向冒泡）
	 * @param before 待排序数组
	 * @return 排序后数组
	 */
	public static int[] cocktailSort(int[] before){
		for(int i=0;i<(before.length/2);i++){
			for(int j=i;j<before.length-i-1;j++){
				if(before[j]>before[j+1]){
					int temp=before[j+1];
					before[j+1]=before[j];
					before[j]=temp;
				}
			}
			for(int j=(before.length-1-(i+1));j>i;j--){
				if(before[j]<before[j-1]){
					int temp=before[j];
					before[j]=before[j-1];
					before[j-1]=temp;
				}
			}
		}
		
		return before;
	}
	
	/**
	 * 归并排序
	 * @param before 待排序数组
	 * @return 排序后数组
	 */
	public static int[] mergeSort(int[] before){
		recMergeSort(before,0,before.length-1);
		return before;
	}
	public static void recMergeSort(int[] before,int lowerBound,int upperBound){
		if(lowerBound==upperBound)
			return;
		else{
			int mid=(lowerBound+upperBound)/2;
			recMergeSort(before,lowerBound,mid);
			recMergeSort(before,mid+1,upperBound);
			merge(before,lowerBound,mid+1,upperBound);
		}
	}
	public static void merge(int[] before,int lowerBound,int mid,int upperBound){
		Queue<Integer> temp = new LinkedList<Integer>();
		int indexA=lowerBound;
		int indexB=mid;
		
		while(indexA<=(mid-1)&&indexB<=upperBound){
			if(before[indexA]<before[indexB])
				temp.offer(before[indexA++]);
			else
				temp.offer(before[indexB++]);
		}
		while(indexA<=(mid-1))
			temp.offer(before[indexA++]);
		while(indexB<=upperBound)
			temp.offer(before[indexB++]);
		
		int index=0;
		while(temp.size()>0){
			before[lowerBound+index]=temp.poll();
			index++;
		}
	}
	

	/**
	 * 打印数组内容到控制台
	 * @param before 待显示数组
	 */
	public static void prt(int[] before){
		for(int x:before){
			System.out.print(x+"  ");
		}
		System.out.println("");
	}
	
	public static void main(String[] args){
		int[] before=init(10);
		prt(before);
//		insertSort(before);
//		bubbleSort(before);
//		cocktailSort(before);
		mergeSort(before);
		prt(before);
	}
}