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

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

import java.util.Random;

public class UnstableSort {
	/**
	 * 生成一个随机数组
	 * @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[] selectSort(int[] before){
		int min;
		for(int i=0;i<before.length-1;i++){
			min=i;
			for(int j=i+1;j<before.length;j++){
				if(before[j]<before[min]){
					int temp=before[j];
					before[j]=before[min];
					before[min]=temp;
				}
			}
		}		
		return before;
	}
		
	/**
	 * 堆排序
	 * @param before 待排序数组
	 * @return 排序后数组
	 */
	public static int[] heapSort(int[] before){
		for(int i=0;i<before.length-1;i++){
			buildMaxHeap(before,before.length-1-i);
			swap(before,0,before.length-1-i);
		}
		return before;
	}
	public static void buildMaxHeap(int[] before,int bound){
		for(int i=(bound-1)/2;i>=0;i--){
			int k=i;
			while(k*2+1<=bound){
				int biggerIndex=2*k+1;
				//比较其左右节点 并保存较大值的下标
				if(biggerIndex<bound){
					if(before[biggerIndex]<before[biggerIndex+1])
						biggerIndex++;
				}
				//比较子节点较大值与自身大小，如果小于，将自身值替换为较大值
				if(before[k]<before[biggerIndex]){
					swap(before,k,biggerIndex);
					k=biggerIndex;
				}else
					break;
			}
		}
	}
	public static void swap(int[] before,int x,int y){
		if(x<before.length&&y<before.length){
			int temp=before[x];
			before[x]=before[y];
			before[y]=temp;
		}
	}
	
	/**
	 * 快排
	 * @param before 待排序数组
	 * @return 排序后数组
	 */
	public static int[] quickSort(int[] before){
		_quickSort(before,0,before.length-1);
		return before;
	}
	public static void _quickSort(int[] before,int low,int high){
		if(low<high){
			int mid=partion(before,low,high);
			_quickSort(before,low,mid-1);
			_quickSort(before,mid+1,high);
		}
	}
	public static int partion(int[] before,int low,int high){
		int temp=before[low];
		while(low<high){
			while(low<high&&before[high]>=temp)
				high--;
			before[low]=before[high];
			while(low<high&&before[low]<=temp)
				low++;
			before[high]=before[low];
		}
		before[low]=temp;
		return low;
	}
	
	/**
	 * 希尔排序（最小增量排序，改进的插入排序） 
	 * @param before
	 * @return
	 */
	public static int[] shellSort(int[] before){
		int size=before.length;
		for(int gap=size/2;gap>=1;gap/=2){
			for(int i=gap;i<size;i++){
				int k;
				int temp=before[i];
				for(k=i-gap;k>=0&&before[k]>temp;k-=gap)
					before[k+gap]=before[k];
				before[k+gap]=temp;
			}
		}
		return before;
	}
	
	/**
	 * 打印数组内容到控制台
	 * @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);
//		selectSort(before);
//		heapSort(before);
//		quickSort(before);
		shellSort(before);
		prt(before);
	}
}