插入排序

171 161 163 165 167 169

1. 首先, 我们只考虑第一个元素,从第一个元素 171 开始，该元素可以认为已经被排序；
   171 161 163 165 167 169
2. 取下一个元素 161 并记录，并让 161 所在位置空出来,在已经排序的元素序列中从后向前扫
   描；
   171 163 165 167 169
3. 该元素（171）大于新元素，将该元素移到下一位置；
   171 163 165 167 169
4. 171 前已经没有最大的元素了, 则将 161 插入到空出的位置
   161 171 163 165 167 169
5. 取下一个元素 163，并让 163 所在位置空出来,在已经排序的元素序列中从后向前扫描；
   161 171 165 167 169
6. 该元素（171）大于新元素 163，将该元素移到下一位置
   161 171 165 167 169
7. 继续取 171 前的元素新元素比较, 直到找到已排序的元素小于或者等于新元素的位置；新
   元素大于 161,则直接插入空位中
   161 163 171 165 167 169
8. 重复步骤 2~7，直到完成排序
   161 163 165 167 169 171
   插入排序: 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，
   找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间
   的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供
   插入空间。

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
   重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
4. 将新元素插入到该位置；
   重复步骤 2~5。

include <stdio.h>
#include <stdlib.h>
void InsertSort(int arr[], int len){//插入排序
int preIndex = 0, current = 0;
for(int i=1; i<len; i++){
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current){
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}

arr[preIndex + 1] = current;
}
}
int main(void){
int beauties[]={163, 161, 158, 165, 171, 170, 163, 159,
162};
int len = sizeof(beauties)/sizeof(beauties[0]);
InsertSort(beauties, len);
printf("美女排序以后的结果是:\n");
for(int i=0; i<len; i++){
printf("%d ", beauties[i]);
}
system("pause");
return 0;
}