liupeng19881028
liupeng19881028
采纳率100%
2017-11-10 01:50

求助大神!!! 谁能帮讲一下这个函数的思想吗?主要是第二个for循环这里。

2
  • 插入排序
已采纳

// 插入排序

void insertSort(int array[], int length)

{

int i, j, key;

for (i = 1; i < length; i++)

{

key = array[i];

// 把i之前大于array[i]的数据向后移动

for (j = i - 1; j >= 0 && array[j] > key; j--)

{

array[j + 1] = array[j];

}

// 在合适位置安放当前元素

array[j + 1] = key;

}

}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

9条回答

  • liangshilin -瞌睡虫- 4年前

    假设数组:3 2 1 4
    第一次循环: i = 1 => key = 2

    进入第二个for:j=0 即 array[j] = 3 大于 key 则交换 此时数组:2 3 1 4
    第二次循环: i = 2 => key = 1

    进入第二个 for:j = 1 即 array[j] = 3 大于 key 则交换 此时数组:2 3 3 4
    j = 0 即 array[j] = 2 仍然大于 key 交换 数组:2 2 3 4 跳出第二个for 时 数组:1 2 3 4

    点赞 1 评论 复制链接分享
  • zhangli00 csulizhang 4年前

    最好的办法就是你随便写一个数组,然后跟着算法走,就了解清楚了
    这个算法的思想是:从前往后扫描数组(第一个循环),把当前数组元素作为key(比较对象),让这个key跟它前面的所有数组元素进行比较(第二个循环),当满足条件的时候(array[j] > key),就把两个元素交换位置,直到比较完成或第二循环条件达到,继续回到第一循环,扫描下一个数组元素。
    说白了,根据这个代码,就是逐个扫描数组元素,把小的元素放前面,大的放后面,最后得到一个从小到大排列的数组

    点赞 1 评论 复制链接分享
  • weixin_40323410 weixin_40323410 4年前

    第二个for循环就是在找当前key应该插入的位置,如果array[j] > key,就让当前元素后移一个位置,直到找到key的合适位置

    点赞 评论 复制链接分享
  • baidu_15903647 冬煦 4年前

    i从1开始(即数组的第2位元素开始),当前为第i位元素,保证前i-1位有序的情况下,在内循环中,从i-1位开始找到所有比第i位元素大的向后移一位,此时空出来的数组的元素序列为j,即第i位数插入的位置。这样循环到最后就保证所有的数在自己应该的位置。

    点赞 评论 复制链接分享
  • qq_24712507 奔跑的_迷彩狼 4年前

    如果对第二个循环不懂的话,就自己举个例子,注释写的已经很清楚了。就是把小于key的全部后移,然后在循环外把key放在合适的位置。
    如果你担心数据被覆盖,,,在循环前已经付给key了,所以覆盖也没事。

    点赞 评论 复制链接分享
  • qq_33220645 木易匕禾页 4年前
        您好,你可以用三个数读一遍程序就可以理解了  5            21        17
        三个数外循环只需要2次就可以出结果
    因为每次到第二个for循环前面都是排好序的
        第二个for循环主要是判断
            1,当前这个数前面的如果比这个数大就向后移一下array[j + 1] = array[j]  ,不满足就插入到不满足的这个数后面
            2,如果前面所有数字都比它大,就把这个数放在第一个
    
    点赞 评论 复制链接分享
  • unique_miao 大白不乖 4年前

    第二个for循环就是在找当前key应该插入的位置,如果array[j] > key,就让当前元素后移一个位置,直到找到key的合适位置

    点赞 评论 复制链接分享
  • wangtong95 w狸猫 4年前

    因为在检查第i个元素时,第i个元素以前的元素都是有序的,
    所以 当第j个元素小于或者等于array[i]时,j以前的元素也必然小于等于key,所以没必要检查了。

    第二个for主要是将 第i个元素以前 所有大于array[i] 的元素向后移一位。

    插入排序的主要思想是 将 第i个元素 从后向前检查,直到遇到比他小的,然后把这个元素放置在比他小的后面。这就是为什么最后一句是 j+1

    点赞 评论 复制链接分享
  • qq_40919174 qq_40919174 4年前

    感觉跟冒泡排序查不多额

    点赞 评论 复制链接分享