1.插入排序
待排序数组从arr[1]向后遍历，“插入”是指将待排序元素插在已排序元素中某个合适的位置，其中arr[0]视作已排序元素。插入排序与打扑克牌时的理牌比较相似，但不同的是，人能一眼看出待排序的那张牌需要插入的位置，而机器需要通过不断比较大小和移动元素来达到插入的目的。顺序排序下，如果待排序元素小于前一个元素，则将前一个元素向后移动一位，否则进入到下一个待排序元素的操作中直至排序完成。
插入排序.gif
python实现：
def insert_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >=0 and key < arr[j] :
arr[j + 1] = arr[j] # 等同于将arr[j]向后移一位
j -= 1
arr[j+1] = key
c++实现：
void insert_sort2(int arr[], int len){
clock_t time_start=clock();
for(int i=1;i<len;i++){
int key = arr[i];
int j = i-1;
while(j>=0 && (key < arr[j])){
arr[j+1] = arr[j]; // 等同于将arr[j]向后移一位
j--;
}
arr[j+1]=key;
}
}
2.希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序的基本思想是：先将整个数组按照间隔 gap 分成若干子序列分别进行插入排序，待整个数组"基本有序"时，再对该数组进行插入排序。
希尔排序.png
python实现：
def shell_sort(arr):
n = len(arr)
gap = int(n/2) # 先将间隔gap定位数组长度的一半
while gap > 0:
for i in range(gap, n):
key = arr[i]
j = i - gap
while j >= 0 and key < arr[j]:
arr[j+gap] = arr[j]
j -= gap
arr[j+gap] = key
gap = int(gap/2)
c++实现：
void shell_sort(int arr[], int len){
int gap = int(len/2); // 先将间隔gap定位数组长度的一半
while(gap > 0){
for(int i=gap;i<len;i++){
int key = arr[i];
int j = i - gap;
while(j>=0 && key<arr[j]){
arr[j+gap] = arr[j];
j -= gap;
}
arr[j+gap] = key;
}
gap = int(gap/2);
}
}
