赞
踩
问题:
对待排序的数组r[1..n]中的元素进行直接插入排序,得到一个有序的(从小到大)的数组r[1..n]。
算法思想:
1、设待排序的记录存放在数组r[1..n]中,r[1]是一个有序序列。
2、循环n-1次,每次使用顺序查找法,查找r[i](i=2,..,n)在已排好的序列r[1..i-1]中的插入位置,然后将r[i]插入表长为i-1的序列r[1..i-1],直到将r[n]插入表长为n-1的有序序列r[1..n-1],最后得到一个表长为n的有序序列。
图解:
代码:
- #include<iostream>
- using namespace std;
- #define MAXSIZE 20//顺序表的最大长度
- typedef int KeyType;//定义关键字类型为整型
- typedef int InfoType;
- typedef struct
- {
- KeyType key;//关键字项
- InfoType otherinfo;//其他数据项
- }RedType;
- typedef struct
- {
- RedType r[MAXSIZE+1];//r[0]闲置或做哨兵单元
- int length;//顺序表的长度
- }SqList;//顺序表类型
-
- void InsertSort(SqList &L)//对顺序表L做直接插
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。