黑马程序员技术交流社区

标题: 【算法】插入排序 [打印本页]

作者: 倾心莫若初见 时间: 2016-12-23 14:38
标题: 【算法】插入排序
本帖最后由倾心莫若初见于 2017-4-27 17:44 编辑

<embed height="415" width="544" quality="high" allowfullscreen="true" type="application/x-shockwave-flash" src="//static.hdslb.com/miniloader.swf" flashvars="aid=9341105&page=1" pluginspage="//www.adobe.com/shockwave/download/download.cgi?P1_Prod_Version=ShockwaveFlash"></embed>

今天我们介绍一种排序算法，直接插入排序。插入排序的基本思想就是将无序的序列插入到有序序列中。

那么第一步，我们要想办法将待排序的序列分成两部分，一部分为有序的序列，一部分为无序序列，第二步，将无序序列中的元素逐个插入到有序序列中，从而使得整个序列变为有序序列。

现在呢，我们要做什么就清楚了，我们现在解决第一个问题，序列分为有序序列和无序序列，大家仔细想一下，当我们一个序列中只有一个元素的时候，那么这个只包含一个元素的序列是不是就成为了有序序列了呢？

上图可以看出序列 4,2,8,0,5,7,1,3,9分成了两个序列一个有序序列，包含一个元素4，另外一个序列为无序序列。这样，我们第一步解决了。

所以我们外层循环，只循环无序序列就可以，从下标为1的位置开始，直到len来遍历，将数据插入到有序序列中。

第二步，我们要将无序序列中的元素，也就是2,8,0,5,7,1,3,9逐个插入到有序序列中。

那么如何插入，我们现在假如序列排序是升序排列，也就是从小到大排序，那么我们让下标为1的元素和其紧挨着的左侧第一个元素4比较，如果比4小，我们就将元素4向右移动一个位置，那么元素4位置就是元素2的合适位置。序列变为：

从上图可以看出，我们整个序列还是分为两个序列，有序，无序序列，此时有序序列还是保持有序，已经有两个元素了。

我们下面继续遍历无序序列，下一个元素为8，我们就让元素8和其最左侧的元素4进行比较，因为我们是升序排列，所以当元素8小于4的时候，移动元素4的位置到元素8的位置，此时，元素8大于元素4，所以8为目前有序序列的最合适的位置，故而继续遍历，此时有序序列为：

现在继续将一下无序序列中的元素插入到有序序列中，下一个元素就是0，那么按照我们的排序目标，升序排列，元素0和其最左侧的元素进行比较，发现元素0小于元素8，那么将元素8移动到元素0的位置，然后继续元素0和有序序列中的元素4进行比较，此时发现元素0比元素4小，元素4向右移动一个位置，元素0继续和元素2比较，发现元素0又小于元素2，元素2向右移动一个位置，此时元素2位置为元素4之前的位置，元素0继续和有序序列中的元素比较，发现已经到左侧有序序列的边界，此时，比较结束，元素2之前的位置为元素0最合适和的位置，此时整个序列为：

此后无序序列中元素依照上面的规则，逐个插入到左侧有序序列中，直到无序序列中元素为空。

下面我贴出完整代码：

void InsertSort(int arr[],int len){

//遍历无序序列中的元素，我们从下标为1的位置开始

for (int i = 1; i < len; i ++){

//判断当前元素是否比左侧元素小

if (arr < arr[i - 1]){

//缓存下当前元素，因为可能发生数据移动，会覆盖当前数据

int temp = arr;

//从有序序列的最后一个元素倒叙和当前元素进行比较

                              int  j = i - 1;
   //如果当前待排序元素比有序序列当前元素小，或者达到有序序列左侧边界
            for  (; j >= 0 && temp < arr[j]; j --){
                        arr[j  + 1] = arr[j];
            }
   //将当前元素插入到有序序列合适的位置
                              arr[j  + 1] = temp;
            }
         }
}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2