公用的交换模块：
protected void swap(int[] a, int i, int j) {
if (i == j) {
return;
}
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
冒泡排序：效率O(n^2), 稳定
public void sort(int[] a) {
for(int i=a.length-1; i>=1;i--)
{
for(int j=1;j<=i;j++)
{
if(a[j-1]>a[j])
{
swap(a,j-1,j);
}
}
}
}
选择排序：效率O(n^2), 不稳定
public void sort(int[] a) {
for (int i = a.length - 1; i >= 1; i--) {
int max = 0;
for (int j = 1; j <= i; j++) {
if (a[max] < a[j]) {
max = j;
}
}
swap(a, i, max);
}
}
插入排序：效率O（n^2）,稳定
public void sort(int[] a) {
for(int i=1;i
{
int tmpVal = a[i];
int tmpNo = i;
while(tmpNo > 0 && a[tmpNo-1] >= tmpVal)
{
a[tmpNo] = a[tmpNo-1];
tmpNo--;
}
a[tmpNo] = tmpVal;
}
}
希尔排序： 效率 O（n^(5/4)） ~O（n^(3/2)）,不稳定
public void sort(int[] a) {
int h = 1;
while (h < a.length) {
h = 3 * h + 1;
}
while (h > 0) {
for (int i = h; i < a.length; i += h) {
int tmpNo = i;
int tmpVal = a[i];
while (tmpNo > h - 1 && a[tmpNo - h] >= tmpVal) {
a[tmpNo] = a[tmpNo - h];
tmpNo -= h;
}
a[tmpNo] = tmpVal;
}
h = (h - 1) / 3;
}
}
归并排序：O(n*log(2))，稳定，缺点是需要额外的一倍内存
代码待补充
快速排序：最好O(n*log(n)), 最差 O(n^2)，不稳定
public void sort(int[] a) {
this.sort(a, 0, a.length - 1);
}
private void sort(int[] a, int first, int last) {
if (first >= last) {
return;
}
int p = pation(a, first, last);
sort(a, first, p - 1);
sort(a, p + 1, last);
}
private int pation(int[] a, int first, int last) {
int pivot = a[last];
int leftPt = first - 1;
int rightPt = last;
while (true) {
while (leftPt < last && a[++leftPt] < pivot);
while (rightPt > first && a[--rightPt] > pivot);
if (leftPt < rightPt) {
swap(a, leftPt, rightPt);
} else {
break;
}
}
swap(a, leftPt, last);
return leftPt;
}
堆排序：O(n*log(2))，即使逆序也不会太坏，不稳定
代码待补充