您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 直接插入 >

c语言直接插入排序中的监视哨问题?

发布时间:2019-07-13 22:26 来源:未知 编辑:admin

  补充就是,假如两个数组,一个是有序,另一个无序。如果我想将无序的插入有序中,那么每一次插入前,我是不是应该先将有序的数组往后空一位,把地址0给空出来

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  1.具有数据库系统的基础知识。 2.基本了解面向对象的概念。 3.掌握关系数据库的基本原理。 4.掌握数据库程序设计方法。 5. 能使用Access建立一个小型数据库应用系统。

  从前往后依次将每一个元素插入到前面已排好的序列中,如当插入到arr[i]时,arr[0]至arr[i-1]已排好序了,将arr[i]与arr[0],arr[2],arr[2],…arr[i-1]依次比较,直到找到正确的插入位置,当把最后一个元素插入完成时,排序结束。

  我们可以将它拆开成两部分,arr[0]是已排好序的,之后全部是未排序的:

  首先从arr[1]开始(i=1时),我们将arr[1]插入到前面已排好的序列arr[0]~arr[0]中(即arr[0]~arr[i-1]),让arr[1]依次与已排好的序列中每个元素比较,找比6大的元素,没找到,插入到末尾。

  然后接着下一个,当i=2时,将arr[2]插入到前面已排好的序列arr[0]~arr[1]中(即arr[0]~arr[i-1]),让arr[2]依次与已排好的序列中每个元素比较,找比5大的,最后找到6,将5插入到6的位置,6及6以后已排序元素依次后移。

  i依次增大,每一步将arr[i]插入到arr[0]~arr[i-1]中,直到i等于元素总个数,说明已全部排序完成,退出循环。

  这种方式第一次查找插入位置的时候需要将这些元素遍历一遍,移动的时候又得遍历一遍,进行了重复的运算,如果第一步寻找插入位置时,我们从后往前寻找插入位置的话,第一步和第二步就可以一起进行:

  从i-1出向前遍历,如果该元素大于此次要插入的元素,往后移动一格,直到找到一个不大于的或到达arr[0]处

  做到这里,我本以为这个函数已经搞定了,然后查了些资料,对比了一下自己的代码,发现有很多提到了“监视哨”,然后研究了一下。

  传进来的那个数组arr,arr[0]中不存储有用的元素,所有的数据存在arr[1]~arr[length]中(传入函数的length值我们规定为有用的元素个数,最后一个元素就是arr[length]),arr[0]就是监视哨,有两个作用:

  第一个作用是用来存储每次待插入的元素,作用和上面那个函数中设置的变量key一样,监视哨要是只有这么一个作用的话,我们为什么要舍弃创建一个临时变量这么简单的办法不用而去用它呢,所以我仔细研究了一下监视哨的第二个作用。

  注意for循环的判定部分,如果将待插入元素存储在arr[0]中,可以省掉这个这个判断条件。

  那么当这个循环体结束时有两种情况,第一种是遇见了第一个不大于arr[0]的元素,此时只要将arr[0]的值赋给arr[j+1]就可以了。

  第二种情况是所有元素都不大于arr[0],j会一直减到0退出,此时只需要把arr[0]赋给arr[1]就好了,arr[1]刚好也是arr[j+1],

  发现设置监视哨确实可以省略判断j=0这一步,可不要小看了这一步,一次循环少判断一次,n次循环就少判断n次,当要排序的元素数量极其庞大时,提高的效率就十分可观了。

http://w5bek.com/zhijiecharu/217.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有