算法札记

线性查找-时间复杂度O(n)–相当于算法界中的HelloWorld

function linearSearch(arr, x) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == x) {
      return i
    }
  }
  return -1
}

二分查找(又称折半查找) - 适用于已排好序的线性结构 - 时间复杂度O(logN)

//二分搜索
//A为已按"升序排列"的数组，x为要查询的元素
//返回目标元素的下标
function binarySearch(arr, x) {
  var leftIndex = 0,
      rightIndex = arr.length - 1
  while (leftIndex <= rightIndex) {
    var midIndex = Math.floor((leftIndex + rightIndex) / 2) //下取整
    var midVal = arr[midIndex]
    if (x == midVal) {
      return midIndex
    }
    if (x < midVal) {
      rightIndex = midIndex - 1
    }
    else {
      leftIndex = midIndex + 1
    }
  }
  return -1
}

冒泡排序 – 时间复杂度O(n^2)

//它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来
function bubbleSort(arr) {
  var temp
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}

选择排序 – 时间复杂度O(n^2)

//选择排序
//思路：找到最小值的下标记下来，再交换
function selectionSort(arr) {
  var min, temp
  for (var i = 0; i < arr.length; i++) {
    min = i
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j])
        min = j
    }
    if (min != i) {
      temp = arr[i]
      arr[i] = arr[min]
      arr[min] = temp
    }
  }
  return arr
}

插入排序 – 时间复杂度O(n^2)

//插入排序
//假定当前元素之前的元素已经排好序，先把自己的位置空出来，
//然后前面比自己大的元素依次向后移，直到空出一个"坑"，
//然后把目标元素插入"坑"中
function insertSort(arr) {
  var temp
  for (var i = 0; i < arr.length; i++) {
    var temp = arr[i]
    for (var j = i; j > 0 && temp < arr[j - 1]; j--) {
      arr[j] = arr[j - 1]
    }
    arr[j] = temp
  }
  return arr
}

快速排序 – 时间复杂度O(nlogn)

//（1）在数据集之中，选择一个元素作为"基准"（pivot）。
//（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
//（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var pivotIndex = Math.floor(arr.length / 2)
  var pivot = arr.splice(pivotIndex, 1)[0]
  var left = []
  var right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    }
    else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}

字符串反转 – 时间复杂度O(logN)

function inverse(s) {
  var arr = s.split('')
  var i = 0,
    j = arr.length - 1
  while (i < j) {
    var t = arr[i]
    arr[i] = arr[j]
    arr[j] = t
    i++
    j--
  }
  return arr.join('')
}

找出下面代码的规律并且编写一个函数，转换特定的整数到对应的字符串。

1 => A，2 => B，3 => C，…，26 => Z，27 => AA，28 => AB，29 => AC，…，52 => AZ，53 => BA，…

//10进制到26进制的转换
function convert(num) {
  var s = ''
  while (num > 0) {
    var m = num % 26
    if (m === 0) {
      m = 26
    }
    s = (m + 9).toString(36) + s
    num = (num - m) / 26
  }
  return s.toUpperCase()
}
console.log(convert(50))