算法学习笔记----插入排序
一、算法描述
插入排序是一种比较直观的排序算法，其思想是：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，直到找到一个合适和位置并插入。具体算法描述如下（升序排列）：
1. 从第一个元素开始，该元素可以认为已经是排好序的了
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一个位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 如果找到小于或者等于新元素的位置，则将新元素插入到该位置后面；如果没有找到，则放在第一个位置
6.重复步骤2~5
如下图所示：
二、算法实现
代码如下所示：
#include <stdio.h>#include <errno.h>int insertsort(int *source, int n){ int i, j; int key; if (!source || n <=0) { fprintf(stderr, "Invalid argument.\n"); return -EINVAL; } for (i = 1; i < n; ++i) { key = source[i]; j = i - 1; while ((j >= 0) && (source[j] > key)) { source[j + 1] = source[j]; --j; } source[j + 1] = key; } return 0;}#define ARRAY_SIZE(__s) (sizeof(__s) / sizeof(__s[0]))int main(void){ int source[] = { 7, 5, 2, 4, 6, 1, 3}; int i; printf("Before sort: "); for (i = 0; i < ARRAY_SIZE(source); ++i) { printf("%d ", source[i]); } printf("\n"); insertsort(source, ARRAY_SIZE(source)); printf("After sort: "); for (i = 0; i < ARRAY_SIZE(source); ++i) { printf("%d ", source[i]); } printf("\n"); return 0;}三、算法分析
如果输入的数组已经是排好序的，则插入排序不需要移动任何元素，这种情况是插入排序的最好情况，时间复杂度为O(n)；若输入数组已反向排序，即按递减顺序排好序，则导致最坏情况，时间复杂度为O(n^2）。“平均情况”往往和最坏情况大致一样差，时间复杂度是O(n^2)。插入排序是就地排序，除了一个临时变量来存储当前要插入的元素外，不需要额外的空间，因此空间复杂度为O(1)。