三大排序在我们刚开始学习编程的时候就接触过，也是刚开始工作笔试会遇到的，后续也会学习希尔、快速排序，这里顺便复习一下
冒泡排序：
步骤：
1、从首位开始，比较首位和右边的索引
2、如果当前位置比右边的大，则交换位置
3、当前位置的索引向右移动一位，必须两两比较
图例：
代码实现：
public static int[] sort(int[] array) {
for (int i = 1; i < array.length; i++) { //外层循环，代表着需要经过多少轮比较
boolean flag = true;
for (int j = 0; j < array.length-i; j++) { //内层循环，两两比较，用来移动索引的，直到找到最大值，注意这里是array.length-i,当然-1也可以，只不过效率会降低，而且没必要
if (array[j]>array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = false;
}
}
if (flag) { //理论上，要经过N-1轮比较，但是如果在之前数据正好是有序的，直接break，减少了循环的次数，这就是flag的作用
break;
}
}
return array;
}
public static void display(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void main(String[] args) {
int[] array = new int[]{77, 99, 33, 44 ,55, 11, 9, 101, 2};
System.out.print("排序前：");
display(array);
sort(array);
System.out.print("\r\n排序后：");
display(array);
}
输出结果：
排序前：77 99 33 44 55 11 9 101 2
排序后：2 9 11 33 44 55 77 99 101
上面代码中注释已经很明显了，而且冒泡排序很简单的，稍微看一遍，应该都可以写出来了
冒泡排序的效率：
第一轮，经过N-1次比较，第二轮是N-2次比较，理论上经过N-1轮：(N-1)+(N-2)+...+1=N*(N-1)/2，在N比较大的时候，可以约等于N^2/2
而数据交换的次数：如果数据完全是随机的，交换个可能是50%，那就是N^2/4
由于常数不算在大O算法中，可以忽略2和4，所以可以认为冒泡排序的时间复杂度O(N^2)
在任何情况，双层循环我们都可以认为时间复杂度O(N^2)，因为外层为N次，内层为N或者几分之N
选择排序：
选择排序在冒泡排序的基础上进行了改进
步骤：
1、找到最小值的索引
2、如果最小值的索引不是首位，就交换
3、最小值的索引右移一位，继续比较
图例：
代码实现：
public static int[] sort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
int min = i; //min为最小值的索引，默认为0
for (int j = i+1; j < array.length; j++) { //这里是j=i+1开始的，循环结束得到最小值的索引
if (array[min]>array[j]) {
min = j;
}
}
if (min != i) { //如果索引不是首位，就交换
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
return array;
}
public static void display(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void main(String[] args) {
int[] array = new int[]{77, 99, 33, 44 ,55, 11, 9, 101, 2};
System.out.print("排序前：");
display(array);
sort(array);
System.out.print("\r\n排序后：");
display(array);
}
输出结果：
排序前：77 99 33 44 55 11 9 101 2
排序后：2 9 11 33 44 55 77 99 101
选择排序的效率：
数据交换次数从O(N^2)变成了O(N)，但是比较次数还是O(N^2)，但是相比冒泡排序效率肯定更好的，因为交换次数少得多了
插入排序：
大多数情况下，插入排序是这三种排序算法中效率最好的，一般情况下，比冒泡排序快一倍，比选择排序也要快一点，但实现方面也要更麻烦
步骤：
1、把数组分为有序和无序两部分，默认array[0]为有序，其他为无序
2、每次把无序的一个元素插入到有序数组中
3、索引后移，知道所有的元素都变有序
图例：
代码实现：
public static int[] sort(int[] array) {
int i, j;
for (i = 1; i < array.length; i++) { //循环比较的次数，默认从1开始
int temp = array[i]; //先保存要插入的元素
j = i;
while (j > 0 && temp < array[j-1]) { //要插入的元素小于之前的元素，循环直到temp找到要插入的位置
array[j] = array[j-1]; //将之前的元素后移一位
j--; //索引前移一位
}
array[j] = temp; //把temp插入到要插入的位置，也就是第一个大于temp的元素的后面
}
return array;
}
public static void display(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void main(String[] args) {
int[] array = new int[]{77, 99, 33, 44 ,55, 11, 9, 101, 2};
System.out.print("排序前：");
display(array);
sort(array);
System.out.print("\r\n排序后：");
display(array);
}
输出结果：
排序前：77 99 33 44 55 11 9 101 2
排序后：2 9 11 33 44 55 77 99 101
插入排序的特点：
比较次数：1+2+3+...+N-1=N*(N-1)/2
每一轮排序发现插入点之前，平均只有全体数据项的一半进行比较，所以是N*(N-1)/4
复制的次数和比较的次数几乎相同。然而，复制和交换的效率是不同的，所以，插入算法比比冒泡排序快一倍，比选择排序也要快一点
对于有序或基本有序的数据来说，插入排序的效率很好，因为while循环总是false，只是外层的循环而已，时间复杂度O(N)
如果是逆序数据，效率和冒泡排序差不多
内容参考：<Java数据结构和算法>
未完待续。。。