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

古城微笑少年丶 2022-10-09 12:06 130阅读 0赞

### 文章目录 ###

*   *  一、直接插入排序
     *  二、冒泡排序

## 一、直接插入排序 ##

**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 <iostream>
    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<L.length; i++)  //从1到10的正负摆动交叉数列 
    	{ 
    		L.R[i].key= i*flag;  //初始化为： 下标乘标志位 开始的数字
    		flag*=-1;  //每次变一次号 
    	}
    } 
    
    //对顺序表进行直接插入排序
    void InsertSort(SqList &L)
    { 
    	int i, j;  //遍历 
    	for(i=2; i<=L.length; i++) //不断遍历比较 
    	{ 
    		if(L.R[i].key<L.R[i-1].key)  //若前一个比后一个大，则需要重新排序小的那个数 
    		{ 
    			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<L.R[j].key; j--)  //（小的那个数）从后往前寻找插入位置 
    				L.R[j+1]= L.R[j];   //记录逐个后移，直到找到能够插入的位置 
    			L.R[j+1]= L.R[0];  //将小的那个数插入到那个位置 
    		}
    	}
    } 
    
    int main()
    { 
    	int i;  //遍历
    	 
    	SqList sq;  //初始化顺序表
    	Init_SqList(sq);
    	cout << "原表： ";
    	for(i=1; i<sq.length; i++)   //第0个是监视哨，不需要输出 
    		cout << sq.R[i].key << " "; 
    	cout << endl;
    	
    	InsertSort(sq);  //对顺序表进行插入排序
    		
    	//输出顺序表的元素 
    	cout << "排序后：";
    	for(i=1; i<sq.length; i++)  //第0个是监视哨，不需要输出 
    		cout << sq.R[i].key << " ";
    }

![1-1][]

## 二、冒泡排序 ##

**1、算法思想：** 依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。  
1）第一次比较，首先比较第一和第二个数，将小数放在前面，将大数放在后面。

2）比较第2和第3个数，将小数 放在前面，大数放在后面。

3）)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成。

4）在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。

5）在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

6）依次类推，每一趟比较次数减少依次。

**2、C++代码实现（核心在BubbleSort函数中）**

#include <iostream>
    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<L.length; i++)  //从1到10的正负摆动交叉数列 
    	{ 
    		L.R[i].key= i*flag;  //初始化为： 下标乘标志位 开始的数字
    		flag*=-1;  //每次变一次号 
    	}
    } 
    
    void BubbleSort(SqList &L)
    { 
    	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; j<=m; j++)
    			if(L.R[j].key>L.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 << "原表： ";
    	for(i=1; i<sq.length; i++)   //第0个是监视哨，不需要输出 
    		cout << sq.R[i].key << " "; 
    	cout << endl;
    	
    	BubbleSort(sq);  //对顺序表进行冒泡排序 
    	
    	//输出顺序表的元素 
    	cout << "排序后：";
    	for(i=1; i<sq.length; i++)  //第0个是监视哨，不需要输出 
    		cout << sq.R[i].key << " ";
    }

![2-1][]

[1-1]: /images/20221005/46bae9b04d1943af96486d60ec377890.png
[2-1]: /images/20221005/81487bdb8c2a423cb9b4b984de79da1e.png