插入排序是稳定的排序方法, 时间复杂度是 O(n^2)
最坏情况 (完全逆序的情况)O(n^2), 最好情况 (完全顺序的情况)O(n), 平均情况 O(n^2),
所以十分适用于基本有序的数组
直接插入排序
- void Insert_Sort(int *a,int n)
- {
- int i,j;
- for(i=1; i<n; i++)
- {
- if(a[i]<a[i-1])
- {
- int t=a[i];
- for(j=i-1; j>=0&&a[j]>t; j--)
- {
- a[j+1]=a[j];
- }
- a[j+1]=t;
- }
- }
- }
二分优化
二分优化指的是通过二分查找的方式快速找到需要插入的位置, 但是插入的方式还是需要一个个的移动元素, 所以优化的只是少一些比较元素大小的步骤
- // 二分优化
- void Insert_Sort_Binary(int *a,int n)
- {
- for(int i=1; i<n; i++)
- {
- if(a[i]<a[i-1])
- {
- int left=0;
- int right=i-1;
- int t=a[i];
- // 利用二分查找的方法快速找到应该插入的位置, 可以少进行一些比较, 但是需要进行的移动次数还是一样的, 所以优化的效果还是有限的
- while(left<=right)
- {
- int mid=(left+right) / 2;
- if(a[mid]>t)
- right=mid-1;
- else
- left=mid+1;
- }
- for(int j=i-1; j>=left; j--)
- {
- a[j+1]=a[j];
- }
- a[left]=t;
- }
- }
- }
插入排序的另一种优化就是希尔排序
来源: http://www.jianshu.com/p/fc2a0a1cbd4b