直接插入排序法

插入排序（Insertion Sort）的算法是一种简单直观的排序算法。

它的工作原理是通过对未排序的数据逐个插入合适的位置完 成排序的工作。

插入排序在算法实现时，在从后向前扫描过程中，需要反复把已排序元素逐步向后移动，为最新元素提供插入空间。

算法描述 

一般地，插入排序都在一个数组上进行。具体算法描述如下： 

（1）对于第1个元素，因为没有比较，将其作为已经有序的序列。 

（2）从数组中获取下一个元素，在已经排序的元素序列中从后向前扫描，并判断该元素与已排序元素的大小。 

（3）若排序序列的元素大于新元素，则将该元素移到下一位置。 

（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。 

（5）将新元素插入到该位置。 

（6）重复步骤2~5，直到将数组中的数据处理完。

下面以一组待排序的数据演示插入排序的过程，假设有8个需要排序的数据序列如下：

 69，65，90，37，92，6，28，54

通过插入排序法进行排序的过程如上图所示。 

（1）在原始数据中，将第1个数据作为已排序的数据序列。 

（2）取出第2个数据，将其与已排序的数据进行比较，因第2个数据小于第1个数据，将这两个数据进行交换，完成第1次插 入排序。 

（3）取出第3个数据，将其与已排序的数据（前两个数据）进行比较，因第3个数据大于已排序的两个数据，不需要进行交 换。 

（4）这样重复操作，最后得到有序的数据序列。 

注意 由图可看出，在插入排序中，可能会存在大量数据的移动操作。例如，第5次排序时，取第6个数据（值为6）， 因为该值比所有数据都小，因此需要向前移动6次才完成排序。