Java 几种排序法

这里主要对8种排序算法做个总结，分别是插入排序，选择排序，冒泡排序，希尔排序，归并排序，堆排序，快速排序以及基数排序。
1、 插入排序
比较和交换的时间复杂度为O(n^2)，算法自适应，对于数据已基本有序的情况，时间复杂度为O(n)，算法稳定，开销很低，适合于数据已基本有序或者数据量小的情况。
public void insertionSort() {// 插入排序

int out, in;

int count1 = 0, count2 = 0;// 复制次数，比较次数

for (out = 1; out < nElems; out++) {

long temp = a[out];

in = out;

boolean flag=in>0&&a[in-1]>=temp;

while(flag){

if(a[in-1]>=temp){

if(in>0){

a[in]=a[in-1];

count1++;

--in;

}

}

count2++;

flag=in>0&&a[in-1]>=temp;

}

a[in] = temp;

}

System.out.println("复制次数为：" + count1 + " 比较次数为：" + count2);

}

2、 选择排序
算法不稳定，O(1)的额外的空间，比较的时间复杂度为O(n^2)，交换的时间复杂度为O(n)，并不是自适应的。在大多数情况下都不推荐使用。只有在希望减少交换次数的情况下可以用。
public void selectionSort(){//选择排序

int out, in, min;

for(out=0;out<nElems-1;out++){

min=out;

for(in=out+1;in<nElems;in++){

if(a[in]<a[min]){

min=in;

}

swap(out,min);

}

}

}

3、 冒泡排序
算法稳定，O(1)的额外的空间，比较和交换的时间复杂度都是O(n^2)，自适应，对于已基本排序的算法，时间复杂度为O(n)。冒泡算法的许多性质和插入算法相似，但对于系统开销高一点点。
public void bubbleSort() {// 冒泡排序，单项

int out, in;