开发者社区> 问答> 正文

c语言中数组排序里的插空排序法是什么意思啊?

知与谁同 2018-07-18 19:20:21 614
c语言中数组排序里的插空排序法是什么意思啊?
C语言
分享到
取消 提交回答
全部回答(2)
  • 美人迟暮
    2019-07-17 22:50:21
    它所做的过程是先移动较大的数据,然后再把移动后空出来的那个插入点 插入这个数
    因此不需要临时变量。
    因为最开始声明时候那数组肯定要比初始化的数目大,至少大1个,以便来存这个要插入的数
    所以这个数组最后就空出来一个位置,这样,依次把前面大的数向后移动一位,注意这个移动是从后面开始的
    比如我int a[11]; 总共初始化有10个已排好序的值,并有一个空位,我移动时,先把a[9]赋给
    a[10],即 a[10] = a[9]; 这样原来最后的一个数就真的变成数组中最后一个位置的数了
    依次下去a[9] = a[8]; 把8号位赋给9号位。。。。这样直到你那个插入点
    把插入点空出来了,就可以把那个值插进去了。
    0 0
  • 小旋风柴进
    2019-07-17 22:50:21
    插入排序法是一种数组元素排序方法,冒泡法也是。
    两者是不同的排序,两者时间复杂度为n的平方,而冒泡法更直观一点。

    插入排序就相当于打牌,假如你手里的牌是从小到大排好序的,那么你每摸一张牌,你就会根据这张牌的大小寻找这张牌应该插入的位置,然后插进去。
    选择排序就是你一下获得了所有的牌,这些牌是无序的,这时,你选择一个最大的牌放在前面,然后再从后面的牌选择最大的放在第2的位置,依此类推。

    插入排序是这样实现的:
    首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。
    从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。
    重复2号步骤,直至原数列为空。
    插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。
    void InsertSort(int* pData,int Count)
    {
    int iTemp;
    int iPos;
    for(int i=1;i<Count;i++)
    {
    iTemp = pData[i]; //保存要插入的数
    iPos = i-1; //被插入的数组数字个数
    while((iPos>=0) && (iTemp<pData[iPos]))
    { //从最后一个(最大数字)开始对比,大于它的数字往后移位
    pData[iPos+1] = pData[iPos];
    iPos--;
    }
    pData[iPos+1] = iTemp; //插入数字的位置
    }
    }
    0 0
添加回答

集结各类场景实战经验,助你开发运维畅行无忧

推荐文章
相似问题