坚持我之前的说法, 学习算法设计关键是要学习算法套路. 一些经典排序算法, 很好的体现了一些重要的套路, 值得想一想. 本文介绍插入排序的算法套路, 即重用与增量有序的思想.
先要注意, 排序的结果一般都是升序的, 也就是从小到大(与上图相反).
插入排序的算法很好理解, 形式上, 跟排扑克牌一样的操作: 一开始, 手是空的, 然后拿一张牌开始插入排序, 每一张新拿的牌都跟手中的牌进行比较, 可以从小到大的比较(遇到大的就插在前面), 也可以从大到小的比较(遇到小的就插在后面).
这个排扑克牌的操作, 有两个特点, 一个是对于每一张新牌都是一样的处理(重用), 另一个是手中的牌始终是有序(增量有序). 类比于这两个特点, 插入排序算法体现了两个重要的套路, 就是重用跟增量有序.
重用, 并不是插入排序算法特有的, 很多算法都有这个表现, 所以 "重用" 已经是一种基本的算法套路.
什么是重用呢?
举个例子:
如何把大象装进一个关着门的冰箱?
先把冰箱打开门, 再把大象装进去, 最后关上门. 这是解决办法, 而且, 把这个视为标准作业.
那么:
如何把大象装进一个开着门的冰箱?
解决办法是, 先把冰箱关上门, 然后执行上面的标准作业.
那么:
如何把十只大象装进冰箱呢?
解决办法是, 找十台冰箱, 先把门关上, 然后执行标准作业.
执行标准作业, 就是在重用.
那插入排序算法中的重用是什么表现呢? 就是每一个元素, 都跟之前的元素进行相同的比较定位与插入的操作, 也就是说, 如果把第 i 个元素的操作想清楚了(比如我把第 3 个元素怎么操作想清楚就好), 那就所有元素的操作都想清楚了.
因为可以重用, 所以思考的复杂度大幅下降. 重用也是抽象的重要手段, 有助于提取主干.
需要注意, 边界并不是算法设计重点考虑的内容, 如果不重要甚至可以忽略边界的处理. 但是, 写程序就要考虑清楚边界. 写程序跟设计算法, 是两个不同的话题, 这个我之前已经介绍过了.
总的来说, 插入排序算法中的第 i 个元素的排序, 是一个标准作业, 可以反复重用.
小白: 如果地上有一支枪, 你的敌人过来了, 你怎么杀死敌人?
小程: 捡起枪, 瞄准射击.
小白: 如果你手上拿着枪, 你的敌人过来了, 你怎么杀死敌人?
小程: 先把枪扔到地上, 然后启用之前的操作.
以上讲的是 "重用" 的套路, 接着讲 "增量有序" 的套路.
"增量有序" 的表现, 有点像清洗的工作, 比如每一棵菜都要洗干净再放到锅里, 每一个新入职的员工都要接受公司的价值观后才能开展工作, 这样保证锅里的菜都是干净的, 一起工作的人都是有相同价值观的.
简单来说, 增量有序, 就是保证正在扩展的区域一定是有序的.
插入排序算法中的 "增量有序", 可以看下面这个图来表现:
这个扩展的区域可以是新的数组, 也可以在原数组中进行.
以上是增量有序的设计套路, 至此,"重用" 与 "增量有序" 这两个重要的算法套路就介绍完毕了.
接下来, 是小的方面, 就是这个标准作业, 即其中一个元素是怎么定位插入的问题. 在增量有序的情况下, 任何一个元素, 如何找到合适的位置, 一般有三个办法.
办法一是从高往低地跟有序队列的元素作比较(也就是从右往左地比较), 遇到一个更小的值, 就插在其后面.
办法二是从低往高地跟有序队列的元素作比较(也就是从左往右地比较), 遇到一个更大的值, 就插在其前面.
办法三是比较的时候, 反复二分定位比较, 最终定下位置的办法, 这个办法可以减小比较的次数, 但程序实现的复杂度高一些.
这三个办法中, 一般来说, 办法一是最好的选择, 一来可以使这个标准作业的思路简单而清晰, 二来程序实现也相对便利.
至此, 插入排序的算法套路就介绍完毕了, 简单来说, 插入排序, 就是, 当前已经处理的数组总是有序的, 然后就重用插入一个元素的操作, 增加一个元素到已处理的数组中, 至到所有元素都处理过. 而对于插入一个元素, 可以从小到大比较(遇大就进前面), 也可以从大到小比较(遇小就进后面), 也可以二分定位(这个复杂一点, 不利于实现), 整个算法就设计完了, 并不复杂.
以下的内容, 是程序实现方面, 这里做一个简单的演示, 你如果想训练程序的编写能力的话, 应该自己动手实现.
- // 多用一个临时数组
- void insertsort(int* arr, int size) {
- int* tmparr=(int*)malloc(sizeof(int) * size);
- memcpy(tmparr, arr, size*sizeof(int));
- int count = 0;
- for (int i = 0; i <size; i ++) {
- int j=0;
- for (j = 0; j < count; j ++) {
- if (arr[i]<tmparr[j]) {
- memcpy(tmparr+j+1, tmparr+j, (size-j-1)*sizeof(int));
- tmparr[j]=arr[i];
- break;
- }
- }
- if (j==count) {
- tmparr[j]=arr[i];
- }
- count ++;
- }
- memcpy(arr, tmparr, size*sizeof(int));
- free(tmparr);
- }
- // 就地 insert
- void insertsort2(int* arr, int size) {
- for (int i = 0; i < size; i ++) {
- for (int j = 0; j < i; j ++) {
- if (arr[i] < arr[j]) {
- int t = arr[i];
- memcpy(arr+j+1, arr+j, (i-j)*sizeof(int));
- arr[j]=t;
- break;
- }
- }
- }
- }
- // 就地 insert, 另一个思路(办法一): 从右向左比较, 边比较边移位, 遇到更小的值为止
- void insertsort3(int* arr, int size) {
- for (int i = 1; i < size; i ++) {
- int t = arr[i];
- int j = 0;
- for (j = i-1; j>= 0 ; j --) {
- if (arr[j] < t) {
- arr[j+1] = t;
- break;
- }
- else {
- arr[j+1] = arr[j];
- }
- }
- if (j<0) {
- arr[0] = t;
- }
- }
- }
- int main(int argc, char *argv[])
- {
- int arr[] = {5, 3, 6, 1, 2};
- int size = sizeof arr/sizeof *arr;
- insertsort3(arr, size);
- for (int i = 0; i < size; i ++) {
- printf("%d,", arr[i]);
- }
- return 0;
- }
写程序跟设计算法不一样, 算法注重套路, 主干, 并且抽象 (忽略不重要的细节), 而写程序就要考虑一些细节(比如边界, 异常之类) 而且还有数据类型, 模块化之类的考虑.
写程序不是本文的重点.
总结一下, 本文介绍了插入排序体现的算法套路, 即重用与增量有序的设计思想, 另外也介绍了任一元素如何完成插入排序这一标准作业, 最后演示了代码实现.
posted on 2019-04-22 15:06 广州小程 阅读(...) 评论(...) 编辑 收藏
来源: https://www.cnblogs.com/freeself/p/10750210.html