【数据结构】-内部排序(插入排序)

秒速五厘米 2022-11-25 11:49 174阅读 0赞

### 内部排序-插入排序 ###

*  写在前面
 *  1.头文件及类型定义
 *  2.函数声明
 *  3.基本操作
 *   *  3.1 直接插入排序
     *  3.2 折半插入排序
     *  3.3 希尔排序
 *  4.main函数
 *  5.小结

# 写在前面 #

【说明】以下代码实现最终均为**递增序列**，即从小到大排序。

# 1.头文件及类型定义 #

#include<stdio.h>
    #define ElemType int

# 2.函数声明 #

/*函数声明*/
    void DirectInsertSort(ElemType A[], int n);		//1.直接插入排序
    void HalfInsertSort(ElemType A[], int n);		//2.折半插入排序
    void ShellSort(ElemType A[], int n);			//3.希尔排序

# 3.基本操作 #

## 3.1 直接插入排序 ##

//1.直接插入排序
    void DirectInsertSort(ElemType A[], int n) {
        
    	int i, j;
    	for(i=2;i<=n;i++)	//依次将A[2]~A[n]插入到前面已排序序列
    		if (A[i] < A[i - 1]) {
          //若A[i]关键字小于其前驱，将A[i]插入有序表
    			A[0] = A[i];	//A[0]设置为“哨兵”
    			for (j = i - 1; A[0] < A[j]; j--)	//从后往前顺序查找待插入位置
    				A[j + 1] = A[j];	//向后挪位
    			A[j + 1] = A[0];	//插入指定位置
    		}
    }

## 3.2 折半插入排序 ##

//2.折半插入排序
    void HalfInsertSort(ElemType A[], int n) {
        
    	int i, j, low, high, mid;
    	for (i = 2; i <= n; i++) {
        	//依次将A[2]~A[n]插入到前面已排序序列
    		A[0] = A[i];	//A[i]暂存到A[0]
    		low = 1;			//设置折半查找的范围
    		high = i - 1;
    		while (low <= high) {
        	//折半查找(默认递增有序)
    			mid = (low + high) / 2;		//取中间点(向下取整)
    			if (A[mid] > A[0])
    				high = mid - 1;		//查找左子表
    			else
    				low = mid + 1;		//查找右子表
    		}
    		for (j = i - 1; j >= high + 1; j--)	
    			A[j + 1] = A[j];	//统一后移元素，空出插入位置
    		A[high + 1] = A[0];		//插入指定位置
    		//或者  A[low] = A[0];  因为最后是在low>high时退出循环的，故low=high+1
    	}
    }

## 3.3 希尔排序 ##

//3.希尔排序
    void ShellSort(ElemType A[], int n) {
        
    	int d, i, j;
    	//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    	for (d = n / 2; d >= 1; d /= 2) //步长(增量)变化
    		for (i = d + 1; i <= n; i++)
    			if (A[i] < A[i - d]) {
        	//需将A[i]插入有序增量子表
    				A[0] = A[i];	//暂存在A[0]
    				for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
    					A[j + d] = A[j];	//记录后移，查找插入位置
    				A[j + d] = A[0];	//插入指定位置
    			}
    }

# 4.main函数 #

int main() {
        
    	//1.直接插入排序
    	ElemType A[11];
    	for (int i = 1; i < 11; i++)
    		scanf("%d", &A[i]);
    	DirectInsertSort(A, 10);
    	for (int i = 1; i < 11; i++)
    		printf("%d\t", A[i]);
    	printf("\n");
    
    	//2.折半插入排序
    	ElemType B[11];
    	for (int i = 1; i < 11; i++)
    		scanf("%d", &B[i]);
    	HalfInsertSort(B, 10);
    	for (int i = 1; i < 11; i++)
    		printf("%d\t", B[i]);
    	printf("\n");
    
    	//3.希尔排序
    	ElemType C[9];
    	for (int i = 1; i < 9; i++)
    		scanf("%d", &C[i]);
    	ShellSort(C, 8);
    	for (int i = 1; i < 9; i++)
    		printf("%d\t", C[i]);
    
    	return 0;
    }

# 5.小结 #

*一、插入排序的概念*

*  顾名思义，就是插入(hhh),主要分两步：  
    **① 找插入位置(比较)**：得知道往哪插，就是查找咯，用顺序查找就是直接插入排序，用折半查找就是折半插入排序，所谓查找也就是**比较**的过程。  
    **② 插入(移动)**：和按个子大小站队一样，找到插入位置以后，你先从队里面出来，跑到要**插入**的位置，别人向后**移动**，填补你原来的位置。

*二、关于三种插入排序的关系*

**逐渐优化**：直接插入排序——>折半插入排序——>希尔排序  
**\[解释\]**  
给定一个乱序序列，从第2个元素开始，依次和前面元素比较(即顺序查找)，也就是进行**直接插入排序**。因此，每一趟直接插入排序开始时，它前面的序列都是有序的(因为前面的已经比过了)。  
既然前面的元素有序，则可以折半查找来提高查找插入位置的效率，也就是**折半插入排序**。  
试想：如果给定序列本身就由小到大，那么则只需要从第2个元素开始比较，不需要移动，由此可见直接插入排序更适用于基本有序且数据量不大的排序表，**希尔排序**就是基于这两点分析进一步改进的，由部分有序到整体有序。

*三、关于三种插入排序的性能分析*

1.  直接插入排序  
    **空间复杂度**：O(1)  
    **时间复杂度**：O(n2)  
    **稳定性**:稳定  
    **适用性**：适用于顺序存储和链式存储的线性表
2.  折半插入排序  
    **空间复杂度**：O(1)  
    **时间复杂度**：O(n2)  
    **稳定性**:稳定  
    **适用**：仅适用于顺序存储的线性表
3.  希尔排序(缩小增量排序)  
    **空间复杂度**：O(1)  
    **时间复杂度**：最坏为O(n2)  
    **稳定性**:不稳定  
    **适用**：仅适用于顺序存储的线性表  
    【注】：当增量d=1时，希尔排序会退化为直接插入排序

*四、其他说明*

1.  对直接插入排序和折半插入排序来说，**每一趟排序都会得到一个部分有序的序列**，这可以作为判断是否进行了直接插入排序或折半插入的依据，而希尔排序不会。
2.  关于算法适用于顺序存储还是链式存储，**主要看在算法的执行过程中，是否涉及到了对元素的随机访问**，如果涉及到了对元素的随机访问，则链表不适用。就上述三种排序算法来说，*直接插入排序* 采用的是顺序查找，挨个找，链表也可以；而*折半插入排序* 采用的是折半查找，对mid指针来说，他是随机访问的，所以链表不行；*希尔排序* 也是同样的，因为每次增量d都是变化的，也是随机访问，所以链表不行。  
    **需要注意的是，大部分的排序算法都仅适用于顺序存储的线性表**