笔记：常用排序算法
公用的交换模块：
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))，即使逆序也不会太坏，不稳定
代码待补充