vlambda博客
学习文章列表

插入排序，课件与代码都在下文中。

排序(三)：插入排序

本质逻辑：将一个数据接入入到一个已经有序的数组中。

逻辑步骤如下：

1、找到该数据应该在的位置。

   降序：找位置的条件是>=前一个 并且<=后一个。

    升序：找位置的条件是 <=前一个 并且>=后一个。

2、将该位置后面的数据依次向后移动1个位置，把数据存入此处。

如何给接入元素腾位置？

策略一：正着遍历数组。首先找位置，然后将该位置元素依次向后移动1个，最后后将元素赋值到该位置。

策略二：从被接入元素位置开始，反向遍历，一边移动一边找，到位赋值。

详细文字逻辑过程如下：

1、第1个元素自然成序，所以不用动，直接从第二个元素开始，将第二个元素接入第一个元素里。

2、第1次将第2个数据接入到前面1个成序数列里。

3、第2次将第3个数据接入到前面2个成序数列里。

4、第3次将第4个数据接入到前面3个成序数列里。

......

5、第n次将第n+1个数据接入到前面n个成序数列里。

图示过程如下，视频中有讲解。

代码逻辑：

1、外层循环代表无序的数据，即1~6。

记录被接入的数据

2、内层循环代表有序的部分，在有序中找位置。比如前5个数据有序了，那么就是遍历0~4下标。

如果位置到了，接入并跳出。

如果比最小还大，需要接入到第一个位置，接入并跳出。

向后移动。

#include <stdio.h>

int main(void)

{

int arr[7] = {1,6,1,2,8,3,7};

for (int i = 1; i <= 6; i++)  //6个数据需要插入，第一个元素不需要

{

int temp = arr[i];    //第一次记6，第二次记1，第三次记2，依次

for (int j = i -1; j >= 0; j--)

{

if (arr[j] >= temp)     //条件 要不要停下来

{

arr[j + 1] = temp;//找到了，元素装进去

break;   //装完就跳出，开始下个插入数据

}

arr[j + 1] = arr[j];   //向后移动

if (0 == j)              //特殊情况，需要接入到第一个位置

arr[0] = temp;

}

}

return 0;

}

遍历输出数组的代码大家就自己写吧，一个循环。