import java.util.Random;
import org.junit.Test;
import junit.framework.TestCase;
/**
* 各类排序算法,这里假设各类排序都为升序排序
* 如果想实现可服用的排序方式,可参见冒泡排序算法实现,该排序方式支持升序和降序排序
* @author gaoyusi
* @since 2010-3-30
* {@link http://blog.csdn.net/gaoyusi4964238}
*
*/
public class Sort extends TestCase{
private enum SortForward{ASC,DEC};
private static final int ARRAY_LENGTH=100000;
/*-------------------------------------------------*/
/*---------------------------测试方法---------------*/
@Test
public void testBubbleSort(){
int [] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============Bubble Sort==================");
//System.out.println("Before Bubble Sort:"+getoutputString(list));
long startTime=getCurrentTime();
BubbleSort(list,SortForward.ASC);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("ASC Bubble Sort:"+getoutputString(list));
//BubbleSort(list,SortForward.DEC);
//System.out.println("DEC Bubble Sort:"+getoutputString(list));
}
@Test
public void testStraightInsertionSort(){
int [] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============straight insert Sort=========");
//System.out.println("Before straight insert Sort:"+getoutputString(list));
long startTime=getCurrentTime();
straightInsertionSort(list);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after straight insert Sort:"+getoutputString(list));
}
@Test
public void testBinaryInsertionSort(){
int [] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============Binary insert Sort==========");
//System.out.println("Before Binary insert Sort:"+getoutputString(list));
long startTime=getCurrentTime();
BinaryInsertionSort(list);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after Binary insert Sort:"+getoutputString(list));
}
@Test
public void testShellSort(){
int [] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============Shell Sort=================");
//System.out.println("Before Shell Sort:"+getoutputString(list));
long startTime=getCurrentTime();
shellSort(list,new int[]{5,3,1});
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after Shell Sort:"+getoutputString(list));
}
@Test
public void testQuickSort(){
int[] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============Quick Sort=================");
//System.out.println("before Quick Sort:"+getoutputString(list));
long startTime=getCurrentTime();
quickEnterSort(list);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after Quick Sort:"+getoutputString(list));
}
@Test
public void testSimpleSelectSort(){
int[] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============simple select Sort=========");
//System.out.println("before simple select Sort:"+getoutputString(list));
long startTime=getCurrentTime();
simpleSelectionSort(list);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after simple select Sort:"+getoutputString(list));
}
@Test
public void testHeapSort(){
int[] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============Heap Sort=========");
//System.out.println("before heap Sort:"+getoutputString(list));
long startTime=getCurrentTime();
heapSort(list);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after heap Sort:"+getoutputString(list));
}
@Test
public void testMergeSort(){
int[] list=new int[ARRAY_LENGTH];
fulfillList(list);
System.out.println("============Merge Sort=========");
//System.out.println("before Merge Sort:"+getoutputString(list));
long startTime=getCurrentTime();
mergeSort(list);
System.out.println("Time:"+(getCurrentTime()-startTime));
//System.out.println("after Merge Sort:"+getoutputString(list));
}
/*--------------------------------------------------*/
/*---------------------------辅助方法---------------*/
/**
* 填充测试数据
*/
public void fulfillList(int[] list){
Random random=new Random();
for(int i=0;i<list.length;i++){
list[i]=random.nextInt(10000);
}
}
public long getCurrentTime(){
return System.nanoTime();
}
/**
* 将数组打印输出
*/
private String getoutputString(int[] list) {
if(list==null)
return null;
StringBuilder str=new StringBuilder();
str.append("[");
for(int i=0;i<list.length;i++){
if(i==0){
str.append(list[i]);
continue;
}
str.append(",").append(list[i]);
}
str.append("]");
return str.toString();
}
/**
* 数据交换
*/
private void swap(int[] list, int i, int j) {
int temp=list[i];
list[i]=list[j];
list[j]=temp;
}
/*--------------------------------------------------*/
/*---------------------------排序算法---------------*/
/************************插入排序************************/
/**
* 直接插入排序(升序排序)
*/
public void straightInsertionSort(int[] list){
if(list==null||list.length<1){
return ;
}
for(int i=1;i<list.length;i++){
//此处可以加一个判断,如果list[i]>list[i-1]的话,continue;
int temp=list[i];
int j=i-1;
for(;j>=0&&temp<list[j];j--){
list[j+1]=list[j];
}
list[j+1]=temp;
}
}
/**
* 二分插入排序(升序排序)
*/
public void BinaryInsertionSort(int [] list){
if(list==null||list.length<1){
return;
}
for(int i=1;i<list.length;i++){
int temp=list[i];
int low=0,high=i-1;
while(low<=high){
int mid=(low+high)/2;
if(list[mid]>temp)
high=mid-1;
else
low=mid+1;
}
for(int j=i-1;j>high;j--)list[j+1]=list[j];
list[high+1]=temp;
}
}
/**
* shell排序
* @param l 待排序数组
* @param il 增量数组[数据是2^n-1,并递减的,此处可以做一个简单排序]
*/
public void shellSort(int [] l,int[] il){
if(l==null||l.length<1||il==null||il.length<1)
return;
for(int i=0;i<il.length;i++)//趟数
shellSort(l,il[i]);
}
public void shellSort(int[] l,int increment){
for(int m=increment;m<l.length;m++){
if(l[m]>l[m-increment])
continue;
int temp=l[m];
int n=m-increment;
for(;n>=0&&l[n]>temp;n-=increment)
l[n+increment]=l[n];
l[n+increment]=temp;
}
}
/************************快速排序***********************/
/**
* 冒泡排序
* @param forward 排序方向,ASC:升序;DEC:降序
*/
public void BubbleSort(int[] list,SortForward forward){
if(list==null||list.length<1){
return;
}
for(int i=1;i<list.length;i++){//趟数
//此处可以加一个flag,如果在下面冒泡过程中没有数据交换过程发生,
//则表示剩下数据已有序,排序结束(这样能保证有序的数列在此排序所需时间复杂度仅为o(n))
for(int j=0;j<list.length-i;j++){//冒泡
if(forward==SortForward.ASC&&list[j]>list[j+1]){
swap(list,j,j+1);
}else if(forward==SortForward.DEC&&list[j]<list[j+1]){
swap(list,j,j+1);
}
}
}
}
public void quickEnterSort(int[] list){
quickSort(list,0,list.length-1);
}
public void quickSort(int [] list,int low,int high){
if(low<high){
int pivotloc=partition(list,low,high);
quickSort(list,low,pivotloc-1);
quickSort(list,pivotloc+1,high);
}
}
/**
* 快速排序的每一次划分执行
* 该处可改进方式:
* 1.取low,high,(low+high)/2中最大值为pivotkey,然后将low值和pivot指向位置处值互换,
* 这样可以不用修改程序其他部分(该种实现方式能够减轻piovt两端长度不均衡情况)
* 2.对于下面while(low<high&&list[high]>=pivotkey)和while(low<high&&list[low]<=pivotkey)
* 分别加一个标志位,如果在每个循环执行到(low+high)/2处时,仍没有数据交换现象发生,
* 那么该半段数据是有序的,从而停止该部分数据的再划分排序(那么此时此处返回的应该是包含三个字段的一个对象
* (当前piovt位置,前半段数据是否有序标志,后半段数据是否有序标志))
*/
public int partition(int [] list,int low,int high){
int pivotkey=list[low];
while(low<high){
while(low<high&&list[high]>=pivotkey) high--;
list[low]=list[high];
while(low<high&&list[low]<=pivotkey) low++;
list[high]=list[low];
}
list[low]=pivotkey;
return low;
}
/************************选择排序***********************/
/**
* 简单选择排序
*/
public void simpleSelectionSort(int [] list){
if(list==null||list.length<1){
return;
}
for(int i=0;i<list.length-1;i++){
int j=selectMinValueLeave(list,i);
if(i!=j)
swap(list,i,j);
}
}
/**
* 从以i开头的所有数组中选择出最小值下标
*/
private int selectMinValueLeave(int[] list, int start) {
int pivot =start;
for(int j=start+1;j<list.length;j++){
if(list[j]<list[pivot])
pivot=j;
}
return pivot;
}
/**
* 堆排序
*/
public void heapSort(int [] list){
for(int i=list.length/2;i>=0;i--){
heapAdjust(list,i,list.length-1);
}
for(int i=list.length-1;i>0;){
swap(list,0,i);
heapAdjust(list,0,--i);
}
}
/**
* 堆调整
*/
private void heapAdjust(int [] list,int start,int end){
if(start==end)
return;
int pivot=list[start];
for(int j=start*2;j<=end;j=j*2){
if(j<end&&list[j]<list[j+1])
j++;
if(pivot>=list[j]) break;
list[start]=list[j];
start=j;
}
list[start]=pivot;
}
/************************归并排序***********************/
/**
* 归并排序
*/
public void mergeSort(int [] list){
msort(list,0,list.length-1);
}
private void msort(int [] list,int start,int end){
if(start==end){
return;
}
else {
int mid=(start+end)/2;
msort(list,start,mid);
msort(list,mid+1,end);
merge(list,start,mid,end);
}
}
/**
* 归并段合并借助于插入排序
* 另一种方式是借助于一个长度为n的辅助存储空间,这里不再实现
*/
private void merge(int [] list,int start,int mid,int end){
/*
* 如果归并的前半段后后半段已经有序,直接返回
*/
if(list[mid+1]>list[mid])
return;
for(int i=mid+1;i<=end;i++){
int temp=list[i];
int j=i-1;
while(j>=start&&list[j]>temp){
list[j+1]=list[j];
j--;
}
list[j+1]=temp;
}
}
}
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9),R是基数(个十百)
Shell O(nlogn) O(ns) 1<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好