简单排序（Java实现）。

冒泡排序

原理

1. 比较相邻元素，如果前者比后者大，交换
2. 对所有相邻元素重复
3. 对除了最后一个的所有元素重复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;
    }
}

三种排序的比较

选择排序降低了交换次数，但是比较次数仍然很多，当数据量比较少，或者基本上有序的时候，使用选择排序。
对于其他情况，应该选择插入排序。