扑克牌式插入排序及升级版希尔排序

た入场券 2022-02-15 02:23 139阅读 0赞

## 插入排序 ##

*  问题提出：为什么叫做扑克牌式插入排序  
    这里我就得给大家解释一下，为什么我要叫做扑克牌式插入排序，很简单，小编本人喜欢打扑克牌。。。相信扑克牌大家应该都不会陌生，打扑克牌其实不仅仅是娱乐，同时也能帮我们锻炼自己的思维能力。因为对于一个扑克牌高手而言，一切尽在掌握中，对方有什么牌，我怎么样能取胜，经过概率推算，就很容易打败对手，有机会有时间大家可以和朋友们切磋一下。。 尴尬 扯的有点远，那么我们来进入我们今天的主题——**插入排序**。
 *  插入排序的基本思想：遍历我们的数据序列，将无序数据逐次插入到我们的有序序列中，直到整个序列有序。为什么叫做扑克牌式插入排序，你有没有发现，插入排序就和我们的打扑克牌非常相似，当我们抓牌的时候，其实就是在做一个插入排序，按顺序摆放的扑克牌，便于我们更好的掌握手中的牌，也就因此，对于插入排序的思想我还是记得比较牢固的，大家也不妨可以这样来理解我们的插入排序，下面让我们来看插入排序的示意图。
 *  插入排序示意图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]  
下面让我们来看一下插入排序的具体实现

#include<iostream>
    using namespace std;
    
    //插入排序
    //原理简述：挨个遍历数组元素，将未排序元素插入到已排序序列的固定位置，默认已排序序列为array[0]
    //时间复杂度：O(n^2)   
    //空间复杂度：O(1)
    //稳定性：稳定
    //插入排序对数据量小基本有序的序列排序效率较高
    
    //打印数组内容
    void print(int array[], int size) {
    	for (int i = 0; i < size; i++) {
    		cout << array[i] << " ";
    	}
    	cout << endl;
    }
    //交换函数
    void swap(int array[], int i, int j) {
    	int tmp = array[i];
    	array[i] = array[j];
    	array[j] = tmp;
    }
    
    
    //插入排序 
    void InsertSort(int array[], int size) {
    	for (int i = 1; i < size; i++) {
    		if (array[i] < array[i - 1]) {
    			int tmp = array[i];   //保存初值，以防被覆盖
    			int j;
    			for (j = i - 1; j >= 0 && tmp < array[j]; j--) {
    				array[j + 1] = array[j];   //数据搬移
    			}
    			array[j + 1] = tmp;   
    		}
    	}
    }
    
    
    int main(void) {
    	int array[] = { 12,23,7,3,54,0,7,2,4,54,9,1,3 };
    	int size = sizeof(array) / sizeof(int);
    	cout << "排序前：";
    	print(array, size);
    	cout << "排序后：";
    	InsertSort(array, size);
    	print(array, size);
    	system("pause");
    	return 0;
    }

*  直接插入排序简单总结

1.  元素集合越接近有序，直接插入排序算法的时间效率越高
2.  时间复杂度：O(N^2)
3.  空间复杂度：O(1)，它是一种稳定的排序算法
4.  稳定性：稳定

## 升级版插入排序——希尔排序 ##

*  基本思想：希尔排序其实就是一种升级版的插入排序，它是在插入排序的基础上进行优化，那么如何进行优化呢？顺着这个思路我们很容易就想到了，如果我们将序列若干组，每组之间的增量是一样的，那么我们在组内进行插入排序，然后缩小增量，直到增量为1，我们只需要再进行一次插入排序就可得到有序序列，这就是希尔排序。
 *  之听我说可能大家还是不能很好的理解希尔排序，那么咱们来看看希尔排序的示意图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 1]  
上图就是希尔排序的示意图，关于图中的gap增量我来说明一下。  
**注：gap就是我们的希尔排序中的增量，这个增量没有明确规定，但是集合了许多大佬的验证，通常我们的gap取值为：gap = gap / 3 + 1 。这是经验，大佬这么用，咱们也就这么用就好了**

*  具体实现

#include<iostream>
    using namespace std;
    
    //希尔排序
    //原理简述：希尔排序就是一种升级版的插入排序，它将待排序的区间划分组，
    //          然后对每个组的数据进行插入排序，然后缩小区间增量，重复，直到增量为1，排序之后，数据有序
    //时间复杂度：最好O(n^1.3)  最坏 O(n^2) 平均   O(N^1.3—N^2）  
    //空间复杂度：O(1)
    //稳定性：不稳定
    //分组依据：经过许多大佬的实验  分组依据满足  gap = gap / 3 + 1
    
    
    //打印数组内容
    void print(int array[], int size) {
    	for (int i = 0; i < size; i++) {
    		cout << array[i] << " ";
    	}
    	cout << endl;
    }
    //交换函数
    void swap(int array[], int i, int j) {
    	int tmp = array[i];
    	array[i] = array[j];
    	array[j] = tmp;
    }
    
    
    
    void ShellSort(int array[], int size) {
    	int gap = size;
    	//分组循环 ,注意当gap == 1 时还要再排序一次，故使用do while 循环
    	do {
    		gap = gap / 3 + 1;
    		for (int i = 0; i < gap; i++) {
    			int j;
    			for (j = i + gap; j < size; j += gap) {
    				if (array[j] < array[j - gap]) {
    					int tmp = array[j];
    					int k;
    					for (k = j - gap;k >= 0 && tmp < array[k]; k -= gap) {
    						array[k + gap] = array[k];
    					}
    					array[k + gap] = tmp;
    				}
    			}
    		}
    
    	} while (gap > 1);
    }
    
    int main(void) {
    	int array[] = {12,23,7,3,54,0,7,2,4,54,9,1,3};
    	int size = sizeof(array) / sizeof(int);
    	cout << "排序前：";
    	print(array, size);
    	cout << "排序后：";
    	ShellSort(array, size);
    	print(array, size);
    	system("pause");
    	return 0;
    }

其实写希尔排序个人认为并没有那么难，我们只需要将插入排序中的增量1改为gap即可。

*  希尔排序总结

1.  希尔排序是对直接插入排序的优化。
2.  当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3.  希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3 ~ N^2）
4.  稳定性：不稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220215/00a9782a04084028972b123f503c90df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70 1]: /images/20220215/91c8591e5e114ae195f149dcbfc7f673.png