奇怪的插入排序
奇怪的插入排序?
忍不住想发牢骚。不是我自己遇到的啥面试笔试题啦。
如果给你这样的题目要填空:
你会怎么做?
既然是插入排序,外层循环这里是从前向后排序,应该保证每轮循环进入时a.slice(0, i)都已经排好序,然后为下标为i的元素在前面找到合适的插入位置插进去。
按这填空题的写法,内层循环的变量j是控制遍历和插入的,初始值为0也就是从前向后遍历找插入位置,最终把原本下标为i的元素插入到下标为j+1的地方。
这⋯⋯从前向后遍历要怎么把插入位置之后的元素向后挪,这是不让用Array内建方法的数组啊orz
==============================================
这题咋出得那么诡异⋯正常的插入排序(升序)的话得是这样吧:
也就是内层循环应该从下标i开始从后向前遍历找插入位置,直观。
或者如果用wiki给的算法的变量名的话:
当然我们可以把这种写法填到原本题目的空里,把原来的j = 0架空就好了:
或
但出题的人多半不是这样想的⋯吧?不然给j赋值为0干嘛,忽悠学生?
这样?
这样?
哈哈哈这也是一种架空j的方式,让它在循环中跟离开循环时意义发生变化。如果标准答案是这样的话我仍然觉得这是坑学生。
忍不住想发牢骚。不是我自己遇到的啥面试笔试题啦。
如果给你这样的题目要填空:
引用
// 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 楼
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; } }
这样?
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的方式,让它在循环中跟离开循环时意义发生变化。如果标准答案是这样的话我仍然觉得这是坑学生。