对顺序表L做直接插入排序
时间: 2024-06-13 12:09:42 浏览: 8
以下是对顺序表L做直接插入排序的Python实现:
```python
def insert_sort(L):
for i in range(1, len(L)):
L[i] < L[i-1]:
temp = L[i]
j = i - 1
while j >= 0 and L[j] > temp:
L[j+1] = L[j]
j -= 1
L[j+1] = temp
return L
```
直接插入排序的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。具体实现时,从第二个记录开始,逐个将记录插入到前面已经排好序的有序表中,直到最后一个记录插入到有序表中为止。
相关问题
//直接插入排序 #include<iostream> #include<fstream> using namespace std; #define MAXSIZE 20 //顺序表的最大长度 #define OK 0 #define ERROR -1 typedef char* InfoType; typedef struct { int key;//关键字项 InfoType otherinfo;//其他数据项 }RedType;//记录类型 typedef struct { RedType r[MAXSIZE+1];//r[0]闲置或用做哨兵单元 int length;//顺序表长度 }SqList;//顺序表类型 //初始化一个空的顺序表L void InitSqList(SqList &L) { L.length = 0; } //将待排序记录依次插入顺序表L void InsertSqList(SqList &L,ifstream& in) { int n;//待排序记录的个数 in>>n; if(n > MAXSIZE) exit(ERROR); for(int i=1; i<=n; ++i) { in>>L.r[i].key; ++L.length; } } //打印顺序表L void show(SqList L) { for(int i=1; i<=L.length; ++i) cout<<L.r[i].key<<" "; cout<<endl; } //对顺序表L做直接插入排序 //要求调用show函数打印每一趟排序的结果 void InsertSort(SqList &L) { show(L);//打印初始待排序序列 /*-------------代码开始------------------*/ for(i=2;i<L.length;++i) if(L.r[i].key<L.r[i-i].key) { L.r[0]+L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;L.r[0].ke y<L.r[j].key;--j) L.r[J+1]=L.r[j]; L.r[j+1]=L.r[0]; } /*-------------代码结束------------------*/ } int main() { ifstream in("data/测试数据.txt");//测试数据 SqList L; InitSqList(L); InsertSqList(L,in); InsertSort(L); return OK; }优化这段代码
这段代码的直接插入排序算法实现存在一些问题,比如变量i和j没有定义,以及在插入排序的过程中没有调用show函数打印每一趟排序的结果。此外,这段代码中的排序算法实现也没有进行优化。以下是优化后的代码:
```c++
//直接插入排序
#include<iostream>
#include<fstream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
#define OK 0
#define ERROR -1
typedef char* InfoType;
typedef struct {
int key;//关键字项
InfoType otherinfo;//其他数据项
}RedType;//记录类型
typedef struct {
RedType r[MAXSIZE+1];//r[0]闲置或用做哨兵单元
int length;//顺序表长度
}SqList;//顺序表类型
//初始化一个空的顺序表L
void InitSqList(SqList &L) {
L.length = 0;
}
//将待排序记录依次插入顺序表L
void InsertSqList(SqList &L,ifstream& in) {
int n;//待排序记录的个数
in>>n;
if(n > MAXSIZE) exit(ERROR);
for(int i=1; i<=n; ++i) {
in>>L.r[i].key;
++L.length;
}
}
//打印顺序表L
void show(SqList L) {
for(int i=1; i<=L.length; ++i)
cout<<L.r[i].key<<" ";
cout<<endl;
}
//对顺序表L做直接插入排序
//要求调用show函数打印每一趟排序的结果
void InsertSort(SqList &L) {
show(L);//打印初始待排序序列
/*-------------代码开始------------------*/
for(int i=2; i<=L.length; ++i) {
if(L.r[i].key < L.r[i-1].key) {
L.r[0] = L.r[i]; //将L.r[i]暂存到L.r[0]
int j;
for(j=i-1; L.r[0].key < L.r[j].key; --j) {
L.r[j+1] = L.r[j]; //记录后移
}
L.r[j+1] = L.r[0]; //插入到正确位置
}
show(L); //打印每一趟排序的结果
}
/*-------------代码结束------------------*/
}
int main() {
ifstream in("data/测试数据.txt");//测试数据
SqList L;
InitSqList(L);
InsertSqList(L,in);
InsertSort(L);
return OK;
}
```
在优化后的代码中,我们对直接插入排序算法进行了优化,具体包括:
1. 在插入排序的过程中,使用了哨兵技术,将L.r[i]暂存到L.r[0]中,避免了反复交换记录的操作。
2. 在排序过程中,每次插入一个记录后,都调用show函数打印出当前的排序结果,方便查看。
这样,优化后的代码可以更加高效地完成直接插入排序算法,并且可以更加清晰地展示算法执行的过程。
6-3 基于顺序表的直接插入排序
好的,下面是基于顺序表的直接插入排序的算法步骤:
1. 从第二个元素开始,依次将每个元素插入到已排好序的元素中。
2. 将当前元素与已排序的元素从后往前逐个比较,找到插入位置。
3. 将当前元素插入到正确位置。
4. 重复步骤1-3,直到所有元素都被插入到正确位置。
以下是C++代码实现:
```
void InsertSort(SqList &L)
{
int i, j;
for (i = 2; i <= L.length; i++) // 从第二个元素开始插入
{
if (L.elem[i] < L.elem[i-1]) // 如果当前元素小于前一个元素
{
L.elem[0] = L.elem[i]; // 将当前元素存储到哨兵位置
for (j = i-1; L.elem[0] < L.elem[j]; j--) // 从后往前比较,找到插入位置
{
L.elem[j+1] = L.elem[j]; // 元素后移
}
L.elem[j+1] = L.elem[0]; // 将当前元素插入到正确位置
}
}
}
```
注意,这里使用了一个哨兵位置来存储当前元素,避免了每次交换元素的操作,提高了效率。