六大排序思路整理+代码
1、冒泡排序
2、选择排序
3、插入排序
原理
把4插入到有序数列[ 1、3、5 ]中还要使其有序。
从左往右的话，只需要找到第一个大于4的数，把4放在它的前面。
从右往左的话，只需要找到第一个小于4的数，把4放在它的后面。
初始有一组8个数字的无序数列：
插入排序就是利用这种思想，把数一个个插入使整个数列有序。
-
第一轮插入：
第一个数47只有一个数所以是有序数列，把58看成等待插入的数。
47 < 58，将58插入到47的后面，即不用动就已经是有序的了。 -
第二轮插入：
[ 47、58 ]是有序数列，把87看成等待插入的数。
58 < 87,将87插入到58的后面，也是不用动就已经有序了。 -
第三轮插入：
[ 47、58、87 ]是有序数列，把89看成等待插入的数。
87 < 89,将89插入到87的后面，还是不用动就有序了！凸(艹皿艹 ) -
第四轮插入：
[ 47、58、87、89 ]是有序数列，把43看成等待插入的数。终于！
先保存一份43。
43 < 89，让89往后覆盖
43 < 87，让87往后覆盖
43 < 58，让58往后覆盖
43 < 47，让47往后覆盖
已经到第一位置了，没有比43更小的了，43就是现在最小的，插入到第一的位置。 -
第五轮插入：
保存一份68，68 < 89，89往后覆盖
68 < 87，87往后覆盖
68 > 58，找到了第一个小于68的数，插在它的后面，使数列继续有序 -
第六轮插入：
2 < 89 ，覆盖
2 < 87 ，覆盖
2 < 68 ，覆盖
2 < 58 ，覆盖
2 < 47 ，覆盖
2 < 43 ，覆盖
到了第一位置，没有更小，插入位置1 -
第七轮插入：
61 < 89，覆盖
61 < 87，覆盖
61 < 68，覆盖
61 > 58，找到第一个小于61的数，在它后面插入
代码实现
//第1个数(下标为0)看作是有序数列,从第2个数开始插入到前面的有序数列中
for (int i = 1; i <N; i++) {
//前一个数小于后一个数，就直接插下一个数了
if(arr[i-1] < arr[i]){
continue;
}
//保存下标为i的数
int j,t = arr[i];
//从i-1到0找出第一个小于t的数
for (j = i-1; j>=0 && t < arr[j] ; j--) {
//小于就覆盖掉后面一个数
arr[j+1] = arr[j];
}
//插入
arr[j+1] = t;
}