数据结构之排序（期末复习）

我不是女神ヾ 2023-02-22 10:59 93阅读 0赞

**【知识框架】**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]  
ps:文末有惊喜

# 一、基本概念和排序方法概述 #

### 1、排序的基本概念 ###

**排序**是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。  
分类：  
（1）内部排序：待排序记录全部存放在计算机内存中进行排序的过程；  
（2）外部排序：待排序记录的数量很大，内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程；

### 2、内部排序方法的分类 ###

（1）插入类：直接插入排序、折半插入排序、希尔排序；  
（2）交换类：冒泡排序、快速排序；  
（3）选择类：简单选择排序、树形选择排序、堆排序；  
（4）归并类：2-路归并排序；  
（5）分配类：基数排序；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]

### 3、待排序记录的存储方式 ###

（1）顺序表：记录之间的次序关系由其存储位置决定，实现排序需要移动记录；  
（2）链表：记录之间的次序关系由其存储位置决定，实现排序不需要移动记录，仅需修改指针即可；  
（3）地址排序：待排序记录本身存储在一组连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，仅移动地址向量中这些记录的地址，在排序结束之后再按照地址向量中的值调整记录的存储位置；

待排序记录的数据类型定义：

#define MAXSIZE 20     //顺序表的最大长度
    typedef int KeyType;   //定义关键字类型为整型
    typedef struct{
        
        KeyType key;       //关键字项
        InfoType otherinfo;//其他数据类型
    }RedType;              //记录类型
    typedef struct{
        
        RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
        int length;          //顺序表长度
    }Sqlist;                 //顺序表类型

### 4、排序算法效率的评价指标 ###

（1）执行时间（时间复杂度）  
高效的排序算法的比较次数和移动次数应尽可能的少。  
（2）辅助空间（空间复杂度）  
理想的空间复杂度为O(1)，即算法执行期间所需要的辅助空间与待排序的数据量无关。

--------------------

# 二、插入排序 #

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

基本操作是将一条记录插入到已经排好的有序表中，从而得到一个新的、记录数量增一的有序表。

void InsertSort(SqList &L)
    {
        
     for(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[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];
     }
    }

【算法特点】  
（1）稳定排序；  
（2）算法简便，且容易实现；  
（3）也适用于链式存储结构，只是在单链表上无需移动记录，仅修改相应的指针；  
（4）更适合初始记录基本有序的情况；

### 2、折半插入排序 ###

void BInsertSort(SqList &L)
    {
        
    	int i, j,low,high,m;
    	for (i = 2; i <= L.length; ++i)
    	{
        
    		L.r[0] = L.r[i];
    		low = 1; high = i - 1;
    		while (low <= high)
    		{
        
    			m = (low + high) / 2;
    			if (L.r[0].key < L.r[m].key)high = m - 1;
    			else low = m + 1;
    		}
    		for (j = i - 1; j >= high + 1; --j)
    		{
        
    			L.r[j + 1] = L.r[j];
    		}
    		L.r[high + 1] = L.r[0];
    	}
    }

【算法特点】  
（1）稳定排序  
（2）只能用于顺序结构，不能用于链式结构（原因：要进行折半查找）；  
（3）适合初始记录无序、n较大时的形况；

### 3、希尔排序 ###

void ShellInsert(SqList &L, int dk)
    {
        
    	int i, j;
    	for (i = dk + 1; i <= L.length; ++i)
    	{
        
    		if (L.r[i].key < L.r[i - dk].key)
    		{
        
    			L.r[0] = L.r[i];
    			for (j = i - dk; i > 0 && L.r[0].key < L.r[j].key; j -= dk)
    			{
        
    				L.r[j + dk] = L.r[j];
    			}
    			L.r[j + dk] = L.r[0];
    		}
    	}
    
    }
    void ShellSort(SqList &L)
    {
        
    	for (int k = 0; k < L.length; ++k)
    	{
        
    		L=ShellInsert(L,k);
    	}
    }

【算法特点】  
（1）记录跳跃式地移动导致排序方法是不稳定的；  
（2）只能用于顺序结构，不能用于链式结构；  
（3）增量序列可以有各种取法，但应该使增量序列中的值没有除一之外的公因子，并且最后一个增量值必须等于一；  
（4）适合初始记录无序、n较大时的情况；

--------------------

# 三、交换排序 #

### 1、冒泡排序 ###

void BubbleSort(SqList &L)
    {
        
    	int m,flag,j;    //flag用来标记某一趟排序是否发生变化，当序列不发生变化（flag=0），排序就完成了
    	RedType t;       //中间变量
    	m = L.length - 1;
    	flag = 1;
    	while (m > 0 && flag == 1)
    	{
        
    		flag = 0;
    		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;
    		}
    	}
    }

【算法特点】  
（1）稳定排序；  
（2）可用于链式存储结构；  
（3）移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，此算法不宜采用；

### 2、快速排序 ###

【算法特点】  
（1）记录非顺次的移动导致排序的方法是不稳定的；  
（2）排序过程中需要定位表的上界和下界，所以适合用于顺序结构；  
（3）适合初始记录无序、n较大时的情况；

--------------------

# 四、选择排序 #

### 1、简单选择排序 ###

void SelectSort(SqList L)
    {
        
    	int i,j,k;
    	RedType t;   //中间变量
    	for (i = 1; i < L.length; ++i)
    	{
        
    		k = i;
    		for (j = i + 1; j <= L.length; ++j)
    		{
        
    			if (L.r[j].key < L.r[k].key)k = j;
    			if (k != i)
    			{
        
    				t = L.r[i];
    				L.r[i] = L.r[k];
    				L.r[k] = t;
    			}
    		}
    	}
    }

【算法特点】  
（1）稳定排序算法；  
（2）可用于链式存储结构；  
（3）移动记录次数较少，比直接插入排序快；

### 2、树形选择排序 => 堆排序 ###

【算法特点】  
（1）不稳定排序；  
（2）只能用于顺序存储结构，不能用于链式存储结构；  
（3）记录较少时不宜采用。

--------------------

# 五、归并排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]  
【算法特点】  
（1）稳定排序；  
（2）可用于链式存储结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈；

--------------------

**附：直接插入排序、折半插入排序、希尔排序、冒泡排序、简单选择排序具体代码（可直接拿来用）**

#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]; 
    	int length;         //顺序表长度
    }SqList;                //顺序表类型
    //直接插入排序
    SqList 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];        //将待插入的记录暂存到监视哨中
    			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];    //将记录插入到正确的位置
    		}
    	}
    		
    	return L;
    }
    //折半插入排序
    SqList BInsertSort(SqList L)
    {
        
    	int i, j,low,high,m;
    	for (i = 2; i <= L.length; ++i)
    	{
        
    		L.r[0] = L.r[i];             //将待插入记录暂存到监视哨中
    		low = 1; high = i - 1;       //设置查找区间的初值
    		while (low <= high)
    		{
        
    			m = (low + high) / 2;    //折半
    			if (L.r[0].key < L.r[m].key)high = m - 1;//插入点在前半区间
    			else low = m + 1;        //插入位置在后半区间          
    		}
    		for (j = i - 1; j >= high + 1; --j)
    		{
        
    			L.r[j + 1] = L.r[j];
    		}
    		L.r[high + 1] = L.r[0];
    	}
    	return L;
    }
    //希尔排序
    SqList ShellInsert(SqList L, int dk)//可以理解为多次直接插入排序
    {
        
    	int i, j;
    	for (i = dk + 1; i <= L.length; ++i)
    	{
        
    		if (L.r[i].key < L.r[i - dk].key)
    		{
        
    			L.r[0] = L.r[i];
    			for (j = i - dk; i > 0 && L.r[0].key < L.r[j].key; j -= dk)
    			{
        
    				L.r[j + dk] = L.r[j];
    			}
    			L.r[j + dk] = L.r[0];
    		}
    	}
    	return L;
    }
    SqList ShellSort(SqList L)
    {
        
    	for (int k = 0; k < L.length; ++k)
    	{
        
    		L=ShellInsert(L,k);
    	}
    	return L;
    }
    //输出排完之后的顺序
    void putList(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		cout << L.r[i].key << " ";
    	}
    }
    //冒泡排序
    SqList BubbleSort(SqList L)
    {
        
    	int m,flag,j;   //flag用来标记某一趟排序是否发生变化，当序列不发生变化（flag=0），排序就完成了
    	RedType t;      //中间变量
    	m = L.length - 1;
    	flag = 1;
    	while (m > 0 && flag == 1)
    	{
        
    		flag = 0;
    		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;
    		}
    	}
    	return L;
    }
    //简单选择排序
    SqList SelectSort(SqList L)
    {
        
    	int i,j,k;
    	RedType t;   //中间变量
    	for (i = 1; i < L.length; ++i)
    	{
        
    		k = i;
    		for (j = i + 1; j <= L.length; ++j)
    		{
        
    			if (L.r[j].key < L.r[k].key)k = j;
    			if (k != i)
    			{
        
    				t = L.r[i];
    				L.r[i] = L.r[k];
    				L.r[k] = t;
    			}
    		}
    		
    	}
    	return L;
    }
    
    int main()
    {
        
    	SqList L;
    	int num;            //待排序记录的个数
    	cout << "请输入待排序记录个数:";
    	cin >> num;
    	L.length = num;
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		cin >> L.r[i].key;
    	}
    	int a;  //选择代号载体
    	cout << "*********请选择以下几种排序方式：**********"<<endl;
    	cout << "           1:直接插入排序                 " << endl;
    	cout << "           2:折半插入排序                 " << endl;
    	cout << "           3:希尔排序                     " << endl;
    	cout << "           4:冒泡排序                     " << endl;
    	cout << "           5:简单选择排序                 " << endl;
    	cout << "*******************************************" << endl;
    	cout << "请输入（1/2/3/4/5）：";
    	cin >> a;
    	switch (a)
    	{
        
    	case 1:
    		L = InsertSort(L);
    		cout << "直接插入排序结果为：";
    		break;
    	case 2:
    		L = BInsertSort(L);
    		cout << "折半插入排序结果为：";
    		break;
    	case 3:
    		L = ShellSort(L);
    		cout << "希尔排序结果为：";
    		break;
    	case 4:
    		L = BubbleSort(L);
    		cout << "冒泡排序结果为：";
    		break;
    	case 5:
    		L = SelectSort(L);
    		cout << "简单选择排序结果为：";
    		break;
    	}
    	putList(L);
    	cout << endl;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020070310375887.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200703221105835.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200705190512806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70