选择排序：每次从待选数据中选出最小的，与未排序序列首元素交换。
它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。
// 插入排序: 前身。
> 从未排序元素中，取第一个插入到已排序集合的合适位置。
void insertSort(int arr[], int len) {
for(int i = 1; i<len; i++) { // 外层循环
for(int j = i; j>0; j--) {
if(arr[j] < arr[j-1]) {
swap(arr[j], arr[j-1]); // 交换元素
} else {
break; // 前面的已排序，提前结束内层循环
}
}
}
}
希尔排序shellInsertSort。对插入排序的又一个优化。对插入排序的分组。
希尔排序，在一个接近排好序的情况下，能减少往后挪动交换，所以比插入排序快。
比前面的几个排序(插入，冒泡，选择排序)，性能更加高。
但是如果数据本身已经接近排好序，使用插入排序效率更高。因为已经接近排序的，再进行分组意义不大。
算法复杂度：
步长如何计算：
思想：对插入排序分组，分治思想。
分治：归并，快速排序。
原数据：1,8,6,7, 4,3,9,10
分成四组8/4=2 每组2个： 1,4一组; 8,3一组; 6,9一组; 7,10一组。就行插入排序，
插入排序后变成：1,3,6,7, 4,8,9,10
再分组8/2=4 每组4个： 1,6,4,9一组; 3,7,8,10一组。
插入排序变成： 1,3,4,7, 6,8,9,10. 接近有序的数组。
再分组：8/1=8 每组8个数据：在进行最后一次希尔排序（完全的希尔排序）--> 相当于插入排序。
// 希尔排序，对插入排序进行分组。不断减小步长。
void shellInsertSort(int arr[], int len) {
int increment = len/2; // 分为4组数据. 4=8/2
int i, j, k;
while(increment > 0) {
// 希尔排序
for( i=0; i<increment; ++i) {
for(j = i+increment; j < len; j += increment) {
int tmp = arr[j];
for(k=j; k>i && arr[k-increment] > tmp; k -= increment) {
// 往后挪动。大元素往后移动。
arr[k] = arr[k-increment];
}
arr[k + increment] = tmp; // 当前这个，赋值temp
}
}
increment /= 2; // 步长继续除2
}
}
希尔排序步骤：
- 间隔分组(通常为总长度的一般)；
- 分组的组内排序；
- 重新设定间隔分组(为前一次分组的一半)；
- 当间隔最终变为1，数据已接近排好序，使用插入排序。
