奇怪的插入排序？

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

如果给你这样的题目要填空：

引用

// 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;
  }
}

这样？