八大排序之插入排序（直接插入排序 & 希尔排序）

╰+攻爆jí腚メ 2022-04-22 00:00 182阅读 0赞

### 文章目录 ###

*   *  插入排序
     *   *   *  直接插入排序
             *  二分插入排序
             *  希尔排序

## 插入排序 ##

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序可以分为直接插入排序和希尔排序。

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

#### 直接插入排序 ####

相信大家都玩过扑克牌（即使没玩过，也听说过）。

*  当我们手里有第一张牌的时候，随便放
 *  当有第二张牌的时候，与第一张牌进行比较，比第一张大，放在它的后面，比一张小，放在它的前面
 *  当有第三张牌的时候，与前两张比较，选择位置插入
 *  以此类推

这就是插入，类比到我们排序中，就能得到如下步骤

1.  从第一个元素开始，该元素可以认为已经被排序
2.  取出下一个元素，在已经排序的元素序列中从后向前扫描
3.  如果该元素（已排序）大于新元素，将该元素移到下一位置
4.  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.  将新元素插入到该位置后
6.  重复步骤2~5  
    **代码如下：**

void InsertSort(int arr[], int size)
    	{ 
    		for (int i = 1; i < size; i++) //i表示当前要排序的数
    		{ 
    			int key = arr[i];
    			int j;
    			for (j = i - 1; j >= 0; j--) //从i的前一个元素开始往前找
    			{ 
    				if (arr[j] > key)
    				{ 
    					arr[j + 1] = arr[j];
    				}
    				else
    				{ 
    					break;
    				}
    			}
    			arr[j + 1] = key;
    		}
    	}

**时间复杂度：O(n ^ 2)**  
**空间复杂度：O(1)**  
**直接插入排序是稳定的**  
**数组越有序，直接插入排序越快**

#### 二分插入排序 ####

由于上述在查找比较关键码的时候，会比较慢。因为关键码前面已经有序，就可以运用二分查找的思想来判断关键码的位置。

void InsertSort(int arr[], int size)
    	{ 
    		for (int i = 1; i < size; i++)
    		{ 
    			int tmp = arr[i];
    			//加入了一个二分查找的过程
    			int left = 0;
    			int right = i - 1;
    			while (left <= right)
    			{ 
    				int mid = (left & right) + ((left ^ right) >> 1);
    				if (arr[mid] > tmp)
    				{ 
    					right = mid - 1;
    				}
    				else
    				{ 
    					left = mid + 1;
    				}
    			}
    			//这里一定要大于等于left，因为在上面left已经加1
    			for (int j = i - 1; j >= left; j--)
    			{ 
    				arr[j + 1] = arr[j];
    			}
    			arr[left] = tmp;
    		}
    	}

#### 希尔排序 ####

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。  
因为直接插入排序依次只能移动一个数据，但如果要是依次可以移动多个数据，排序时间肯定就短了，于是便有了希尔排序。  
**基本思想：**

*  先将待排序序列分成若干个子序列（由相隔某个“增量”的元素组成的）
 *  将每个子序列进行直接插入排序
 *  将增量减1，再重复上述过程
 *  最终直到增量为1停止  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]  
    **代码如下：**

void __InsertSort(int arr[], int size, int gap)
    	{ 
    		for (int g = 0; g < gap; g++)
    		{ 
    			for (int i = g + gap; i < size; i += gap)
    			{ 
    				int key = arr[i];
    				int j;
    				for (j = i - gap; j >= 0; j -= gap)
    				{ 
    					if (arr[j] > key)
    					{ 
    						arr[j + gap] = arr[j];
    					}
    					else
    					{ 
    						break;
    					}
    				}
    				arr[j + gap] = key;
    			}
    		}
    	}
    
    	void ShellSort(int arr[], int size)
    	{ 
    		int gap = size;
    		while (1)
    		{ 
    			gap = gap / 3 + 1;
    			__InsertSort(arr, size, gap);
    			if (gap == 1)
    			{ 
    				break;
    			}
    		}
    	}

**上述中gap = size / 3 + 1这是经过大量实验推算出来的，第一步的增量取这个值会更合理**  
虽然上述代码比较容易理解，但不够简洁。  
**优化：**

void __InsertSort(int arr[], int size, int gap)
    	{ 
    		int j, key;
    		for (int i = gap; i < size; i++)
    		{ 
    			key = arr[i];
    			for (j = i - gap; j >= 0; j -= gap)
    			{ 
    				if (arr[j] > key)
    				{ 
    					arr[j + gap] = arr[j];
    				}
    				else
    				{ 
    					break;
    				}
    			}
    			arr[j + gap] = key;
    		}
    	}
    	void ShellSort(int arr[], int size)
    	{ 
    		int gap = size;
    		while (1)
    		{ 
    			gap = gap / 3 + 1;
    			__InsertSort(arr, size, gap);
    			if (gap == 1)
    			{ 
    				break;
    			}
    		}
    	}

**直接插入排序可以看做是增量为1的希尔排序**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]: /images/20220422/4a81ac2d51da40179005bfcb26524044.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]: /images/20220422/825b7afd8f734cd2b04dbae0a9322b04.png