忍不住想发牢骚。不是我自己遇到的啥面试笔试题啦。
如果给你这样的题目要填空:
引用
// 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干嘛,忽悠学生?
分享到:
相关推荐
1.28 文件中的第一个声明就报出奇怪的语法错误,可我看没什么问题。这是为什么? 1.29 为什么我的编译器不允许我定义大数组,如doublearray[256][256]? 命名空间 1.30如何判断哪些标识符可以使用,哪些被保留了...
1.28 文件中的第一个声明就报出奇怪的语法错误,可我看没什么问题。这是为什么? 15 1.29 为什么我的编译器不允许我定义大数组,如double array[256][256]? 15 命名空间 15 1.30 如何判断哪些标识符可以使用,...
但是我得到了奇怪的结果。 o 8.3 但是 strcat 的手册页说它接受两个 char * 型参数。我怎么知道 (空间) 分配的事情呢? o 8.4 我刚才试了这样的代码 char *p; strcpy(p, "abc"); 而它运行正常?怎么回事?为什么...
9. **排序与查找算法**:如冒泡排序、选择排序、插入排序、快速排序、二分查找等,这些基本算法是解决问题的基础。 10. **数据结构**:包括栈、队列、树(如二叉树、AVL树、红黑树)、图等,它们在解决复杂问题时...
排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等,它们的性能分析在这一章也会被详细探讨。 第8章“The Disjoint Set ADT(不相交集抽象数据类型)”讲述了一种特殊的抽象数据类型,它用于在不...
面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速排序 11.3 选择排序 面试题5:编码实现直接选择排序 面试题6:编程实现堆排序 ...
老资源。...5.10 这有点奇怪。NULL 可以确保是0, 但空(null) 指针却不一定? . . 24 5.11 为什么有那么多关于空指针的疑惑?为什么这些问题如此经常地 出现? . . . . . . . . . . . . . . . . . . . ...
本章将涵盖常见的排序算法,如冒泡排序、选择排序、插入排序、归并排序、快速排序等,并分析各自的优缺点。 #### Chapter 8: The Disjoint Set ADT 不相交集合(Disjoint Sets)是一种抽象数据类型,用于表示一组...
Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
Levenshtein距离是一种衡量两个字符串之间差异的度量,通过计算最少的单字符编辑操作(插入、删除或替换)数量来将一个字符串转换为另一个字符串。 Levenshtein距离算法的核心思想是动态规划,它能够有效地找到两个...
4. "1029 魔咒词典.cpp" 可能是一个字符串处理或字典树的问题,可能需要实现查找或插入操作,或者寻找特定模式的字符串。 5. "1449 确定比赛名次.cpp" 可能涉及到排序算法,比如快速排序、归并排序等,用来确定比赛...
smaxer:为PGCPS老师的SchoolMAX...•“成绩报告卡格式” - 学生GPA将自动插入(修正3/24/11) •改善考勤中的“更改日期” •自动显示“所有”班级,而不是“今天的班级”(主页→学生→学生时间表) 支持语言:English
<<page 1>> page begin==================== 目 目目 目 录 录录 录 第一部分 C#语言概述.4 第一章 第一章第一章 第一章 .NET 编 编 ... 比尔....这一天 微软公司正式推出了其下一代...