直接插入排序算法详解

喜欢ヅ旅行 2022-06-05 04:59 163阅读 0赞

直接插入排序算法到底是什么个情况呢？ 我们看到“直接”2个字，说明这个算法应该是先得到我们插入的位置，然后就直接插入进去没有什么比较过程就插入进去了。

那么直接插入排序算法的本质是什么呢，比如我们有一个有序数组 1 2 3 4 5 6 8 9  
我们想把一个8插入到当前数组中，可以肯定我们必须找到我们插入的位置 我们这里的位置是数据6的后面，这个6数据的索引5 因此我们的插入位置是索引为6

在日常生活中，经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中。例如:一组从小到大排好顺序的数据列\{1,2,3,4,5,6,7,9,10\}，通常称之为有序列，我们用序号1,2,3，…表示数据的位置，欲把一个新的数据8插入到上述序列中。

完成这个工作的步骤:

①确定数据”8”在原有序列中应该占有的位置序号。数据”8”所处的位置应满足小于或等于该位置右边所有的数据，大于其左边位置上所有的数据。

②将这个位置空出来，将数据”8”插进去。

直接插入排序(straight insertion sort)的做法是:

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

//插入排序算法  iArray待排序的数组    n数组中的元素个数
    void insertSort(int iArray[], int n)
    {
          //我们第一个元素假如是有序的
          //我们通过循环遍历得到除了第一个元素外的其他全部元素索引
          //可以操作元素插入到指定的属于他自己的位置
          for(int i = 1; i < n; i++)
          {
               //定义临时变量保存我们需要插入的元素
               int tempNeedInsert = i;
               //现在我们需要得到当前位置的前面的全部元素
               for(int j = i - 1; j >= 0; j--)
               {
                    //开始把当前i位置元素和他的前面元素进行一一对比找当前元素应该插入的位置
                    if(iArry[j] > iArray[i])
                    {
                        //在找到了比当前待插元素更大的元素我们就把大的元素后移一位
                        iArray[j + 1] = iArray[j];               
                    }else
                    {
                        //说明当前待排序的元素已经大于他的前面的这个元素
                        //说明我们已经找到我们插入元素的位置了
                        //那我们就没必要在循环寻找了
                        break;
                    }
               }
    
               //当前这个循环完毕的话说明我们已经找到待插入元素的索引了
               //准备插入我们的元素
               iArray[j + 1] = iArray[i];
          }
    }
    
    int main()
    {
        int iArray[5] = { 5,4,3,2,1 };
    
        insertion_sort(iArray, 5);
    
        for (int i = 0; i < 5; i++)
        {
            std::cout << iArray[i] << std::endl;
        }
        return 0;
    }