首页 > 代码库 > 数据结构与算法学习之路:直接插入排序

数据结构与算法学习之路:直接插入排序

一、什么是直接插入排序:

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

简单来说,就是把待排序的数组,分为有序组和无序组。假设数组有n个元素,初始有序组只有一个元素,无序组有n-1个元素。然后不断拿无序组的第一个元素与有序组的元素进行对比,将这个元素插入到恰当的位置,使得有序组元素数增加,因为这个元素已经在有序组里了,此时无序组元素将减少。循环进行这个过程,最后一整个数组就是有序的了。

如果觉得这样的描述太难理解,不妨想想打牌了时候,你是怎么把牌排序的 -..-。或者看看下面的图:


二、算法分析:



三、代码:

void DirectInsert_Sort(int* nums, int length){<span style="white-space:pre">	</span>int i, j;<span style="white-space:pre">	</span>for (i = 2; i < length; ++i){<span style="white-space:pre">		</span>nums[0] = nums[i];<span style="white-space:pre">		</span>for (j = i - 1; j > 0; --j)<span style="white-space:pre">			</span>if (nums[j] >= nums[0])<span style="white-space:pre">				</span>nums[j + 1] = nums[j];<span style="white-space:pre">			</span>else<span style="white-space:pre">				</span>break;<span style="white-space:pre">		</span>nums[j + 1] = nums[0];<span style="white-space:pre">	</span>}


数据结构与算法学习之路:直接插入排序