下载掌阅APP，畅读海量书库
立即打开
生活之中，处处皆见比较，路程的远近、颜色的深浅、时间的长短、动力的强弱等等，有比较就要排出先后、分出高低，有比较就有排序。在计算机科学及其应用领域常常涉及对数据按照设定的规则进行重组，对数据进行排序。所谓排序算法，就是定义一种数据的重组规则，输入无序数据按照该规则重新进行排列后得到有序输出序列。通常用到的排序方式包括数值序和字典序，数值序是依据数值的大小（按照排序规则所确定的大小，不一定是字面值）进行重新排列，字典序则是按照符号表中字符出现的先后顺序进行重新排列。
关于排序的资料汗牛充栋，众多材料中当数计算机科学泰斗Donald E.Knuth（高纳德）所著的《计算机程序设计艺术卷3：排序与查找》最为经典。排序算法总体上可分为比较类排序和非比较类排序。比较类排序通过比较待排序元素的关键字来决定重新排列后元素间的相对次序，非比较类排序则不是通过比较来决定重新排序后元素间的相对次序。常见的比较类排序算法包括交换排序、插入排序、选择排序和归并排序等算法，非比较类排序包括计数排序、桶排序和基数排序等算法，如图2-1所示。本书将在不同章节对不涉及数据结构的排序算法进行分析和说明，本章只介绍适合初学者入门的冒泡排序、选择排序、插入排序和计数排序。