扑克牌式插入排序及升级版希尔排序 た 入场券 2022-02-15 02:23 111阅读 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
还没有评论，来说两句吧...