C++算法之直接插入排序算法详解

C++算法之直接插入排序算法详解

//直接插入排序 array待排序的数组  n数组的元素个数
void InsertSort(int[] array, int n)
{
    //我们默认第一个元素也就是索引为0的有序
    //循环遍历索引1--n-1对应的数据进行排序 
    //依次从索引1开始到最后一个元素一一和当前索引前面的元素进行一一的比较进行排序
    //定义循环需要的变量
    int i = 1;  //默认为1，我们就从索引为1开始排序
    for(i; i <= n - 1; i++)
    {
          //开临时内存把当前需要排序的元素先缓存，因为可能前面的元素会后移操作以免覆盖
          int temp = array[i];  
          //由于前面会有很多元素,因此我们可以用一个循环比较

          //定义变量j 用于循环中依次索引当前被比较元素的前面元素的下标
          int j = i;
          while(true)
          {
              //不能一直循环吧，那么下标肯定越界，所以我们需要控制下标，也就是我们前面已经没                           、            //有元素需要比较就退出循环
              if(j <= 0) //为什么j不可以==0,注意我们下面用的找前面的元素用的索引是j-1
              break;
              //当当前元素比他的前面元素小的情况下
              if(temp < arry[j - 1])
              {
                    arrray[j] = array[j - 1]; //元素后移
                   //索引下标进行前移，让我们得到当前比较元素的下一个比较目标
                   j--;
              }
              else  //出现了当前比较元素temp大于前面的元素,那么就不必比较了
              {
                    //把temp里面的数据写入当前腾出来的空
                    arry[j] = temp;
                    break;  //当前元素前面元素都是有序的，那么本次排序结束
              }
          }
    }
}


针对算法设计的时间复杂度分析:
最好的情况那就是我们的元素就已经是有序这个时候我们还是会执行比较的也就是1 + 2 + ... + n-1次,但是没有移动元素。求和得到n/2   那么时间复杂度就是0(n)
最坏的情况我们的数组是逆序的，时间复杂度是0(n^2)