逍遥游

插入排序------基本有序序列的最佳选择

插入排序(Insertion Sort)是又一经典排序算法,因每次将一个新元素插入到有序序列并保持序列有序而得名。插入排序是处理基本有序序列的最佳选择。

算法原理/步骤

  1. 从序列中取出第一个元素,形成一个有序序列;
  2. 从待排序序列中取出下一个元素,从有序序列尾部向前开始检索,找到一个位置,使得将新元素放在该处后,仍然有序;
  3. 将该元素插入到该位置
  4. 重复过程2、3,直到取完所有元素;
    Insertion_sort
    (来自维基百科)

时间复杂度

从算法原理中可以看到,每次只对一个元素进行排序,故原序列第K个位置上的元素最多需要K次比较和1次赋值、最少1次比较和1次赋值即可完成,故时间复杂度最快为O(N),最差为O(N^2),平均为O(N^2)。注:最好情况:序列有序;最坏:序列逆序。

稳定性

插入排序中元素间交换不是跳跃性的,所以是稳定的排序。

算法演示

下面给出是对某组数据进行排序的过程演示。(还是维基的)

插入排序演示

注:演示的过程与文中所给代码有些许差异,在于图片中先找到位置再插入,而文中代码则是一边检索位置一边交换。对应的代码请点击查看查看。

更加高大上的演示,请猛击这里

实例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
#define MAXN 10
int insert_sort(int *, int);
int main()
{
int src[MAXN];
for(int i=0; i<MAXN; i++)
src[i] = rand()%10000;//先随机生成MAXN个数字,做测试用
for(int i=0; i<MAXN; i++)
cout<<src[i]<<" ";
cout<<endl;//输出原始数据
//执行插入排序
insert_sort(src, MAXN);
/*检查排序结果*/
for(int i=0; i<MAXN-1; i++)
{
if(src[i]>src[i+1]){
cout<<"wrong"<<endl;
}
}
cout<<"sort finished!"<<endl;
return 0;
}
int insert_sort(int *src, int size)
{
for(int i=0; i<size; i++)
{
//从第一个元素开始,每次取出一个加入到有序序列中
int j=i;
while(j<0 && c[j-1])
{
//找到新元素在有序序列中的位置
swap(src[j], src[j-1]);
j--;
}
}
return 0;
}

算法改进

  1. 文中给出的代码在处理每一个元素时,都会经过最多i次比较、K次交换(3次赋值)。可以通过先比较得出位置再赋值的办法来减少赋值(K+1次交换)。
  2. 检索位置过程中利用二分查找可以减少一定次数的比较。
  3. 添加哨兵节点(即在序列头加入一个无穷小的元素),减少越界判断操作。(想出这办法的人一定是疯了)

总结

插入排序算法是一种思想简单明了的算法,在处理一些基本有序的序列上甚至优于其他算法,例如快速排序

详细代码请点击这里查看。


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com