数据结构——直接插入排序

一、基本知识1.排序默认递增。2.定义每一趟把待排序序列的第一个值插入到前面的已经排序好的序列。不申请额外的空间在原序列的基础上进行排序所以就需要避免覆盖的问题。二、基本原理将数组分成已排序区间和未排序区间1.第一个元素单独作为已排序区间剩余所有元素是未排序区间假设我们现在有一个待排序序列默认第一个数据就是一个已经排序好的序列因为我们此时将第一个数据看成一个单独的序列因为只有一个数据所以不存在是否有序无序也就是说它是一个有序序列。2.依次取出未排序区间的第一个元素向前插入到已排序区间的合适位置。以上面序列为例①第一趟思想未排序区间第一个元素是18根据比较得到1859又因为默认排序是递增的所以18应该在59的左边。操作此时我们已经知道18应该在0号下标59应该在1号下标但是插入排序是在原序列的基础上进行排序所以在数据移动时就需要将18提前拷贝下来避免覆盖之后让59进行数据移动到1号下标再让已经拷贝下来的18移动到0号下标。此时已排序好的序列就是18 59 从72开始就是未排序序列②第二趟思想此时72是未排序区间的第一个值将72和已排序区间59 18进行比较因为序列是递增的所以我们发现72比59大所以72应该放在59的后面。操作我们将待排序序列的第一个值拷贝下来因为计算机开始不知道这个待排序数据应该在那个下标所以我们还是要先将待排序的数据进行拷贝避免后续可能会出现的数据覆盖。将72和已经排序好的序列进行比较5972所以72应该放置在59的后面。所以此时 18 59 72 是已经排序好的序列从85开始是未排序好的序列。③第三趟思想此时85是未排序序列的第一个元素将85和已排序好的序列18 59 72进行排序因为序列是递增的所以我们发现85比72小应该放在72的后面。操作将待排序序列的第一个元素85拷贝下来和已经排序好的序列进行数据比较728585就放到72的后面④后续雷同............三、代码实现void Insert_Sort(int arr[], int len) { for (int i 1;i len;i)//控制的是趟数 { int temp arr[i]; int j i - 1; for (;j 0;i--)//控制的是对已经排好的序列从右至左依次遍历 { if (temparr[j])//如果比我取出来的temp大向后挪动 { arr[j 1] arr[j]; } else { break; //情况1遇到了不大于我的值停下来把值放回去。 } } //情况2越界了停下来把值放回去 arr[j 1] temp; } }