/**
 * 插入排序，时间复杂度最坏O(n^2)，最好（基本有序）O(n)；空间复杂度O(1)
 * @param {Array} arr 需要进行排序的数据源
 * @return {Array} arr 排序完成后的数组
 */
function insertSort(arr) {
  var len = arr.length;
  for(var i=1; i<len; i++) {
    var sortedIndex = i - 1;
    var unSortedData = arr[i];
    while(sortedIndex >= 0 && unSortedData < arr[sortedIndex]) {
      arr[sortedIndex + 1] = arr[sortedIndex];
      sortedIndex -= 1;
    }
    arr[sortedIndex + 1] = unSortedData;
  }
  return arr;
}