利用拿扑克牌让你几分钟搞定插入排序算法

我会带着你远行 2022-06-04 23:29 125阅读 0赞

![这里写图片描述][SouthEast]

先拿一个j，然后拿到一个k放在j的后面

![这里写图片描述][SouthEast 1]

接着拿到一个A,放入k后面，

![这里写图片描述][SouthEast 2]

现在拿到一个Q 那么我们必须把Q插入到K中，那么我们必须拿Q和A到J之间的一一比较最终找到一个合适的位置插进去。

现在上代码

//插入排序算法   需要参数为待排序数组以及数组的元素个数n
    void Insertion_Sort(ElementType A[], int n)
    {
           //代表数组的1到n-1的索引  表示我们假如手里有了n张牌，那么我们第一张牌假定开始是有序的，
           //那么我们就先不动第一张牌，也就是我们没有必须去拿到第一数组元素的索引。
           //我们给我们手里是怎么排序的呢，我们是不动第一张牌，然后找到第二张牌，也就是索引为1对应的元素，
           //然后我们需要拿到这个索引为1的牌和索引为0也就是他前面的牌进行比较大小，如果前面的牌大于后面的
           //那么我们就交换这2张牌，直到我这张牌前面的牌全部比较过，那么我们是怎么交换的呢，
           //首先假如我们索引为2的牌小于索引为1的牌，那么我们提前把索引为2的牌先保存在临时变量，以免被前面的小牌覆盖
           //是这样的，如果索引为1的牌大的话，现在我们就可以把索引为1的牌放到索引为2的地方。
           // 然后我们接着拿那个被临时保存的索引为2的数据接着喝索引为0的牌比较大小。如果索引0的牌还是比这
           //这个临时牌大，那么我们就把这个索引为0的牌放到索引为1的位置，覆盖以前索引为1的数据是没有问题的，
           //因为索引为1的数据已经存在了索引为2的地方。
           //反之假如索引为0的地方数据已经大于那个临时值，这样的话我们就把这个临时数据存到索引为1的地方。这
           //个情况下我们的数据也就是从索引2到索引0之间的数据肯定是有序的，这个是我们第一趟排序，我们总共有
           //n张牌的话，就需要做n - 1趟排序就全部牌是有序了
          for(int i = 1; i < n; i++)   //因此这个下标是从1开始也就是索引为1开始到n -1
          {
               int j; 
               ElementType temp = A[i];  //把当前趟的数据先临时保存，以免前面的大数据移动覆盖他
    
               //这里是真正的比较牌大小的过程，因为是要把当前拿到的牌和这个牌前面的全部比较
               //因此我们又需要一个循环  并且里面的变量j是直接对应数组的索引的
               //我们初始j = i也就是拿到的牌   
               //j这个下标不能一直减少，因为我的牌最前面的一个的索引就是0  所以必须大于=0
               for( j = i; j >= 0; j--)  
               {
                   //开始拿手里的牌和前面的牌进行一一比较大小
                   if(A[j - 1] > temp)
                   {
                      //当前的牌小于前面的牌我们就把前面这个牌放到当前牌的位置
                      A[j] = A[j - 1];
                   }
               }
    
               //当代码执行到这来的时候说明当前索引的数据小于了当前的temp也就是手中的牌
               // 这个时候我们得到的数据的索引下标是j-1,也就是A[j - 1] < temp
               // 那么我们就可以把当前手中的牌放在当前索引为j - 1牌后面那个位置既j的位置          
               A[j] = temp;//写入数据
          }
          //全部执行完后就全部有序了
    }

[SouthEast]: /images/20220605/7ae3653865354340bbe786a407200d00.png
[SouthEast 1]: /images/20220605/b6c90e169b304af49fbd8fb8e65b21f5.png
[SouthEast 2]: /images/20220605/8a0e242461484ef79b0a819f1a7c21d3.png