当前位置：首页 > news >正文

直接插入排序

news 2025/6/6 11:04:59

用一个生动的例子来比喻直接插入排序：打扑克时理牌的行为

在理牌的时候，我们会根据牌面的大小将其插入合适的位置，那么直接插入排序也是如此

直接插入排序：

直接插入排序可以看作是将待排序的内容分为两个部分，一部分为有序，一部分为无序，整个排序过程就是每次都从无序的部分里取出第一个元素，和有序部分的尾部元素开始往前进行比较，直到找到合适的位置进行插入就停止

过程模拟：

假设现在有一个序列如：2 5 3 0 6 4 需要对其使用直接插入排序进行升序排序

那么第一趟排序，第一个元素[ 2 ]就是有序部分，剩下的元素就为无序部分

①取出无序部分的第一个元素5，和有序部分的元素 [ 2 ] 进行比较，选择合适的位置插入

②因为5>2，所以 5 就放在 2 的后面，不进行移动改变，此时前两个数是有序的即[ 2，5 ]

此时第二趟排序，有序部分为[ 2，5 ]，剩下的元素就为无序部分

因为有序部分不止一个元素，使用end来指向有序部分中的元素，来控制两个部分之间的元素比较

使用end指向有序部分中待比较的位置，使用变量tmp保存待插入元素的值，因为比较过程中可能会挪动覆盖掉待插入的值，所以提前保存

①取出无序部分的第一个元素 3 即待插入的元素，用tmp变量保存起来，再和有序部分的元素 [ 2，5 ] 进行比较，使用end来指向每次待比较的元素，选择合适的位置插入

②使用 tmp 的值和 end 指向位置（有序部分中最后一个位置）的值即 5 进行比较，因为3<5，所以 end 位置的值即 5 移动到end+1的位置即 3 的位置或者说5的下一个位置，3就被覆盖

③此时比较完有序部分中的一个元素，end就进行减减--，指向有序部分中下一个待比较的元素，此时该元素为 2 ，因为tmp的值即 3>2 ，所以此时tmp就插入到end的下一个位置即end+1的位置

只要将tmp插入到合适的位置，那么该躺排序就结束

进入第三趟排序，有序部分为[ 2，3，5 ]，剩下的元素就为无序部分

此时待插入的元素为 0 ，tmp=0，end就指向有序部分末尾的位置，即5所在位置

① 使用tmp的值 0 与 end 指向的位置进行比较，0<5，end位置的值往后挪动即挪到到end+1的位置，即5覆盖掉0

② end进行减减--，指向有序部分的下一个待比较元素即3，因为tmp为0，0<3，所以3挪动到end+1的位置

③ end继续减减--，指向有序部分的下一个待比较元素即2，因为tmp为0，0<2，所以2挪动到end+1的位置

③ end再继续减减--，但是此时有序部分已经全部都比较完毕了，end--后等于-1，此时tmp的值就直接插入到end+1的位置即序列的第一个位置

那么剩下的无序部分依此类推，每次都取出无序部分的第一个元素与有序部分进行比较，直到找到合适的位置进行插入就结束

代码逻辑抽象：

先来单趟的逻辑：一个元素进行插入的过程

无论是通过找到比 tmp 小的元素而找到插入的位置结束即break，还是通过将有序部分的元素都比较完，而找到插入的位置结束即end<0，会发现最终插入的位置都是end+1的位置即end指向的位置的下一个

// 数组 int a[]={2,5,3,0,6,4}
int end;
int tmp=a[end+1];
while(end>=0) // 当有序部分都比较完了就结束
{if( tmp < a[end] ){a[end+1]=a[end]; // 元素向后挪动end--;}else{break; // tmp大于比较的元素，即找到合适的位置，结束比较}
}
// 循环结束即找到合适的位置，即为end+1,将tmp插入
a[end+1]=tmp;

完整代码：

// 数组 int a[]={2,5,3,0,6,4}
void InsertSort(int* a,int n)
{// 外层循环，控制有序部分范围,即end指向的位置for(int i=0;i<n-1;i++){int end=i;int tmp=a[end+1];while(end>=0) // 当有序部分都比较完了就结束{if( tmp < a[end] ){a[end+1]=a[end]; // 元素向后挪动end--;}else{break; // tmp大于比较的元素，即找到合适的位置，结束比较}}// 循环结束即找到合适的位置，即为end+1,将tmp插入a[end+1]=tmp;}
}