简单排序（Java实现）。
冒泡排序
原理
- 比较相邻元素，如果前者比后者大，交换
- 对所有相邻元素重复
- 对除了最后一个的所有元素重复2
复杂度
最好情况：O(n)
平均时间复杂度：O(n^2)
代码
public static void bubbleSort(int[] a){
for(int outer = a.length - 1; outer > 1; outer--)
for(int inner = 0; inner < outer ;inner++)
if(a[inner] > a[inner + 1])
swap(a, inner, inner+1);
}
选择排序
原理
每次选出最小的元素放到开始位置。
复杂度
时间复杂度 O(n^2)
但是交换次数比冒泡排序少
代码
public static void selectSort(int[] a){
int min;
for(int i = 0; i < a.length - 1; i++){
min = i;
for(int j = i + 1; j < a.length; j++)
if(a[j] < a[min]) min = j;
swap(a, i, min);
}
}
插入排序
原理
在局部有序的数字中插入被标记的值。
复杂度
时间复杂度为O(n^2)
但是一般情况下比冒泡排序快一倍，比选择排序也快一点。
代码
public static void insertSort(int[] a){
for(int i = 1; i < a.length; i++){
int j = i, temp = a[i];
while(j > 0 && a[j - 1] >= temp){
a[j] = a[j - 1];j--;
}
a[j] = temp;
}
}
三种排序的比较
选择排序降低了交换次数，但是比较次数仍然很多，当数据量比较少，或者基本上有序的时候，使用选择排序。
对于其他情况，应该选择插入排序。
