这是排序算法中最常见的排序方法，也是初学者使用最多的。有时候我们在生活中也会不自觉地用到插入排序，例如：
给手里的牌排序
这是最常见的例子之一，我们通常从纸牌的一边开始看，找到一张位置不正确的，把它拿出来，再从开始的位置开始找，直到找到合适者张牌插入的位置。
假设手里有这几张牌2，4，6，3，10，K，J。排序的步骤如下：
- 假设我们从左边开始看，2位置正确，4位置正确，6位置正确，3错误，他比前面的6要小。
- 需要给3重新找到正确位置。
- 取出3这张牌，冲头开始看，3比2大，再往后，3比4小，因此3插入2和4之间的位置。现在纸牌的顺序变成了2，3，4，6，10，K，J。
- 接着上次我们离开的点开始看（就是3的位置，现在变成了6），6位置正确，10位置正确，K位置正确，J位置不正确，因为他比前面的K小。
- 把J拿出来，重头开始看，J比2，3，4，6，10都大，比K小，因此插在10和K之间。
排序就完成了，手里的纸牌也变成了正确的顺序，这种方法就叫做插入排序。
相应的算法设计：
- Start scanning the elements from 2nd position. The 1st is assumed to be at correct place.
- if ( arr[i] < arr[i-1])
- Swap arr[i] and arr[i-1]
- Keep swapping until the number is less than the previous number
- The array gets sorted as we reach the end.
下面是具体执行代码：
#include<stdio.h> // function to swap two integers
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
} // a function to perform Insertion Sort on the array arr with size specified
void insertionSort(int arr[],int size)
{
int i,j; // iterating from 2nd element to the last
for(i=1;i<size;i++)
{
if(arr[i] < arr[i-1])
{
j = i;
while(arr[j-1] > arr[j])
{
// swapping all the numbers
// until the next number is smaller than previous number
swap(&arr[j],&arr[j-1]);
j--;
}
}
}
} // driver function to test the above function
int main(void)
{
int i;
int arr[10] = {3, 4, 7, 1, 10, 8, 2, 22, 99, 50}; insertionSort(arr,10); printf("SORTED array:- ");
for(i=0;i<10;i++)
printf("%d ",arr[i]); return 0;
}
时间复杂度：
Average Case:- O(n2)
Best Case:- O(n)
Worst Case:- O(n2)