直接插入排序算法演示.ppt

直接插入排序算法演示
void InsertSort(SqList &L)
{//对顺序表L做直接插入排序
for(i=2;i<=;++i)
if([i].key<[i-1].key)//待排序记录关键字<有序序列最后一个记录关键字
{ [0] =[i];//待排序记录复制为哨兵
[i]=[i-1];
for(j=i-2;LT([0].key,[j].key);--j)//记录后移
[j+1]=[j];
[j+1]=[0];//R[i]插入到正确位置
}
}
0 1 2 3 4 5 6 7 8
49
38
65
97
76
13
27
49
i=2
i
假设有序队列中已经有一个元素
直接插入排序算法演示
void InsertSort(SqList &L)
{//对顺序表L做直接插入排序
for(i=2;i<=;++i)
if([i].key<[i-1].key)//待排序记录关键字<有序序列最后一个记录关键字
{ [0] =[i];//待排序记录复制为哨兵
[i]=[i-1];
for(j=i-2;LT([0].key,[j].key);--j)//记录后移
[j+1]=[j];
[j+1]=[0];//R[i]插入到正确位置
}
}
0 1 2 3 4 5 6 7 8
49
38
65
97
76
13
27
49
i=2
i
直接插入排序算法演示
void InsertSort(SqList &L)
{//对顺序表L做直接插入排序
for(i=2;i<=;++i)
if([i].key<[i-1].key)//待排序记录关键字<有序序列最后一个记录关键字
{ [0] =[i];//待排序记录复制为哨兵
[i]=[i-1];
for(j=i-2;LT([0].key,[j].key);--j)//记录后移
[j+1]=[j];
[j+1]=[0];//R[i]插入到正确位置
}
}
0 1 2 3 4 5 6 7 8
49
38
65
97
76
13
27
49
i=2
38
i
直接插入排序算法演示
void InsertSort(SqList &L)
{//对顺序表L做直接插入排序
for(i=2;i<=;++i)
if([i].key<[i-1].key)//待排序记录关键字<有序序列最后一个记录关键字
{ [0] =[i];//待排序记录复制为哨兵
[i]=[i-1];
for(j=i-2;LT([0].key,[j].key);--j)//记录后移
[j+1]=[j];
[j+1]=[0];//R[i]插入到正确位置
}
}
0 1 2 3 4 5 6 7 8
49
49
65
97
76
13
27
49
i=2
38
i
直接插入排序算法演示
void InsertSort(SqList &L)
{//对顺序表L做直接插入排序
for(i=2;i<=;++i)
if([i].key<[i-1].key)//待排序记录关键字<有序序列最后一个记录关键字
{ [0] =[i];//待排序记录复制为哨兵
[i]=[i-1];
for(j=i-2;LT([0].key,[j].key);--j)//记录后移
[j+1]=[j];
[j+1]=[0];//R[i]插入到正确位置
}
}
0 1 2 3 4 5 6 7 8
49
49
65
97
76
13
27
49
i=2
38
i
j
直接插入排序算法演示
void InsertSort(SqList &L)
{//对顺序表L做直接插入排序
for(i=2;i<=;++i)
if([i].key<[i-1].key)//待排序记录关键字<有序序列最后一个记录关键字
{ [0] =[i];//待排序记录复制为哨兵
[i]=[i-1];
for(j=i-2;LT([0].key,[j].key);--j)//记录后移
[j+1