selection sort
一个指针从数组开头i开始，从左向右扫描数组的最小值，找到后将其位置与i交换，指针指向i+1，继续选择
完成一次后 0~i 应当是有序的 i+1~n-1可能是无序的
具有O(N^2)的时间复杂度以及最小的移动开销
insertion sort
优于处理部分有序。
首先我们假设 0~i 应当是排好序的， i+1~n-1则是未查看的。每次将i右移，即加入新的元素到sorted序列中（新加入的元素一开始肯定在这个序列的末端），将这个元素不断与左边相邻元素比较、交换，直到左边的元素都比之更小。
具有O(1/4 * N^2 )访问以及O（1/4 * N^2）的交换，两倍效率于selection sort
shell sort
优于处理中等长度数组。
插入排序的缺点在于一次交换只移动了一个位置。以此点改进得到shell sort。首先选择一段序列，如：1 4 13 40 (h = 3 * h + 1)作为排列得不同层次。然后对待排序数组以此作 h-sort （从0号元素开始，间隔h的子数组做插入排序）直到 1-sort，h从上述序列中递减，h < N。
对于上述序列，有最坏的比较次数O(N^3/2)
对于一个h-sort的数组再选择一个k做k-sort，得到的数组仍是h-有序的。
关于序列的选择：1~2^i NO, 1~2i+1 maybe, 1~3i+1 ok.