插入排序——直接插入排序，希尔排序思想及其实现

我会带着你远行 2022-12-07 01:26 141阅读 0赞

## 思想 ##

我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，然后在未排序区间中依次取出元素并插入到已排序区间的合适位置，并保证已排序区间一直是有序。重复这个步骤直到未排序区间元素为空，算法结束  
**插入排序步骤：**

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

对于插入排序有两种排序算法：

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

首先来看直接插入：  
对于插入排序最优的结果就是排序区间刚好有序，并且是我们想要的顺序。那么时间复杂度是O(N), 但是最坏的情况就是排序区间的顺序刚好不是我们想要的顺序。那么时间复杂度就是O(N^2).

## 直接插入排序实现实现 ##

void InsertSort(int* a, int n ) {
        
    	for (int i = 0; i < n-1; i++) {
        
    		int end = i;
    		int tmp = a[end + 1];
    		while (end >= 0) {
        
    			if (a[end] > tmp) {
        
    				a[end + 1] = a[end];
    				--end;
    			}
    			else {
        
    				break;
    			}
    		}
    		a[end+1] = tmp;
    	}
    }

时间复杂度：O(N^2)  
空间复杂度: O(1)

## 希尔排序实现 ##

由于插入排序的性质， 一个数组越接近我们想要的顺序，插入的越快，那么我们就可以对数组进行预排序的处理。  
希尔排序的处理方式也叫缩小增量法。  
具体做法：  
我们将一个数组以gap（一个数字）分组进行预排序，具体代码如下所示。

void ShellSort(int* a, int n) {
        
    	int gap = n;
    	while (gap > 1) {
        
    		gap = gap / 3 + 1;
    		for (int i = 0; i < n - gap; i++) {
        
    			int end = i;
    			int tmp = a[end + gap];
    			while (end >= 0) {
        
    				if (a[end] > tmp) {
        
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else {
        
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}
    }

时间复杂度：O(N^1.3)  
空间复杂度: O(1)