四种简单算法

发表于

1、选择排序

第一次从数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
选择排序
*/
function selectionSort(arr) {
  let len = arr.length;
  let minIndex, temp;
  for (let i = 0; i < len - 1; i++) {
      minIndex = i;
      for (let j = i + 1; j < len; j++) {
          if (arr[j] < arr[minIndex]) {     // 寻找最小的数
              minIndex = j;                 // 将最小数的索引保存
          }
      }
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
  }
  return arr;
}

2、快速排序

  • 在数据中找一项作为基准
  • 比基准数大的放右边，小的放左边 （基准的位置是正确的）
  • 把左右两边再分别这样划分排序，直到左右两边只有一项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
快速排序
*/
let quickSort = (array) => {
  if (array.length <= 1) {
    return array
  }
  let pivotIndex = Math.floor(array.length / 2)
  let pivot = array.splice(pivotIndex, 1)[0]
  let left = []
  let right = []
  for (let i = 0; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}

3、归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
归并排序
*/
let mergeSort = (array) => {
  if (array.length === 1) {
    return array
  }
  let left = array.slice(0, Math.floor(array.length / 2))
  let right = array.slice(Math.floor(array.length / 2))
  return merge(mergeSort(left), mergeSort(right))
}
let merge = (a, b) => {
  if (a.length === 0) {
    return b
  }
  if (b.length === 0) {
    return a
  }
  return a[0] > b[0]
    ? [b[0]].concat(merge(a, b.slice(1)))
    : [a[0]].concat(merge(a.slice(1), b))
}

4、计数排序

  • 使用哈希表将数据对应起来，重复次数作为哈希表对应 key 的 value
  • 遍历哈希表，对于哈希表的每个 key，遍历对应的 value 次
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
/*
计数排序
*/
let countSort = (array) => {
  let hashTable = {},
    max = 0,
    result = []
  for (let i = 0; i < array.length; i++) {
    if (!(array[i] in hashTable)) {
      hashTable[array[i]] = 1
    } else {
      hashTable[array[i]] += 1
    }
    if (array[i] > max) {
      max = array[i]
    }
  }
  for (let i = 0; i <= max; i++) {
    if (i in hashTable) {
      for (let j = 0; j < hashTable[i]; j++) {
        result.push(i)
      }
    }
  }
  return result
}