服务器怎么放网站吗,网络优化师是什么工作,如何自己建网站服务器,免费虚拟云windows主机本篇是排序专栏博客的第一篇#xff0c;主要探讨以 “插入” 为核心思想的排序算法该如何实现 文章目录 一、前言二、直接插入排序1. 算法思想与操作分析2. 代码实现version 1version 2 3. 复杂度分析 三、折半插入排序1. 算法思想与操作分析2. 代码实现3. 复杂度分析 四、2路…
本篇是排序专栏博客的第一篇主要探讨以 “插入” 为核心思想的排序算法该如何实现 文章目录 一、前言二、直接插入排序1. 算法思想与操作分析2. 代码实现version 1version 2 3. 复杂度分析 三、折半插入排序1. 算法思想与操作分析2. 代码实现3. 复杂度分析 四、2路插入排序1. 算法思想与操作分析2. 代码实现3. 复杂度分析 五、希尔排序1. 算法思想与操作分析2. 代码实现version 1version 2version 3 3. 复杂度分析 一、前言
所谓插入排序就是将数据整体的一部分独立看作有序另一部分看作无序然后将无序区间的数据一个一个地插入到有序区间中并且在插入过程中始终保持有序区间有序的一种算法。
或许你会觉得很少见但实际日常生活中我们玩扑克牌游戏时就不自觉应用了这种思想。
既然插入排序要不断将数据插入有序区间中那关键的地方就在于如何在有序区间中找到一个合适的位置给新的数据。因此根据查找插入位置的方法不同就衍生出了多种插入排序。 按顺序法查找插入位置的——直接插入排序。按折半法也叫二分法查找插入位置的——折半插入排序。通过缩小增量进行分组预排序的——希尔排序。通过辅助空间减少挪动次数的——2路排序。 接下来就分别探讨这四个插入思想的排序算法如何实现。
二、直接插入排序
1. 算法思想与操作分析
思想
假设我们现在要对 n 个数据排序
将第1个数据作为有序区间后面的n-1个数据作为无序区间然后将无序区间的首个数据插入到有序区间中这个操作要进行n-1次。直接插入排序又称顺序插入排序因此做法就是定义一个索引end指向有序区间的最后一个数据每次插入操作都从后往前遍历有序区间找到合适的插入位置。重复步骤 2直到无序序列数据个数为 0 。
图解分析基本操作
有一组数据如下我们现在需要将其从小到大排序。 首先将数据划分出有序区间和无序区间。 定义索引end指向有序区间的末个数据用于遍历有序区间 定义索引i指向无序区间的首个数据遍历无序区间进行每一趟的数据插入。 a[end] a[i]说明 1 应该插入到 9 的前面但是 9 的前面已经不是数组的有效空间。 因此9 要往后挪动一位但是这样又会把a[i]给覆盖了所以挪动前需要定义一个临时变量temp来保存a[i]的内容。 然后--end看到这里你会惊讶的说end 为什么要 -1减完它就越界了啊这样做是不是错了别急先记住这里后面会一起解释。 这样操作待插入数据 1 就可以在 9 前面插入了因为此时 end 的值为 -1所以插入操作为a[end 1] temp。 此时有序区间数据个数增加1无序区间个数减少1索引变量end、i也要随着更新更新操作为i、end i - 1 第二轮待插入数据为 2然后我们再重复上面的步骤 2、3、4、5 废话不多说直接上图为了节省画图压力个人这里就压缩成两张图了 排序的步骤就演示到这里接下来的操作无非就是重复步骤 2、3、5 的操作罢了所以这里主要是总结一下排序过程的注意点。 从 3、6 这两点的图中我们可以总结出找到插入位置的情况有两种 索引变量end遍历完有序区间即 end -1 索引变量end未遍历完有序区间但它指向的值a[end] temp 这两种情况下插入位置都在end的下一个位置。
2. 代码实现
version 1
typedef int DataType;
void InsertSort1(DataType* a, int n)
{// 待插入数据即区间[1, n-1]int i 0;for (i 1; i n; i){// 单趟插入默认有序区间[0, n-2]int temp a[i];int end i - 1;// 找到合适位置的条件有2// 条件1end -1退出循环while (end 0){if (a[end] temp){a[end 1] a[end];--end;}else{// 条件2a[end] temp// 按道理来说这里应该进行插入操作的// 但是根据上面分析条件1、2的插入操作都是一致于是都放在循环外了break;}}a[end 1] temp;}
}version 2
也许你会感觉虽然上面的方法已经能够完成算法了但是索引变量end在遍历过程中毕竟越界了有种不安全的感觉这里提供了第二种实现思路。
typedef int DataType;
void InsertSort2(DataType* a, int n)
{// while -- for结构紧凑不会越界int i 0;for (int i 1; i n; i){int temp a[i];int pos 0;// 这里就很明显地看到找到合适位置有两个条件了for (pos i; pos 0 a[pos - 1] temp; pos--){a[pos] a[pos - 1];}// 当退出循环后pos指向的位置就是插入位置a[pos] temp;}
}3. 复杂度分析
时间复杂度
直接插入排序是一种受序列初始排布状态影响的排序算法。
我们来对比以下两组数据排升序的性能差别
第一组数据{10, 9, 8, 7, 6, 5, 4, 3, 2, 1} 第一组数据{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 从上面两组数据中我们不难看出如果数据越接近于有序那么直接插入排序的效率越高反之效率越差时间复杂度越高。 虽然我们希望每次排序时都出现最好情况但是很遗憾时间复杂度是一个悲观预期它以最坏情况为标准。 因此结论是直接插入排序的时间复杂度是O(N^2)。 空间复杂度 空间复杂度取决算法实现过程中额外空间消耗的大小像temp、end、i、pos这样的常数个变量的开销的空间复杂度是O(1)。 三、折半插入排序
1. 算法思想与操作分析
思想
同样我们现在仍要对 n 个数据排序
将第1个数据作为有序区间后面的n-1个数据作为无序区间然后将无序区间的首个数据插入到有序区间中这个操作要进行n-1次直到无序区间数据个位数为 0。相比较于边比较边挪动数据的直接插入排序折半插入排序先用二分法找到插入位置然后再挪动数据最后将数据插入到合适的位置。
图解分析基本操作
首先将数据划分出有序区间和无序区间。 为了方便折半插入排序仍旧采用与前面相同的一组数据 定义用于二分查找插入位置的 3 个索引变量left、mid、right 定义用于遍历控制无序区间数据插入的循环迭代变量i。 设计好变量后接下来进行第一趟的插入先说明一下变量的初始化 首先是循环迭代变量i它承担的任务和前面相同从下标为 1 开始遍历完无序区间 其次是折半查找的三个变量 left指向有序区间的最左端即初始化为left 0right指向有序区间最右端即初始化为right i - 1mid指向当前区间的中间数据即初始化为mid (left right) / 2 折半插入排序仅仅只是改变了插入位置的查找方式数据挪动过程中仍会对待插入数据a[i]进行覆盖因此挪动前要将a[i]用临时变量temp保存 然后此时的a[mid] temp说明插入位置在a[mid]的左边然后更新查找的边界操作为right mid - 1 更新完边界之后我们 需要判断一下是否满足条件left right如果满足说明明仍要继续查找当right left时left指向的位置就是插入位置从left开始到有序区间的最右端的数据都要向后挪动一位temp的作用就在这里体现了 第一轮插入完毕接下来进行第二轮插入 首先要对变量left、mid、right、i分别进行更新 i使变量i重新指向无序区间的首个数据 left 0使变量left重新指向有序区间左边界 right i - 1使变量right重新指向有序区间的右边界 mid (left right) / 2使变量mid重新指向当前查找区间的中间值 ①临时变量temp保存a[i] ②比较得a[mid] temp说明插入位置在右半区间 [mid1, right]更新查找区间的左边界即left mid 1此时left right查找继续 ③边界发生变化更新mid (left right) / 2 ④比较得temp a[mid]说明插入位置在左半区间 [left, mid-1]更新查找区间的右边界边界即right mid - 1此时left right查找停止 ⑤此时left指向的位置就是查找位置 ①有序区间内从left开始的数据都向后挪动一位 ②将temp插入到left指向的位置 剩余数据的插入与上面的大同小异唯一的不同点就是随着有序区间数据的增多区间更新的次数也随之增加而已这里就不再过多演示
2. 代码实现
typedef int DataType;
void BinaryInsertSort(DataType* a, int n)
{int i 0;for (i 1; i n; i) // 无序区间[1, n-1]n-1 次插入操作 {int temp a[i]; // 临时变量保存a[i]int left 0;int right i - 1;// 二分查找插入位置while (left right){int mid (left right) / 2;if (a[mid] temp) // 插入位置在右半区间{left mid 1; // 左边界更新}else // 插入位置在左半区间{right mid - 1;// 右边界更新}}//数据挪动int j 0;for (j i; j left; j--){a[j] a[j - 1];}// 数据插入a[left] temp;}
}3. 复杂度分析
时间复杂度
折半插入排序不同于直接插入排序的边比较边挪数据该算法将比较和挪动的捆绑关系解放通过减少比较次数来进行一个小幅度的优化但是数据挪动的次数相较于直接插入排序是没有优化的。 在最坏情况下比如{10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }等 插入第1个数据挪动1次 插入第2个数据挪动2次 …… 插入第10个数据挪动10次 ……以此类推 插入第n-1个数据挪动n-1次 在最坏情况下虽然比较次数有所减少但数据挪动次数却没有减少。 因此结论是折半插入排序的时间复杂度是O(N^2)。 空间复杂度 空间复杂度取决算法实现过程中额外空间消耗的大小像temp、end、i、pos这样的常数个变量的开销的空间复杂度是O(1)。 四、2路插入排序
前面提到过折半插入排序是在直接插入排序的基础上实现了比较次数和数据挪动之间的关系解绑而在接下来要探讨的2路插入排序则是在直接插入排序上尽可能减少数据的挪动。
1. 算法思想与操作分析
思想
2路插入排序是一种典型的通过牺牲空间换取时间的算法先开辟与原数据等长的数据空间然后遍历原数据在辅助空间中排好序然后拷贝回源数据空间。
图解思想和基本操作
第一步: ①开辟等长的辅助排序空间初始化为0将源数组第一个数据拷贝过去 ②定义索引变量headtail指向assist数组的第一个值 ③定义循环变量i用于遍历源数组进行数据插入。 第二步 现在数据分成三种情况 ①a[i] assist[head]a[i] 插入到 head 的前一个位置更新 head ②assist[tail] a[i]a[i] 插入到 tail 的后一个位置更新 tail ③其余情况统一按直接插入排序处理
接下来插入第一个数据
a[i] ( 6) assist[head]属于第一种情况head向前挪动一个位置操作为head (head - 1 n) % n 这个就是这个算法的最核心之处了如果你学过循环队列那这个会很好理解如果没有了解过这方面的知识你可以把数组想象成一个首尾相接的圆 接下来插入第二个数据
assist[head] a[i] ( 7) assist[tail]属于第三种情况将a[i]插入有序区间 [head, tail]。
规定操作如下
先让tail向后移动一个位置再定义变量end控制数据挪动
只有遇到 (end 的前一个数据) a[i] 才停止挪动数据
当 end 停止移动时end指向的位置就是插入位置 一般来说tail 向后移动不会出现越界的情况但为了代码的一致统一对索引变量的移动进行取余操作 当索引变量向后移动时不再是而是变量 (变量 1) % n 当索引变量向前移动时不再是–而是变量 (变量 - 1 n) % n tail (tail 1) % n向后移动一位。 定义变量end tail将end的前一个数据向后挪动一位再更新end即 assist[end] assist[(end - 1 n) % n] end (end - 1 n) % n。 当end 0 时end 的前一个位置的值为6 a[i] ( 7)停止挪动、插入数据。 接下来插入第三个数据
此时assist[tail] a[i] ( 7) 属于第一种情况将a[i]插入tail的后一个位置。 操作为 tail (tail 1) % n assist[tail] a[i]; 三次插入操作分别讲述了算法操作过程中会遇到三种情况图解分析就到此为止就下来就是代码实现。 2. 代码实现
typedef int Datatype;
void TwoWayInsert(DataType* a, int n)
{// 辅助空间int* assist (int*)calloc(n, sizeof(DataType));if (assist NULL){printf(calloc failed\n);exit(-1);}assist[0] a[0];// 索引变量控制插入int head 0, tail 0;int i 0;for (i 1; i n; i){// assist[head] 放头前if (assist[head] a[i]){assist[head (head - 1 n) % n] a[i];}// assist[tail] 放尾后else if (assist[tail] a[i]){assist[tail (tail 1) % n] a[i];}// 其余统一按直接插入排序处理else{int end tail;while (1){assist[end] assist[(end - 1 n) % n];end (end - 1 n) % n;// end前一个位置比a[i]小就退出if (assist[(end - 1 n) % n] a[i]){break;}}assist[end] a[i];}}for (i 0; i n; i){a[i] assist[head];head (head 1) % n;}free(assist);
}3. 复杂度分析
时间复杂度
取决于移动元素和比较元素。 最坏情况 放第一个元素移动0比较0 放第二个元素移动0比较1 放第三个元素挪动1比较2 放第四个元素挪动2比较3 放第五个元素挪动3比较4 … 放第n个元素挪动(n-2)比较(n-1) 比较次数之和大于挪动次数之和以比较为标准则排序部分的时间复杂度为O(N^2)。 最后还要将辅助空间数据拷贝回源数据该操作复杂度为O(N)。 因此结论为2路插入排序的时间复杂度为O(N^2)。
空间复杂度
算法在执行过程中额外的空间开销取决于源数据个数总的空间开销为 未知数N 常数个变量。 因此结论为2路插入排序的时间复杂度为O(N)。
五、希尔排序
前面提到过“对于直接插入排序如果数据越接近于有序那么它的排序效率越高”但是现实中的数据不总是接近于有序。
那么如何使数据更加接近于有序呢
1959年有一个名叫 DLShell 提出了一种解决方法对直接插入排序进行了大幅度的性能优化最后这个方法被以它的提出者来命名叫做 “希尔排序”这就是希尔排序的由来。
1. 算法思想与操作分析
思想
希尔排序又叫做 “缩小增量排序”“分组插入排序”。
它的基本思想如下
将整个待排序数据序列以某个间隔(假设为gap)作为一组划分成不同的子区间分别进行直接插入排序不断缩小gap、重新划分子区间、分别进行直接插入排序直到整体数据接近于有序再对全体元素进行一次直接插入排序。
图解分析基本操作
以下为对一组简单的数据进行希尔排序的过程 图中很清晰的展示了希尔排序是如何进行的 定义一个增量gap设置初始值为n/2将数据分为gap组分别对gap组数据进行直接插入排序gap / 2缩小增量再对新划分的gap组数据进行直接插入排序重复步骤 2如果gap 1进行的是预排序目的是将较大的数据放到后面较小的数据挪到前面使数据更接近于有序如果gap 1此时数据已经基本接近于有序对数据整体进行一次直接插入排序使数据完全有序。 2. 代码实现
version 1
根据上面基本操作分析我们来将代码进行实现实现过程中个人建议从小到大写即先写好对小组的直接插入排序再用外循环控制增量gap的缩小。
对分组进行直接插入排序时要注意gap。
typedef int DataType;
void ShellSort(DataType* a, int left, int right)
{int gap right;while (gap 1){// 当 gap 1 时进行的就是预排序// 当 gap 1 时进行的就是直接插入排序gap / 2;int i 0;// 对分别划分出的gap组数据进行直接插入排序for (i 0; i gap; i){int end i;// 每组数据中定义变量end来遍历有序区间进行数据挪动// 注意间隔为gap不再是1for (end i; end right - gap; end gap){// 临时变量temp保存无序区间的第一个值int temp a[end gap];while (end 0){if (a[end] temp){a[end gap] a[end];}else{break;}end - gap;}a[end gap] temp;}}}
}
这样代码就成功实现出来了但是这样的代码就是最优的吗
我们接着往下看。
version 2
有人经过观察发现下面两个循环在写法上可以进行合二为一。
何出此言 typedef int DataType;
void ShellSort(DataType* a, int left, int right)
{int gap right;while (gap 1){// 当 gap 1 时进行的就是预排序// 当 gap 1 时进行的就是直接插入排序gap / 2;int end 0;// 对gap组进行多组并排for (end 0; end right - gap; end){// 临时变量temp保存无序区间第一个值int temp a[end gap];while (end 0){if (a[end] temp){a[end gap] a[end];}else{break;}end - gap;}a[end gap] temp;}}
}该写法相较于第一种写法通过调整代码运行的逻辑结构对代码进行简化代码的易理解程度个人认为相较于第一种有所下降。但这种方法进行调整的逻辑思维巧妙性个人认为还是值得学习的。 version 3
探讨直接插入排序时我们不是实现了两种方法吗那版本二的代码能不能套进希尔排序呢——答案是可以的。
改动如下
void ShellSort3(DataType a[], int left, int right)
{int gap right;while (gap 1){// 当 gap 1 时进行的就是预排序// 当 gap 1 时进行的就是直接插入排序gap / 2;int tmp 0;// 对gap组进行多组并排i指向无序区间的第一个值for (int i gap; i right; i){tmp a[i];int pos 0;// 上面的end是指向tmp的前一个位置这里的pos直接指向tmp所在位置// 当循环结束之后pos就是数据该插入的位置for (pos i; pos gap a[pos - gap] tmp; pos - gap){a[pos] a[pos - gap];}a[pos] tmp;}}
}3. 复杂度分析
时间复杂度
希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定
比如《数据结构(C语言版)》—严蔚敏 比如《数据结构-用面相对象方法与C描述》—殷人昆 个人这里gap的取值用的就是 shell 提出的gap gap / 2时间复杂度大概在O(N^1.5)。
空间复杂度
希尔排序过程中并未产生额外的线性空间开销因此它的空间复杂度为O(1)。
