依赖包：
junit-4.11-extended:1.0.4
commons-lang3:3.4
源码：
package com.alogrithms.sort;
/**
* Created by 410s on 2016/6/13.
*/
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.RandomUtils;
import org.junit.Test;
import java.lang.reflect.Array;
import static org.apache.commons.lang3.ArrayUtils.EMPTY_INT_ARRAY;
/**
*
*/
public class Sort {
public static int arraySize=1000000;
public static int[] nums=new int[arraySize];
static{
for(int i=0;i<arraySize;i++){
nums[i]=RandomUtils.nextInt(1,arraySize);
}
}
// public static int[] nums={2,8,7,1,3,5,6,4};
/**
* 插入排序 方法1 将后续值插入已排好序的数组中的对应位置
* 数据量 耗时
* 10W 4327
* 100W NAN
*/
@Test
public void InsertSort(){
//读取后续值，插入前边已排好序的队列中
int len=nums.length;
for(int i=0;i<len;i++)
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
//如果大于，则继续下一次循环
continue;
else{
//当前值正好大于当前值，nums[i]需要插入到num[j]之前
int tmp=nums[i];
for(int k=i;k>j;k--){
nums[k]=nums[k-1];
}
nums[j]=tmp;
break;
}
}
System.out.println(ArrayUtils.toString(nums));
}
/**
* 选择排序 寻找后续数组中的最少值，将其与数组的每一个元素替换位置
* 数据量 耗时
* 10W 8624
* 100W NAN
*/
@Test
public void SelectSort(){
//查找后续值中最小的值，将其插入已排好序的队列中
int len=nums.length;
int min=Integer.MAX_VALUE;
int min_index=0;
for(int i=0;i<len;i++){
//找到后续值中的最小值
int j=i;
for(;j<len;j++){
if(nums[j]<min)
{
min=nums[j];
min_index=j;
}
}
//找到最小值后nums[min_index]与nums[i]替换位置
int tmp=nums[i];
nums[i]=nums[min_index];
nums[min_index]=tmp;
//初始化min再次寻找后续的最小值
min=Integer.MAX_VALUE;
}
System.out.println(ArrayUtils.toString(nums));
}
/**
*
* 分治法排序
* D divide 分隔
* c Conquer 解决
* c 合并
* 数据量 耗时(ms)
* 10W 209
* 100W 750
* 300W 2347
* 1000W NAN
*/
@Test
public void DccSort(){
DccSort(0,nums.length-1);
System.out.println(ArrayUtils.toString(nums));
}
public void DccSort(int start,int end){
if(start==end)
return;
int mid=(start+end)/2;
DccSort(start,mid);
DccSort(mid+1,end);
int[] left=subarray(nums,start,mid);
int[] right=subarray(nums,mid+1,end);
int i=0;
int j=0;
for(int k=start;k<=end;k++) {
if (j>=right.length||i<left.length&&left[i] <= right[j])
{
nums[k]=left[i];
i=i+1;
}else if(i>=left.length||j<right.length){
nums[k]=right[j];
j=j+1;
}
}
}
public int[] subarray(int[] array, int startIndexInclusive, int endIndexExclusive) {
if(array == null) {
return null;
} else {
if(startIndexInclusive < 0) {
startIndexInclusive = 0;
}
if(endIndexExclusive > array.length) {
endIndexExclusive = array.length;
}
int newSize = endIndexExclusive - startIndexInclusive;
if(newSize < 0) {
return EMPTY_INT_ARRAY;
} else {
int[] subarray = new int[newSize+1];
System.arraycopy(array, startIndexInclusive, subarray, 0, newSize+1);
return subarray;
}
}
}
/**
* 冒泡排序
* 数据量 耗时(ms)
* 10W 15595
* 100W NAN
* 1000W NAN
*/
@Test
public void BubbleSort(){
for(int i=0;i<nums.length;i++)
for(int j=nums.length-1;j>i;j--){
if(nums[j]<nums[i])
{
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
}
}
System.out.println(ArrayUtils.toString(nums));
}
/**
* 堆排序
* 数据量 耗时(ms)
* 10W 162
* 100W 884
* 300W 2866
* 1000W
*/
@Test
public void HeapSort(){
for(int i=nums.length/2-1;i>=0;i--)
this.max_heapify(i,nums.length);
for(int i=nums.length-1;i>=1;i--){
int tmp=nums[0];
nums[0]=nums[i];
nums[i]=tmp;
max_heapify(0,nums.length-(nums.length-i));
}
System.out.println(ArrayUtils.toString(nums));
}
/**
*
* @param i
* @param size 对数组中 前size个元素构建堆
*/
public void max_heapify(int i,int size){
int l=this.leftIndex(i);
int r=this.rightIndex(i);
int largest=0;
if(l<size&&nums[l]>nums[i])
{
largest=l;
}else
{
largest=i;
}
if(r<size&&nums[r]>nums[largest]){
largest=r;
}
if(largest!=i){
int tmp=nums[i];
nums[i]=nums[largest];
nums[largest]=tmp;
max_heapify(largest,size);
}
}
public static final int parentIndex(int i)
{
return (i-1)/2;
}
public static final int leftIndex(int i)
{
return 2*i+1;
}
public static final int rightIndex(int i)
{
return 2*i+2;
}
/**
* 快速排序
*/
@Test
public void QuickSort(){
QuitSort_Random(0,nums.length-1);
System.out.println(ArrayUtils.toString(nums));
};
public void QuickSort_Classical(int p,int r){
if(p<r)
{
int q=QuickSort(p,r);
QuickSort_Classical(p,q-1);
QuickSort_Classical(q+1,r);
}
}
public void QuitSort_Random(int p,int r){
if(p<r){
int i=RandomUtils.nextInt(p,r);
int tmp=nums[i];
nums[i]=nums[r];
nums[r]=tmp;
int mid=QuickSort(p,r);
QuitSort_Random(p,mid-1);
QuitSort_Random(mid+1,r);
}
}
public int QuickSort(int p,int r){
int x=nums[r];
int i=p-1;
for(int j=p;j<r;j++){
if(nums[j]<=x){
i++;
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
}
}
int tmp=nums[i+1];
nums[i+1]=nums[r];
nums[r]=tmp;
return i+1;
}
/**
* 计数排序
* 10W 155
* 100w 603
*/
@Test
public void CountingSort(){
int max=nums[0];
for(int i=0;i<nums.length;i++){
if(nums[i]>max)
max=nums[i];
}
int[] c=new int[max+1];
int[] out=new int[nums.length];
for(int i=0;i<nums.length;i++){
c[nums[i]]++;
}
for(int i=1;i<nums.length;i++){
c[i]=c[i]+c[i-1];
}
for(int i=nums.length-1;i>=0;i--){
out[c[nums[i]]-1]=nums[i];
c[nums[i]]--;
}
System.out.println(ArrayUtils.toString(out));
}
}
