直接插入排序、冒泡排序实验详解【数据结构实验报告】

2024-07-09 06:58| 来源: 网络整理| 查看: 265

文章目录一、直接插入排序二、冒泡排序

一、直接插入排序

1、算法思想直接插入排序（straight insertion sort），有时也简称为插入排序，是减治法的一种典型应用。其基本思想如下：对于一个数组A[0,n]的排序问题，假设认为数组在A[0,n-1]排序的问题已经解决了。考虑A[n]的值，从右向左扫描有序数组A[0,n-1]，直到第一个小于等于A[n]的元素，将A[n]插在这个元素的后面。很显然，基于增量法的思想在解决这个问题上拥有更高的效率。

2、直接插入的效率和特点直接插入排序对于最坏情况（严格递减的数组），需要比较和移位的次数为n(n-1)/2；对于最好的情况（严格递增的数组），需要比较的次数是n-1，需要移位的次数是0。当然，对于最好和最坏的研究其实没有太大的意义，因为实际情况下，一般不会出现如此极端的情况。然而，直接插入排序对于基本有序的数组，会体现出良好的性能，这一特性，也给了它进一步优化的可能性。直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1)，同时也是稳定排序。

3、举例现有一个无序数组，共7个数：89 45 54 29 90 34 68。使用直接插入排序法，对这个数组进行升序排序。 89 45 54 29 90 34 68

45 89 54 29 90 34 68

45 54 89 29 90 34 68

29 45 54 89 90 34 68

29 34 45 54 89 90 68

29 34 45 54 68 89 90

4、C++代码实现（核心在InsertSort函数中）

#include using namespace std; typedef int KeyType; //给int的别名KeyType typedef int InfoType; //给int的别名InfoType //数据元素类型定义 typedef struct { KeyType key; //定义数据的关键字域 InfoType otherinfo; //定义数据的其他域 } ElemType; //数据元素类型名 //顺序表定义 typedef struct { ElemType R[11]; //存储空间的基地址（用R[]数据可以正常输出） int length; //顺序表的长度 }SqList; //表类型名 //顺序表的初始化 void Init_SqList(SqList &L) { int i, flag=-1; L.length= 11; //表长设为10+1，因为需要留一个监视哨R[0]的位置 //设置表的前10个数据元素值（无序） for(i=1; i int i, j; //遍历 for(i=2; i L.R[0]= L.R[i]; //将待插入的记录暂存到监视哨中（中间变量R[0]） L.R[i]= L.R[i-1]; //R[i-1]（大的那个数）需要向后移一位 for(j=i-2; L.R[0].key KeyType key; //定义数据的关键字域 InfoType otherinfo; //定义数据的其他域 } ElemType; //数据元素类型名 //顺序表定义 typedef struct { ElemType R[11]; //存储空间的基地址（用R[]数据可以正常输出） int length; //顺序表的长度 }SqList; //表类型名 //顺序表的初始化 void Init_SqList(SqList &L) { int i, flag=-1; L.length= 11; //表长设为10+1，因为需要留一个监视哨R[0]的位置 //设置表的前10个数据元素值（无序） for(i=1; i int m= L.length-1; //从后往前进行排序 int flag=1; //用flag来标记某一趟排序是否发生交换 int j; //遍历 ElemType t; //中间变量 while((m>0) && (flag==1)) //总共进行m趟排序 { flag= 0; //flag置零表示初始每一趟都表示没有交换，则不会执行下趟排序 for(j=1; jL.R[j+1].key) //若前面的大于后面的 { flag= 1; //已经发生排序 //交换两个记录的前后顺序 t=L.R[j]; L.R[j]=L.R[j+1]; L.R[j+1]= t; } --m; //向前继续排序 } }

3、测试部分

int main() { int i; //遍历 SqList sq; //初始化顺序表 Init_SqList(sq); cout

【本文地址】

公司简介

联系我们