插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
插入排序算法描述:
1、从第一个元素开始,该元素可以认为已经被排序;
2、取出下一个元素,在已经排序的元素序列中从后向前扫描;
3、如果该元素(已排序)大于新元素,将该元素移到下一位置;
4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5、将新元素插入到该位置后;
6、重复步骤2~5。
一、 插入排序源码
#include <stdio.h> #include <stdlib.h> #include <time.h> #define NUM 10 // 插入排序函数实现 void insertion_sort(int a[], int n) { for(int i=1; i<n; i++) { int j, temp = a[i]; for(j=i; j>0&&a[j-1]>temp; j--) { a[j] = a[j-1]; } a[j] = temp; } } int main(void) { int array[NUM]; srand((unsigned int)time(NULL)); // 给数组赋随机值 for(int i=0; i<NUM; i++) { array[i] = rand()%100; } // 打印排序前数组 for(int i=0; i<NUM; i++) { printf("%5d", array[i]); } printf("\n"); // 插入排序 insertion_sort(array, NUM); // 打印排序后数组 for(int i=0; i<NUM; i++) { printf("%5d", array[i]); } printf("\n"); return 0; }
二、 运行结果
[root@fedora Workspace]# gcc insertion_sort.c -o insertion_sort -Wall [root@fedora Workspace]# ./insertion_sort 45 71 94 18 64 66 3 49 59 27 3 18 27 45 49 59 64 66 71 94 [root@fedora Workspace]# ./insertion_sort 3 86 38 58 40 2 62 76 86 66 2 3 38 40 58 62 66 76 86 86 [root@fedora Workspace]# ./insertion_sort 86 49 90 46 95 5 0 85 79 11 0 5 11 46 49 79 85 86 90 95 [root@fedora Workspace]# ./insertion_sort 42 79 69 68 57 88 15 54 76 35 15 35 42 54 57 68 69 76 79 88 [root@fedora Workspace]# ./insertion_sort 41 91 14 74 22 4 69 3 66 82 3 4 14 22 41 66 69 74 82 91 [root@fedora Workspace]# ./insertion_sort 95 40 78 72 96 59 5 37 34 42 5 34 37 40 42 59 72 78 95 96