js之算法练习

发表于


二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function getNotIncluded(arr1, arr2) {
  var res = []
  for (var i = 0; i < arr2.length; i++) {
    var l = 0;
    var r = arr1.length - 1
    var has = false
    while (l <= r) {
      var mid = l + ((r - l) >> 1)
      if (arr1[mid] === arr2[i]) {
        has = true
        break
      }
      if (arr1[mid] > arr2[i])
        r = mid - 1
      if (arr1[mid] < arr2[i])
        l = mid + 1
    }
    if (!has)
      res.push(arr2[i])
  }
  return res
}


function swap(arr, n, m) {
  [arr[n], arr[m]] = [arr[m], arr[n]]
}
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
/*
 * 两两比较找到最大的
 * 从头向前把最大的放到最后面
 */
function bubbleSort(arr) {
  if (arr === null || arr.length < 2) return
  for (var e = arr.length - 1; e > 0; e--) {
    for (var i = 0; i < e; i++) {
      if (arr[i] > arr[i + 1]) swap(arr, i, i + 1)
    }
  }
}
插入排序
1
2
3
4
5
6
7
8
9
10
11
/*
 * [1，2，3] [x] 当前位置和前面的已排好的排
 */
function insertionSort(arr) {
  if (arr === null || arr.length < 2) return
  for (var i = 1; i < arr.length; i++) {
    for (var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
      swap(arr, j, j + 1)
    }
  }
}
选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * 找到最小的防盗最前面
 * 拟定最小序号，向前比较，把最小的放到最前面
 * 0 - n
 * 1 - n-1
 * 2 - n-2
 */
function selectionSort(arr) {
  if (arr === null || arr.length < 2) return
  for (var i = 0; i < arr.length - 1; i++) {
    var minIndex = i
    for (var j = i + 1; j < arr.length; j++) {
      minIndex = arr[j] < arr[minIndex] ? j : minIndex
    }
    swap(arr, i, minIndex)
  } 
}
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function quickSort(arr, l, r) {
  if (arr === null || arr.length < 2) return
  if (l < r) {
    swap(arr, l + Math.random() * (r - l + 1) | 0, r)
    var p = partition(arr, l, r)
    quickSort(arr, l, p[0] - 1)
    quickSort(arr, p[1] + 1, r)
  }
}

function partition(arr, l, r) {
  var less = l - 1
  var more = r
  while (l < more) {
    if (arr[l] < arr[r]) {
      swap(arr, ++less, l++)
    } else if (arr[l] > arr[r]) {
      swap(arr, l, --more)
    } else l++
    swap(arr, more, r)
    return [less + 1, more]
  }
}
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
 * 上来直接二分然后合并
 */
function mergeSort(arr, l, r) {
  if (arr === null || arr.length < 2) return
  if (l === r) return
  var mid = l + ((r - l) >> 1)
  mergeSort(arr, l, mid)
  mergeSort(arr, mid + 1, r)
  merge(arr, l, mid, r)
}

function merge(arr, l, m, r) {
//   var help = new Array(r - l + 1) // r - l 多少个数
  var help = []
  var i = 0
  var p1 = l // 第一部分 l - m
  var p2 = m + 1 // 第二部分 m + 1 - r
  while (p1 <= m && p2 <= r) {
    help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]
  }
  while (p1 <= m) {
    help[i++] = arr[p1++]
  }
  while (p2 <= r) {
    help[i++] = arr[p2++]
  }
  for (var j = 0; j < help.length; j++) {
    arr[l + j] = help[j]
  }
}
堆排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
 * 先建立大根堆 最大的头放最后一个改变size 然后比较头是否比左右子大需要下沉
 */
function heapSort(arr) {
  if (arr === null || arr.length < 2) return
  for (var i = 0; i < arr.length; i++) {
    heapInsert(arr, i)
  }
  var size = arr.length
  swap(arr, 0, --size) // 头尾相换，边界从最后-1
  while (size > 0) {
    heapify(arr, 0, size) // 从堆顶调整，成立新大根堆
    swap(arr, 0, --size)
  }
}

// size 边界
function heapify(arr, index, size) {
  var left = index * 2 + 1 // left node index
  while (left < size) { // left 不出界， right = left + 1 不出界
    var largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left
    larget = arr[largest] > arr[index] ? largest : index // node 最大与 parent 比
    if (largest === index) break // 没的比 parent 最大
    swap(arr, largest, index)
    index = largest
    left = index * 2 + 1
  }
}

function heapInsert(arr, index) {
  while(arr[index] > arr[(index - 1) / 2 | 0]) {
    swap(arr, index, (index - 1) / 2 | 0) 
    index = (index - 1) / 2 | 0
  }
}
桶排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bucketSort(arr) {
  if (arr === null || arr.length < 2) return
  
  var bucket = new Array(arr.length) // undefined[]
  for (var i = 0; i < arr.length; i++) {
    bucket[arr[i]] ? bucket[arr[i]]++ : bucket[arr[i]] = 1
  }
  
  var m = 0
  for (var n = 0; n < bucket.length; n++) {
    while (bucket[n]-- > 0) {
      arr[m++] = n
    }
  }
}

var arr = [-89, -80, -74, -64, -63, -61, -61, -56, -47, -44, -41, -40, -38, -36, -27, -26, -25, -24, -22, -17, -14, -13, -11, -6, -6, -5, -5, -2, 1, 3, 5, 8, 8, 9, 9, 11, 13, 15, 1616, 17, 18, 19, 21, 22, 23, 25, 26, 30, 30, 32, 35, 36, 36, 45, 59, 64, 73, 89]
quickSort(arr, 0, arr.length-1)
console.log(arr)