C语言---插入排序（直接插入和希尔）

刺骨的言语ヽ痛彻心扉 2023-09-23 23:25 116阅读 0赞

### 文章目录 ###

*  前言
 *  一、直接插入排序
 *   *  1.简介
     *  2.算法思路
     *  3.代码实现
 *  二、希尔排序
 *   *  1.简介
     *  2.算法思路
     *  3.代码实现

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

# 前言 #

插入排序一般分为两种，一种直接插入排序，另一种则是希尔排序。

# 一、直接插入排序 #

## 1.简介 ##

直接插入排序是一种简单的排序方法，基本操作就是将需要排序的元素插入到已排好的有序表序列中，从而得到一个完整的序列。
      时间复杂度为：O(n²)    空间复杂度：O(1)      稳定性：稳定
      生活中最明显的例子就是，打扑克，把牌洗混，然后抓牌，以第一张为基础，然后将后面的牌依次插入，最后得到有顺序的牌面。

## 2.算法思路 ##

1.  将**待排的序列**看作成2个部分，一部分为有序，另一部分为无序。
2.  我们将第一个元素看作有序序列，第二个到最后都是无序序列。
3.  将无序序列的每一个元素依次插入到有序序列的合适位置。![在这里插入图片描述][3f3b292de0b94db898d71395b0b55a1e.png]  
    讲解：有一个待排序序列：【2,5,8,3】  
    我们将第一个2看成已经排序好的序列，即有序序列，从第二个元素到最后一个元素看作是无序序列。  
    待排序元素比有序元素大，则插在有序元素后，反之，插在有序元素前

## 3.代码实现 ##

#include<stdio.h>
    #define num 12
    void insert_sort(int* a, int n)
    {
        
    	
    	for (int i = 0; i < n - 1; ++i)
    	{
        
    		// 将x插入[0, end]有序区间
    		int end = i;
    		int x = a[end + 1];
    		while (end >= 0)
    		{
        
    			if (a[end] > x)
    			{
        
    				a[end + 1] = a[end];
    				end--;
    			}
    			else break;
    		}
    		a[end + 1] = x;
    	}
    }
    int main()
    {
        
    	int arr[num] = {
         3,1,4,5,2,7,9,0,8,10,11,6 };
    	printf("\n初始序列\n");
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    	insert_sort(arr, num);
    	printf("\n排序后序列\n");
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    }

运行结果：  
![在这里插入图片描述][dc2bae2aa5ce4ac9858ffd1f8d2e7674.png]

# 二、希尔排序 #

## 1.简介 ##

> 希尔排序是在直接插入排序的基础上做了较大的改进，是将整个无序序列分割成若干个的子序列分别进行插入排序。  
> 简单而言：将数组预排序，接近有序。  
> 元素为逆排序时，时间复杂度最差为O(n²） 空间最差复杂度: O(n)  
> 平均时间复杂度为O(nlog2n) 平均空间复杂度（O(1)）  
> 稳定性：差

## 2.算法思路 ##

1.  先取一个小于数组数的整数x作为第一个增量，把文件的全部记录分成x个组。
2.  所有距离为x的倍数的值在同一组里，然后进行直接插入排序，变成有序序列。
3.  取一个小于x的 x1 作为第二个增量，重复上述分组和排序，直到增量为1。  
    **注：当增量为1时，相当于所有记录放在同一组里进行直接插入排序**

![来自百度][5cc37e1fc1f84e93ab78b6aa71289d40.png]  
假设有一组\{70，30，40，10，80，20，90，100，75，60，45\}无序序列

> 第一趟：增量gap为3时，即距离为3的元素放在一组，可以分成3组，分别是\{70，10，90，60\}，\{30，80，100，45\}，\{40，20，75\}，按照直接插入排序对每个组进行排序。  
> 第二趟：gap变成了2，接着和第一趟一样，最后也是按照直接插入排序对每个组进行排序。  
> 第三趟：gap为1，后续操作也是如此…

## 3.代码实现 ##

代码如下：

#include<stdio.h>
    #define num 12
    void ShellSort(int* a, int n)
    {
        
    	int gap = n;	
    	while (gap > 1)
    {
        
    	gap = gap / 3 + 1; 
    		for (int i = 0; i < gap; i++)
    		{
        
    			for (int j = i; j < n - gap; j += gap)
    			{
        
    				int end = j;
    				int x = a[end + gap];
    				while (end >= 0)
    				{
        
    					if (a[end] > x)
    					{
        
    						a[end + gap] = a[end];
    						end -= gap;
    					}
    					else break;
    				}
    				a[end + gap] = x;
    			}
    		}
    	}
    }
    int main()
    {
        
    	int arr[num] = {
         3,1,4,5,2,7,9,0,8,10,11,6 };
    	printf("初始序列:\n");
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    	ShellSort(arr, num);
    	printf("\n排序后序列\n");
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    }

运行结果：  
![在这里插入图片描述][6412999ff7d049778aa0ef63189a79c3.png]

> 注：插入排序是排序的开始，各位努力学习的IT人员们，一起加油努力哦。祝各位学业有成，财源滚滚。  
> \---------来自菜鸟TQ02的祝福语

[3f3b292de0b94db898d71395b0b55a1e.png]: https://img-blog.csdnimg.cn/3f3b292de0b94db898d71395b0b55a1e.png
[dc2bae2aa5ce4ac9858ffd1f8d2e7674.png]: https://img-blog.csdnimg.cn/dc2bae2aa5ce4ac9858ffd1f8d2e7674.png
[5cc37e1fc1f84e93ab78b6aa71289d40.png]: https://img-blog.csdnimg.cn/5cc37e1fc1f84e93ab78b6aa71289d40.png
[6412999ff7d049778aa0ef63189a79c3.png]: https://img-blog.csdnimg.cn/6412999ff7d049778aa0ef63189a79c3.png