java 排序算法代码大全

java 排序算法代码大全

2012-04-17 14:58:02| 分类： JAVA 知识积累 |字号订阅

/**

* 插入排序:直接插入排序、折半插入排序和系尔排序

* 交换排序:冒泡排序和快速排序

* 选择排序:简单选择排序和堆排序

* 归并排序:归并排序

*

* 基本思想

* 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。

* 交换排序:按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。 * 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。

*

* 排序方法比较

* 排序方法平均时间最坏时间辅助存储

* 直接插入排序 O(N2) O(N2) O(1)

* 起泡排序 O(N2) O(N2) O(1)

* 快速排序 O(Nlog2N) O(N2) O(Nlog2N)

* 简单选择排序 O(N2) O(N2) O(1)

* 堆排序 O(Nlog2N) O(Nlog2N) O(1)

* 归并排序 O(Nlog2N) O(Nlog2N) O(n)

* 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix)

*

*

*

* @author Administrator

*

*/

public class SortTest {

public static void main(String[] args)throws Exception {

//测试排序是否正确

//String[] testErr=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"};

//new SortTest().testErr(testErr);

//排序1（全部）

String[] strs=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","希尔排序","堆排序","归并排序","快速排序"};

new SortTest().test(strs,10000,50000,5000);

//排序2（加强）

String[] strs2=new String[]{"希尔排序","堆排序","归并排序","快速排序"}; new SortTest().test(strs2,100000,1900000,100000);

}

private void testErr(String[] strings) throws Exception{

//System.out.println(Arrays.toString(old));

System.out.println(Arrays.toString(strings));

Number[] old=getRundom(50);

Integer[]

oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};

old=oo;

for(String s:strings){

Number[] testNum=Arrays.copyOf(old, old.length);

long begin=System.currentTimeMillis();

SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);

long end=System.currentTimeMillis();

System.out.println(s+":"+(end-begin)+"\t");

System.out.println(Arrays.toString(testNum));

}

System.out.println();

}

private void test(String[] strings,long begin,long end,long step) throws Exception{ System.out.print("数量\t");

for(String str:strings){

System.out.print(str+"\t");

}

System.out.println();

for(long i=begin;i<end;i=i+step){

System.out.print(i+"个\t");

Number[] old=getRundom(i);

for(String s:strings){

Number[] testNum=Arrays.copyOf(old, old.length);

long beginTime=System.currentTimeMillis();

SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);

long endTime=System.currentTimeMillis();

System.out.print((endTime-beginTime)+"\t");

//System.out.println(Arrays.toString(testNum));

}

System.out.println();

}

}

private static Integer[] getRundom(long num) {

List<Integer> list=new ArrayList<Integer>();

for(long i=0;i<num;i++){

int k;

if(Math.random()>0.5){

k=(int)(Math.random()*Integer.MAX_VALUE);

}else{

k=(int)(Math.random()*Integer.MIN_VALUE);

}

list.add(k);

}

return list.toArray(new Integer[list.size()]);

}

/**

* 插入排序————直接插入排序

* @param data

*/

public static void 直接插入排序(Number[] data)

{

Number tmp=null ;

for(int i=1;i<data.length;i++){

tmp = data[i];

int j=i-1;

while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){

data[j+1]=data[j];

j--;

}

data[j+1]=tmp;

}

}

/**

* 插入排序————折半插入排序

* @param data

*/

public static void 折半插入排序(Number[] data)

{

Number tmp=null ;

for(int i=1;i<data.length;i++){

tmp = data[i];

int smallpoint=0;

int bigpoint=i-1;

while(bigpoint>=smallpoint){

int mid=(smallpoint+bigpoint)/2;

if(tmp.doubleValue()>data[mid].doubleValue()){

smallpoint=mid+1;

}else{

bigpoint=mid-1;

}

}

for(int j=i;j>smallpoint;j--){

data[j]=data[j-1];

}

data[bigpoint+1]=tmp;

}

}

/**

* 插入排序————希尔排序

* @param data

*/

public static void 希尔排序(Number[] data)

{

int span=data.length/7;

if(span==0)span=1;

while(span>=1){

for(int i=0;i<span;i++){

for(int j=i;j<data.length;j=j+span){

//组内直接插入排序

int p = j-span;

Number temp = data[j];

while( p >=0 && data[p].doubleValue() > temp.doubleValue()){ data[p+span] = data[p];

p -=span;

}

data[p + span] = temp;

}

}

span=span/2;

}

}

/**

* 交换排序————冒泡排序

*

* @param data

*/

public static void 冒泡排序(Number[] data)

{

for (int i = 0; i < data.length; i++) {

//将相邻两个数进行比较，较大的数往后冒泡

for (int j = 0; j < data.length - i-1; j++) {

if (data[j].doubleValue()> data[j + 1].doubleValue()) {

//交换相邻两个数

swap(data, j, j + 1);

}

}

}

}

/**

* 交换排序————快速排序

* @param data

*/

public static void 快速排序(Number[] data)

{

QuickSort(data,0,data.length-1);

}

private static void QuickSort(Number[] data, int begin, int end) {

// System.out.println(begin+":"+end);

if(begin<end){

//取中点

int mid=(begin+end)/2;

if(data[end].doubleValue()<data[begin].doubleValue()){

swap(data, end, begin);

}

if(data[end].doubleValue()<data[mid].doubleValue()){

swap(data, end, mid);

}

if(data[mid].doubleValue()<data[begin].doubleValue()){

swap(data, mid, begin);

}

swap(data, mid, begin);

// System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) ); int min=begin+1;

int big=end;

while(true){

while(min<big

data[min].doubleValue()<data[begin].doubleValue()){min++;}

while(min<big

data[big].doubleValue()>=data[begin].doubleValue()){big--;}

if(min>=big){

break;

}

swap(data, min, big);

}

if(data[begin].doubleValue()>data[min].doubleValue()){

swap(data, begin, min);

}

if(min>1)

QuickSort(data,begin,min-1);

//if(min<end)

QuickSort(data,min,end);

}

}

/**

* 选择排序————简单选择排序

* @param data

*/

public static void 简单选择排序(Number[] data)

{

for (int i = 0; i < data.length-1; i++) {

int smallPoint=i;

for (int j = i+1; j < data.length; j++) {

if (data[smallPoint].doubleValue()> data[j].doubleValue()) { smallPoint=j;

}

} && &&

swap(data, i, smallPoint);

}

}

/**

* 选择排序————堆排序

* @param data

*/

public static void 堆排序(Number[] data)

{

int n = data.length;

for(int i=n/2;i>=0;i--){

keepHeap(data, n, i);

}

while (n > 0) {

swap(data, 0, n-1);

keepHeap(data, --n, 0);

}

}

private static void keepHeap(Number[] a, int n, int i) {

Number x = a[i];

int j = 2 * i + 1;

while (j <= n - 1) {

if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue()) ++j;

if (a[j].doubleValue() > x.doubleValue()) {

a[i] = a[j];

i = j;

j = 2 * i ;

} else{

break;

}

}

a[i] = x;

}

/**

* 归并排序法————归并排序

* @param data

*/

public static void 归并排序(Number[] data)

{

Number[] result = merge_sort(data,0,data.length-1); for(int i=0;i<result.length;i++){

data[i]=result[i];

}

}

private static Number[] merge_sort(Number[] array, int start, int end){ Number[] result = new Number[end-start+1];

if(start< end){

int mid= (start+end)/2;

Number[] left= merge_sort(array, start, mid);

Number[] right = merge_sort(array, mid+1, end); result= merge(left,right);

} else if (start == end) {

result[0] = array[start];

return result;

}

return result;

}

private static Number[] merge(Number[] left, Number[] right) { Number[] result = new Number[left.length+right.length]; int i=0;

int j=0;

int k=0;

while(i< left.length&&j< right.length){

if(left[i].doubleValue()< right[j].doubleValue()){ result[k++] = left[i++];

}else{

result[k++] = right[j++];

}

}

while(i< left.length){

result[k++] = left[i++];

}

while (j< right.length) {

result[k++]= right[j++];

}

return result;

}

/**

* 交换数组中指定的两元素的位置

* @param data

* @param x

* @param y

*/

private static void swap(Number[] data, int x, int y) { Number temp = data[x];

}

} data[x] = data[y]; data[y] = temp;