直接插入排序法-最简单的排序方法

几乎所有计算机中的序列都是被排过序的。电子邮件列表按照日期排序，最新的邮件被放置在最顶端；播放器中的歌曲按照名字或歌手名排列在一起，以便你快速查找到最喜欢的那首；文件名则往往是按照字母顺序排列的。那么计算机是如何进行排序的呢?

为了理解计算机的排序原理，我们可以先来考虑一下在现实生活中是如何排序的。在一次考试结束后，同学们把试卷都交上来了，老师为了便于评阅试卷和登记成绩，需要将试卷按学生的学号顺序排列好。假如你被老师安排来完成这项试卷排序的工作，你会怎么做呢?最通常的做法是:首先从这摞试卷中随便取出一份放在一边作为排好序的试卷，然后再从未排序的试卷中依次移出每张试卷将它们插入排好序的试卷中的正确位置(这里所说的正确位置是指插入后始终保持这摞整理好的试卷是按学号排好序的)。每成功插入一次，即意味着未排序的试卷减少了，排好序的试卷增加了，直到所有试卷被完全排列好。扑克牌玩家通常也是使用这种方法来理牌的。我们把这种方法称为直接插入排序法，这也是最简单的排序方法。该算法的重点在于如何将数值放入左侧序列(即已排好序的序列)中的正确位置上，而不是去考虑该在右侧的序列要挑出哪一个数值。(www.xing528.com)

另一种常用的排序方法也可以这样去做:考虑10个小朋友排队，为了让这些小朋友能按照身高从矮到高的次序站成一条整齐的队伍，我们可以先让第一个小朋友和第二个先比一比，让个子矮的站第一个、个子高的站第二个；然后让第二个和第三个比，同样让矮的站前面、高的站后面；……；如此下去，当比完第九个和第十个小朋友后，最高的小朋友就排到最后一个位置了。第二趟我们只需要对第一个到第九个小朋友按照相邻的进行比较，高的站后面，同样可以让第二高的小朋友排到第九个位置上。这样反复进行下去，直到第九趟对第一个和第二个小朋友进行比较后排好，所有排队工作就完成了。在排队过程中，我们可以发现每趟完成后，在排队范围内个子最高的小朋友就排到最后去了。在计算机学科中，形象地把这种排序方法称为冒泡排序。冒泡排序是一种需要将整个序列反复扫描，并交换所有相对位置错误的相邻数据的方法。当检查整个序列发现不用交换任何数据时便证明序列已被排好序了。