`
RednaxelaFX
  • 浏览: 3047633 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

奇怪的插入排序?

阅读更多
忍不住想发牢骚。不是我自己遇到的啥面试笔试题啦。

如果给你这样的题目要填空:
引用
// a是密集的number数组,不让用Array的内建方法
function insertion_sort(a) {
  for (var i = 1; i < a.length; i++) {
    var t = a[i];
    var j = 0;
    for (_____;_____;_____) {
      __________;
    }
    a[j + 1] = t;
  }
}

你会怎么做?

既然是插入排序,外层循环这里是从前向后排序,应该保证每轮循环进入时a.slice(0, i)都已经排好序,然后为下标为i的元素在前面找到合适的插入位置插进去。

按这填空题的写法,内层循环的变量j是控制遍历和插入的,初始值为0也就是从前向后遍历找插入位置,最终把原本下标为i的元素插入到下标为j+1的地方。

这⋯⋯从前向后遍历要怎么把插入位置之后的元素向后挪,这是不让用Array内建方法的数组啊orz

==============================================

这题咋出得那么诡异⋯正常的插入排序(升序)的话得是这样吧:
function insertion_sort(a) {
  for (var i = 1; i < a.length; i++) {
    var t = a[i];
    var j = i;
    for ( ; j > 0 && a[j - 1] > temp; j--) {
      a[j] = a[j - 1];
    }
    a[j] = t;
  }
}

也就是内层循环应该从下标i开始从后向前遍历找插入位置,直观。

或者如果用wiki给的算法的变量名的话:
function insertion_sort(a) {
  for (var i = 1; i < a.length; i++) {
    var valueToInsert = a[i];
    var holePos = i;
    for ( ; holePos > 0 && a[holePos - 1] > valueToInsert; j--) {
      a[holePos] = a[holePos - 1];
    }
    a[holePos] = valueToInsert;
  }
}


当然我们可以把这种写法填到原本题目的空里,把原来的j = 0架空就好了:
function insertion_sort(a) {
  for (var i = 1; i < a.length; i++) {
    var t = a[i];
    var j = 0;
    for (var k = i; k > 0 && a[k - 1] > t; k--) {
      a[k] = a[k - 1]; j = k - 1;
    }
    a[j + 1] = t;
  }
}


function insertion_sort(a) {
  for (var i = 1; i < a.length; i++) {
    var t = a[i];
    var j = 0;
    for (j = i - 1; j >= 0 && a[j] > t; j--) {
      a[j + 1] = a[j];
    }
    a[j + 1] = t;
  }
}

但出题的人多半不是这样想的⋯吧?不然给j赋值为0干嘛,忽悠学生?
分享到:
评论
2 楼 RednaxelaFX 2013-10-27  
lpdl 写道
function insert_sort(a){
  for(var i = 1; i < a.length; i++) {
    var t = a[i];
    var j=0;
    for(;(j<i && a[i-j-1]>t) ||((j=i-j-1) && 0);j++) {
      a[i-j]=a[i-j-1];
    }
      a[j+1]=t;
  }
}

这样?

哈哈哈这也是一种架空j的方式,让它在循环中跟离开循环时意义发生变化。如果标准答案是这样的话我仍然觉得这是坑学生。
1 楼 lpdl 2013-10-27  
function insert_sort(a){
  for(var i = 1; i < a.length; i++) {
    var t = a[i];
    var j=0;
    for(;(j<i && a[i-j-1]>t) ||((j=i-j-1) && 0);j++) {
      a[i-j]=a[i-j-1];
    }
      a[j+1]=t;
  }
}

这样?

相关推荐

    你必须知道的495个C语言问题

    1.28 文件中的第一个声明就报出奇怪的语法错误,可我看没什么问题。这是为什么? 1.29 为什么我的编译器不允许我定义大数组,如doublearray[256][256]? 命名空间 1.30如何判断哪些标识符可以使用,哪些被保留了...

    《你必须知道的495个C语言问题》

    1.28 文件中的第一个声明就报出奇怪的语法错误,可我看没什么问题。这是为什么? 15 1.29 为什么我的编译器不允许我定义大数组,如double array[256][256]? 15 命名空间 15 1.30 如何判断哪些标识符可以使用,...

    C语言FAQ 常见问题列表

    但是我得到了奇怪的结果。 o 8.3 但是 strcat 的手册页说它接受两个 char * 型参数。我怎么知道 (空间) 分配的事情呢? o 8.4 我刚才试了这样的代码 char *p; strcpy(p, "abc"); 而它运行正常?怎么回事?为什么...

    2015年第六届蓝桥杯大赛个人赛省赛(软件类)

    9. **排序与查找算法**:如冒泡排序、选择排序、插入排序、快速排序、二分查找等,这些基本算法是解决问题的基础。 10. **数据结构**:包括栈、队列、树(如二叉树、AVL树、红黑树)、图等,它们在解决复杂问题时...

    数据结构与算法分析(c语言描述)第二版 习题解答 英文原版

    排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等,它们的性能分析在这一章也会被详细探讨。 第8章“The Disjoint Set ADT(不相交集抽象数据类型)”讲述了一种特殊的抽象数据类型,它用于在不...

    C/C++程序员面试指南.杨国祥(带详细书签).pdf

    面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速排序 11.3 选择排序 面试题5:编码实现直接选择排序 面试题6:编程实现堆排序 ...

    你必须知道的495个C语言问题(PDF)

    老资源。...5.10 这有点奇怪。NULL 可以确保是0, 但空(null) 指针却不一定? . . 24 5.11 为什么有那么多关于空指针的疑惑?为什么这些问题如此经常地 出现? . . . . . . . . . . . . . . . . . . . ...

    数据结构与算法分析(英文版)第二版答案

    本章将涵盖常见的排序算法,如冒泡排序、选择排序、插入排序、归并排序、快速排序等,并分析各自的优缺点。 #### Chapter 8: The Disjoint Set ADT 不相交集合(Disjoint Sets)是一种抽象数据类型,用于表示一组...

    超级有影响力霸气的Java面试题大全文档

    Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...

    levenshtein-dictionary:字典词的探索与重排

    Levenshtein距离是一种衡量两个字符串之间差异的度量,通过计算最少的单字符编辑操作(插入、删除或替换)数量来将一个字符串转换为另一个字符串。 Levenshtein距离算法的核心思想是动态规划,它能够有效地找到两个...

    Jobdu-OJ.zip_教育系统应用_C/C++_

    4. "1029 魔咒词典.cpp" 可能是一个字符串处理或字典树的问题,可能需要实现查找或插入操作,或者寻找特定模式的字符串。 5. "1449 确定比赛名次.cpp" 可能涉及到排序算法,比如快速排序、归并排序等,用来确定比赛...

    smaxer-crx插件

    smaxer:为PGCPS老师的SchoolMAX...•“成绩报告卡格式” - 学生GPA将自动插入(修正3/24/11) •改善考勤中的“更改日期” •自动显示“所有”班级,而不是“今天的班级”(主页→学生→学生时间表) 支持语言:English

    C#微软培训资料

    &lt;&lt;page 1&gt;&gt; page begin==================== 目 目目 目 录 录录 录 第一部分 C#语言概述.4 第一章 第一章第一章 第一章 .NET 编 编 ... 比尔....这一天 微软公司正式推出了其下一代...

Global site tag (gtag.js) - Google Analytics