排序算法(1)-插入排序【史上最保姆级的教程】

文章目录 隐藏

前言

几大经典排序法的各种情况用一张图概括：

这里我们第一个先介绍插入排序。

一、插入排序的基本原理

可以对着动态示意图看着文字解释：

初始状态：
将待排序序列的第一个元素视为已排序部分（上图中的黄色部分）
其余元素为未排序部分(蓝色部分)。
上图中数组 {5, 2, 4, 6, 1, 3}
第一步，首先将数组的第一个元素，也就是下标、索引为0的数–{5}看成已排序的部分
剩下未排序部分为 {2, 4, 6, 1, 3}。
则数组{5, 2, 4, 6, 1, 3}
逐步插入：
从未排序部分取出第一个元素作为当前元素，将其与已排序部分的元素从后往前比较。
如果当前元素比已排序部分的某个元素小，则将已排序部分的元素后移一位，腾出位置。
重复上述步骤，直到找到当前元素的合适插入位置。
最终结果：所有元素都被插入到已排序部分后，整个序列变为有序。

简单来说

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤2-5。

二、插入排序的步骤示例

如上面动态图所示，这里我用文字形式方便大家阅读：

初始

最开始拿到下面这个数组
{5, 2, 4, 6, 1, 3}

先分两个部分

分为已排序和未排序两个部分。

将数组第一个元素看成已排序部分(橙色)，剩下的为未排序部分(蓝色)
{5, 2, 4, 6, 1, 3}

取未排序部分第一个元素

取未排序部分的第一个元素作为“当前元素”。这个当前元素和已排序部分的最后一个元素比较。
他们俩的关系其实就是靠在一块的，已排序部分的最后一个元素的下一个元素一定是未排序部分的第一个元素。
这里当前元素是 2 ，未排序部分因为现在只有一个数，就是5。

存储当前元素

将当前元素 2 存储在一个中间变量 key 当中。这时候原来 2 的位置就是空的。如下：
{5,[空],4, 6, 1, 3} 也就是数组索引为 1 的位置是空的。2存在变量key当中。

`比较`

现在让key和已排序部分比较，从已排序部分最后一个数字开始比较。这里只有5。key是 2。所以 5 > key
所以要交换元素

交换

现在数组
{5,[空],4, 6, 1, 3}
让 5 去空的那个位置。
{[空],5,4, 6, 1, 3}
这时候原来 5 的位置，即索引为 0 的位置是空的。

现在将存在 key 中的 2 赋值给空出来的那个位置。数组变为下面的样子：
{2,5,4, 6, 1, 3}

这样就完成了一次排序，重复上面的过程，到最后就可以得到正确的排序。

三、代码以及解释

 void insertionSort(int arr[], int n) 
 {
     int i, j, key;
     for (i = 1; i = 0 && arr[j] > key) 
         {c
             arr[j + 1] = arr[j];  // 元素后移
             j--;
         }
         arr[j + 1] = key;  // 插入到正确位置
     }
 }

咱们一行一行解释：

for (i = 1; i

第四行中，循环从‘i=1’开始，因为刚开始就将待排序序列的第一个元素(索引为i=0)视为“已排序部分”，所以未排序部分是从索引“i=1”开始的元素，也就是第二个数字。

数组元素 :{5,[空],4, 6, 1, 3} 下标(i/j):[0，1 ，2，3，4，5]
初始时已排序部分只有 {5}，未排序部分为 {2, 4, 6, 1, 3}。

i=0 就是{5} i=1 就是{2}

从索引i=1开始循环直到数组末尾（i ）

key = arr[i]

第六行key = arr[i]; 就是将当前待排序元素的值保存到 key 变量中

数组元素 :{5,[空],4, 6, 1, 3} 下标(i/j):[0，1 ，2，3，4，5]

i=1的时候，arr[i] 就是2，也就是将 2 存放在变量key中。这时，arr[1]就是一个空壳子，里面没有数值了。

数组元素:{5,[空],4, 6, 1, 3} 下标(i) :[0，1 ，2，3，4，5] key = 2

需要注意的是，代码中的 i 永远表示待排序部分的第一个，那么 i 前一个就是 i-1，就是已排序部分的最后一个，在下面我们使用 j 表示。

j=i-1

第7行 j=i-1; 这里j 指向已排序部分的最后一个元素（当前元素的前一个位置）

while(j>=0 && arr[j]>key)

第十行 while (j >= 0 && arr[j] > key) 是说在 j 的值大于等于0，并且 arr[j] 大于 key的值对于数组{5,[空],4, 6, 1, 3}，在刚刚 i=1时候，j = 0
那么 arr[j]=arr[0]=5
则 key = arr[i] = arr[1] = 2
由于arr[1]已经赋值给key,现在就是一个空壳子，里面没有数值了。=

他们的作用：

条件 j >= 0：确保不越界（不到达数组开头之前）
条件 arr[j] > key：当前比较元素大于待插入元素时继续循环

arr[j+1] = arr[j]

第十二行arr[j + 1] = arr[j]; 是将较大的元素向右移动一位，为 key 腾出插入空间

对于数组
数组元素 :{5,[空],4, 6, 1, 3} 下标(i/j):[0，1 ，2，3，4，5]

同样i=1时候，j = 0
arr[j+1]=arr[j] 就是 arr[1]=arr[0]
arr[1]已经赋值给key,现在就是一个空壳子
现在 arr[0]的数值 5 给了这个空壳子,也就是就是将数字5赋值给arr[1]
那么数组变成下面这样：

数组元素 :{[空],5，4, 6, 1, 3} 下标(i/j):[ 0 ，1，2，3，4，5] key = 2

这样数字5从原来序列的第一个变成序列的第二个
索引为 0 的元素变成空壳，下面用来放 key 的值达到交换让索引 0 和 1 的值交换的目的。

j–

第十三行j--; 将内层循环索引向左移动，继续与前一个元素比较。

注意，j原来是j = i-1 = 0 ，j--之后 j = -1
也就是现在 j = -1

arr[j+1] = key

第十五行arr[j + 1] = key; 将key的值赋值给arr[j+1]
key是从arr[1]里面拿的2,
现在把2赋值给arr[j+1]。
注意现在j=-1，所以arr[j+1] = arr[0]
就是将 2 赋值给arr[0]

现在的序列是：

数组元素 :{2，5，4, 6, 1, 3} 下标(i/j):[0，1，2，3，4，5]

这样就完成了一次排序接着让 i=2 循环多次，就可以排序完成。

完整代码示例

#include 

void insertionSort(int arr[], int n) // n 是数组的长度
{
    int i, j, key;
    for (i = 1; i = 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];  // 元素后移
            j--;
        }
        arr[j + 1] = key;  // 插入到正确位置
    }
}

int main() 
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
    
    printf("排序前: ");
    for (int i = 0; i

文章来源于互联网:排序算法(1)-插入排序【史上最保姆级的教程】

相关推荐: 打卡信奥刷题（1785）用C++实现信奥 P8804 [蓝桥杯 2022 国 B] 故障

P8804 [蓝桥杯 2022 国 B] 故障题目描述在软件或系统开发中，我们会遇到各种各样的故障。为了从故障现象反推故障原因，工程师们会总结一种叫做相关性矩阵的二维表格，来表示故障原因与故障现象之间的关系。比如: 其中每行表示一种故障原因，每一列表示一种…