【数据结构入门】排序算法：插入排序
目录
1.排序的概念
1.1 常见的排序算法
2. 插入排序
2.1 插入排序的思想
2.2 代码逻辑
单趟排序：
多趟排序：
2.3 代码：
2.4 测试：
1.排序的概念
所谓排序，是一串记录，按照其中的某个或者某些关键字的大小，递增或者递减的排列起来的操作。
稳定性：
假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录相对次序不变，在原序列中,r[i] = r[j]，且r[i]在r[j]之前，在排序之后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的，否则称之为不稳定的。
内部排序：数据元素放在内存中排序。
外部排序：数据元素大多不同时放在内存中，根据排序的过程的要求不能在内外存之间移动数据的排序。
1.1 常见的排序算法
常见的排序算法分为四大类：插入排序、选择排序、交换排序、归并排序。本文将按照顺序进行学习，由于排序的内容过多，这里会拆分成若干章节进行学习。
2. 插入排序
2.1 插入排序的思想
如果各位玩过扑克牌，那么整理扑克牌的时候其实就是插入排序，每一张牌对每一个位置进行比较，如果遇到合适的位置，那么就进行插入。具体流程如下：
①首先默认将第一个数作为有序的数，那么有序区间就是5；
②从第二个数字开始，对有序区间的数字进行比较，如果比有序区间的数字要小，那么就放在该数字之前；
③每次将非有序区的数字进行插入的时候，有序区的范围就会扩大一个数字；
④循环往复，最终所有数字都在有序区内。
2.2 代码逻辑
单趟排序：
在[0,end]中间插入，保证0-end是有序的；将end+1位置的元素进行插入到[0,end]；
①首先定义指针end，存储end+1所指的数字为tmp；
②当tmp比指针所指向的数要小的时候，这个数需要后移一位，此时就会覆盖tmp，这就是为何要提前保存的原因。
③后移的过程是持续的，只要end指向的数字比tmp要大，那么就需要后移；
④如果tmp比end指向的数字要大，说明此时tmp应该存放在end+1的位置上。
多趟排序：
我们注意观察end下标为0的时候，此时有序区的范围是0,；
当下标增加的时候，有序区的范围也不断增加，最后end应该在倒数第二个位置，所以end的范围是0-n-2。（n是数组的长度）
2.3 代码：
// 插入排序
void insertSorted(int* arr,int size)
{// 多趟排序for (size_t i = 0; i < size - 1; i++)// i最多在倒数第二个位置上{// 单趟排序int end = i;// 0开始到倒数第二个元素int tmp = arr[end + 1];// 存储最后一个元素防止被覆盖// 后移元素while (end >= 0){if (tmp < arr[end]) // 若tmp比指针所指位置更小，那么该元素后移{arr[end + 1] = arr[end];--end;}else{// 如果当前元素比tmp还要小，那么就不用后移了break;}}// 此时退出循环两种情况// 情况1：所有的数字都比tmp大，end下标为-1// 情况2: 找到了一个数字比tmp小// 这两种情况都需要将end+1的位置给tmparr[end + 1] = tmp;}}
2.4 测试：
void printArr(int* arr,int size)
{for (int i = 0; i < size; i++){printf("%d ",arr[i]);}
}// 测试插入排序
void test1()
{int arr[] = {3,1,4,1,7,9,8,2,0,5};insertSorted(arr, sizeof(arr) / sizeof(arr[0]));printArr(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{test1();
}