讨厌算法的程序员 1 | 插入排序

什么是算法

在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。

一般性解释:

算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一个或一组值作为输出。

基于应用的解释:

算法是一种工具,用来解决一个具有良好规格说明的计算问题。该问题的描述可以用通用的语言,来规定所需的输入/输出关系。与之对应的算法则描述了一个特定的计算过程,用于实现这一输入/输出关系。

后一种解释在告诉我们,我们不必对于每个问题都去重新设计、证明和实现算法,而是有能力将实际问题转换成已知算法问题,然后选取合适的解法。而这种能力就是学习算法的目的所在。这要求我们不仅要积累算法知识,还要在更高的抽象层次上理解算法的方法论。

排序问题的形式定义

排序问题是算法要解决的一个基本问题。它的形式化定义如下:

输入:n个数的一个序列[a1, a2, ..., an]。

输出:输出序列的一个排列[a1', a2', ..., an'], 满足a1' ≤ a2' ≤ ... ≤ an'。

插入排序算法

插入排序算法,对于少量元素的排序问题,是一个有效的算法。

经典应用

扑克

即便是玩过扑克牌的小孩子,其实都对插入排序算法了然于胸。

  • 摸牌之前,所有将会被你摸到的牌,此时是一种乱序的状态。
  • 你开始摸牌,并将新摸到的牌插入到合适的位置,以保证你手中的牌总是有序的。
  • 直到摸到最后一张,将其插入到合适的位置,此时你手中所有的牌就已经排好序了。

算法的抽象表达

想让计算机听懂上述的算法,需要将其进行翻译。

INSERTION-SORT(A) 1 for j = 2 to A.length 2 key = A[j] 3 // Insert A[j] into the sorted sequence A[1..j-1]. 4 i = j - 1 5 while i > 0 and A[i] > key 6 A[i + 1] = A[i] 7 i = i - 1 8 A[i + 1] = key

原著中的伪码无可挑剔,就沿用了。做一些说明:

  • 算法名称INSERT-SORT;
  • A是一个长度为n的要排序的数组,用A.length表示n;
  • 把待排序数组A逻辑上分为两个数组,排好序的(手中的牌),未排序的(桌上待摸的牌);
  • 排好序的数组起始只有一个元素,就是原数组A的第一个元素(摸出的第一张牌无需排序),循环变量用i表示;
  • 未排序的数组起始,从原数组A的第二个元素一直到最后一个元素,所以外层的遍历是“2 to A.length”,循环变量用j表示;
  • 外层遍历过程中,每个当前元素A[j]都暂存至key变量中;
  • key要加入排序好的数组,会从该排序好数组的最末i(j-1)开始进行比较,如果A[i]大于key,A[i]移动到A[i+1],i自减,继续与key比较,如果此时i ≤ 0 或者 A[i] ≤ key,循环条件不成立跳出,将key存入A[i+1]。

算法工作例子

插入算法如何工作

说明:

  • (a)~(e)是循环迭代,(f)是最终排好的数组;
  • 数组上方是数组的下标;
  • 黑色块表示每次外层迭代,待插入左侧数组的数A[j];
  • 灰色块表示参与和A[j]比较的数;
  • 黄色箭头是伪码第6行表达的移动;
  • 蓝色大箭头是伪码第8行表达的移动;

Java实现

public class InsertionSort { public static void sortInASC(int[] numbers){ for(int j = 1; j < numbers.length; j++){ int key = numbers[j]; int i = j - 1; while(i >= 0 && numbers[i] > key){ numbers[i + 1] = numbers[i]; i = i - 1; } numbers[i + 1] = key; } } }

InsertSort.java下载 (https://github.com/EthanYuan/algorithm/tree/master/src/algorithm)

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

[Silverlight动画]转向行为 - 2D向量

转向行为已经被各种语言实现过多次了,其最底层是用向量来描述的(也是最常见的实现方式)。 概括的看,一个向量由两部分组成:一个方向和一个大小。比如,一个运动中对象...

1786
来自专栏向治洪

数据结构之2-3-4树

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构,可以在O(lgn)的时间内查找、插入和删除,这里的n是树中元素的数目。2-3-4树和红黑树是等价的,也...

1809
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

662
来自专栏云时之间

NLP入门之形式语言与自动机学习(三)

在前边的文章中我们把简单的需要的基础知识简单的列举了一遍,包括简单的集合逻辑,还有图论以及一些的证明方法等等,接下来我们将要开始我们正式的关于形式语言的学习,所...

4016
来自专栏灯塔大数据

每周学点大数据 | No.20序列有序的判定

No.19期 序列有序的判定0 数组的判 Mr. 王:这里我们再讲一个亚线性时间的判定问题——数组有序的判定问题。你来说一下问题定义,并想一想这个问题...

2675
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3204
来自专栏云霄雨霁

排序算法总结

960
来自专栏AI派

Numpy 修炼之道 (7)—— 形状操作

无论是ravel、reshape、T,它们都不会更改原有的数组形状,都是返回一个新的数组。

2823
来自专栏机器学习算法全栈工程师

Sample K算法

0、题目来源    最近去国内某牛叉互联网公司面试,出了一道算法题,看似简单,但是真正的答案十分巧妙。故此回忆并将原题以及解题思路记录下来,供大家学习: 随机...

3398
来自专栏mathor

matlab—回归与内插(完结)

1564

扫码关注云+社区