冒泡、选择、插入排序算法
一、冒泡排序
算法描述
①、比较相邻的元素，如果第一个比第二个大，就交换他们两个。
②、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。
③、针对所有的元素重复以上的步骤，除了最后一个。
④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现：
public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length-i-1; j++) {
// i=0，两两进行9轮比较0...8，经过一轮之后最大值出现
// i=1，两两进行8轮比较0...7，以此类推
if (a[j] > a[j+1]) {
int tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
}
}
}
}
冒泡性能分析：
假设参与比较的数组元素个数为 N，则第一轮排序有 N-1 次比较，第二轮有 N-2 次，如此类推，这种序列的求和公式为：
（N-1）+（N-2）+...+1 = N*（N-1）/2
当 N 的值很大时，忽略减1，算法比较次数约为N*N/2次。
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n) | O(n²) | O(1) |
冒泡排序是最容易实现的排序， 最坏的情况是每次都需要交换，共需遍历并交换将近n²/2次，时间复杂度为O(n²)。最佳的情况是内循环遍历一次后发现排序是对的，因此退出循环，时间复杂度为O(n)。 平均来讲，时间复杂度为O(n²)。由于冒泡排序中只有缓存的temp变量需要内存空间，因此空间复杂度为常量O(1)。
二、选择排序
算法描述
①、从未排序序列中，找到关键字最小的元素
②、如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
③、重复1、2步，直到排序结束。
代码实现：
public static void selectSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // 默认最小值下标
for(int j=i+1; j<a.length; j++){
if(a[j] < a[min]){
min = j;
}
}
// 没经过一轮排序，最小值出现
if(min != i){
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
选择性能分析：
选择排序和冒泡排序执行了相同次数的比较：N*（N-1）/2，但是至多只进行了N次交换。
只有temp变量需要内存空间。
选择排序交换次数少，比冒泡排序要快。
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
三、插入排序
算法描述
①、从第一个元素开始，该元素可以认为已经被排序
②、取出下一个元素，在已经排序的元素序列中从后向前扫描
③、如果该元素（已排序）大于新元素，将该元素移到下一位置
④、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤、将新元素插入到该位置后
⑥、重复步骤2~5
代码实现：
public static void insertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int tmp = a[i]; // tmp待插入数据
int j = i;
while(j > 0 && tmp < a[j-1]){ // 与前面有序数组进行j轮比较
a[j] = a[j-1]; // 前面大则后移
j--;
}
a[j] = tmp; // 找到比其小的插入
}
}
插入性能分析：
总共进行N-1轮比较，第一轮最多比较1次，第二轮最多2次....最后一轮N-1次，总比较次数：1+2+3+...+N-1 = N*（N-1）/2。
假设在每一轮排序发现插入点时，平均只有全体数据项的一半进行了比较，平均比较次数：N*（N-1）/4，大O表示法O(N^2)。
插入排序对于元素已经有序(或接近有序)的数组进行排序将会比随机顺序数组或逆序数组排序要快得多。
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
总结：
一般情况下，不太使用冒泡排序算法，然而当数据量很小的时候会有些应用价值。
选择排序虽然把交换次数降到了最低，但比较次数仍然很大，当数据量很小并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
当数据量比较小或基本有序时，插入算法是最好的选择。
对于更大数据量的排序来说，快速排序通常是最快的方法，后续再做介绍。
算法除了在速度方面的比较之外，还应考虑内存空间使用情况，上述三种排序算法都属于内部排序，除了初始的数组外几乎不需要其他的内存空间，所有排序算法都需要一个额外的变量来暂时存储交换时的数据项。