查找与排序-插入排序
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
插入排序是一种简单直观的排序算法，其基本思想是将未排序的元素逐个插入到已排序的部分中，直到所有元素都被插入到合适的位置为止。
算法步骤：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5，直到所有元素都被排序。
假设我们有以下待排序的数组：[5, 3, 8, 6, 2]
- 初始状态：[5, 3, 8, 6, 2]
- 第一轮：将3插入到已排序部分[5]中，得到[3, 5, 8, 6, 2]
- 第二轮：将8插入到已排序部分[3, 5]中，得到[3, 5, 8, 6, 2]
- 第三轮：将6插入到已排序部分[3, 5, 8]中，得到[3, 5, 6, 8, 2]
- 第四轮：将2插入到已排序部分[3, 5, 6, 8]中，得到[2, 3, 5, 6, 8]
最终，数组变为有序状态：[2, 3, 5, 6, 8]
/* 插入排序 */
void insertion_sort(int arr[], int len){
int i,j,key;
for (i=1;i<len;i++){
key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}