排序

• 合并两个有序数组

function merge(arr1, arr2) {
  var merge_arr = []
  var index_1 = 0
  var index_2 = 0

  while(index_1 < arr1.length && index_2 < arr2.length) {
    if(arr1[index_1] <= arr2[index_2]) {
      merge_arr.push(arr1[index_1])
      index_1++
    } else {
      merge_arr.push(arr2[index_2])
      index_2++
    }
  }

  // arr1 有剩余
  if(index_1 < arr1.length) {
    while(index_1 < arr1.length) {
      merge_arr.push(arr1[index_1])
      index_1++
    }
  }

  // arr2 有剩余
  if(index_2 < arr2.length) {
    while(index_2 < arr2.length) {
      merge_arr.push(arr2[index_2])
      index_2++
    }
  }

  return merge_arr
}

// console.log(merge([1,3,5],[2,4,6]))    [1,2,3,4,5,6]

• 归并算法
  • 分治法将一个大的问题, 转化分解成若干个子问题, 当每个子问题都解决之后, 大的问题也就随之解决。

function merge_sort_ex(arr, start, end) {
  if(start < end) {
    // 分
    var middle = Math.floor((start + end)/2)
    var arr1 = merge_sort_ex(arr, start, middle)
    var arr2 = merge_sort_ex(arr, middle+1, end)

    // 治
    return merge(arr1, arr2)
  }
  return [arr[end]]
}

function merge_sort(arr) {
  return merge_sort_ex(arr, 0, arr.length - 1)
}

// var arr = [3,5,1,2,8,0,6]
// console.log(merge_sort(arr))    [0,1,2,3,5,6,8]

• 快速排序
  • 取 arr[start]为基准值，将start到end这个区域进行分区

function partition(arr, start, end) {
  var pivotpos = start
  var pivot = arr[start]

  for(var i = start + 1; i <= end; i++) {
    if(arr[i] < pivot) {
      pivotpos++
      if(pivotpos != i) {
        // 将小于基准的值交换到左侧
        var temp = arr[pivotpos]
        arr[pivotpos] = arr[i]
        arr[i] = temp
      }
    }
  }

  arr[start] = arr[pivotpos]
  arr[pivotpos] = pivot

  return pivotpos
}

function quick_sort_ex(arr, start, end) {
  if(start < end) {
    var pivotpos = partition(arr, start, end)
    quick_sort_ex(arr, start, pivotpos-1)
    quick_sort_ex(arr, pivotpos+1, end)
  }
}
function quick_sort(arr) {
  quick_sort_ex(arr, 0, arr.length -1)
}
// var arr = [7,2,8,1,4,6,9,3]
// quick_sort(arr)
// console.log(arr)    [1,2,3,4,5,6,7,8,9]

• 直接插入排序
  • 当插入第(i>=1)个元素时，假设前面从arr[0]到arr[i-1]已经有序，那么只需要arr[i]和前面那些有序的数值进行比较,找到自己应该插入的位置即可，原来位置上的元素一次向后顺移

function insert_sort(arr, start, end) {
  for(var i = start +1; i <= end; i++) {
    if(arr[i] < arr[i-1]) {
      var tmp = arr[i]
      var j = i-1
      // 找到tmp 应该放的位置
      while(j>=start && tmp<arr[j]){
        arr[j+1] = arr[j]
        j--
      }
      arr[j+1] = tmp
    }
  }
}

// var arr = [7,2,8,1,4,6,9,3]
// insert_sort(arr, 0, arr.length-1)
// console.log(arr)   [1,2,3,4,5,6,7,8,9]

• 快速排序改进

function quick_sort_ex2(arr, start, end) {
  if(start < end) {
    if(end-start <= 25) {
      insert_sort(arr, start, end)
    } else {
      var pivotpos = partition(arr, start, end)
      quick_sort_ex2(arr, start, pivotpos - 1)
      quick_sort_ex2(arr, pivotpos + 1,end)
    }
  }
}
function quick_sort2(arr) {
  quick_sort_ex2(arr, 0, arr.length-1)
}
// var arr = [7,2,8,1,4,6,9,3]
// quick_sort(arr, 0, arr.length-1)
// console.log(arr)

• 二分查找

function binary_search(arr, target, start, end) {
  if(start > end) {
    return -1
  }
  var middle = Math.floor((start+end)/2)
  if(arr[middle] == target) {
    return middle
  } else if(middle > target) {
    // 去左侧查找
    binary_search(arr, target, start, middle-1)
  } else {
    // 去右侧查找
    return binary_search(arr, target, middle+1, end)
  }
}

• 利用二分查找找到第一个比 target 大的值的位置

function binary_search_bigger(arr, target, start, end) {
  if(arr[start] > target) {
    return start
  }
  if(start > end) {
    return -1
  }
  var middle = Math.floor((start+end)/2)
  if(arr[middle] <= target) {
    if(arr[middle+1] > target) {
      return middle + 1
    }
    return binary_search_bigger(arr, target, middle+1, end)
  }
  return binary_search_bigger(arr, target, start, middle+1)
}

var arr = [1,3,4,6,7,8,9,18,18,20]
console.log(binary_search_bigger(arr, 18, 0, arr.length-1))
console.log(binary_search_bigger(arr, 0, 0, arr.length-1))