js排序

Posted on

选择排序

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

const minIndex = (numbers) => {
  var index = 0
  for (let i = 1; i < numbers.length; i++) {
    if (numbers[i] < numbers[index]) {
      index = i
    }
  }
  return index
}

const swap = (array, i, j) => {
  let temp = array[i]
  array[i] = array[j]
  array[j] = temp
}

const sort = (numbers) => {
  for (let i = 0; i < numbers.length - 1; i++) {
    console.log(`----`)
    console.log(`i: ${i}`)
    let index = minIndex(numbers.slice(i)) + i
    console.log(`index: ${index}`)
    console.log(`min: ${numbers[index]}`)
    if (index !== i) {
      swap(numbers, index, i)
      console.log(`swap ${index}: ${i}`)
      console.log(numbers)
    }
  }
  return numbers
}

sort([2, 55, 78, 99, 88, 654])

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const quickSort = arr => {
  if (arr.length <= 1) {
    return arr
  }
  let pivotIndex = Math.floor(arr.length / 2)
  let pivot = arr.splice(pivotIndex, 1)[0]
  let left = [],
    right = []
  for (let 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))
}

quickSort([24, 946, 9, 45, 6])

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const mergeSort = arr => {
  if (arr.length === 1) {
    return arr
  }
  let left = arr.slice(0, Math.floor(arr.length / 2))
  let right = arr.slice(Math.floor(arr.length / 2))
  return merge(mergeSort(left), mergeSort(right))
}

const 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))
}

mergeSort([23, 8, 4, 99, 12])


计数排序

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
const countingSort = arr => {
  let hashTable = {},
    max = 0,
    result = []
  for (let i = 0; i < arr.length; i++) {
    if (!(arr[i] in hashTable)) {
      hashTable[arr[i]] = 1
    } else {
      hashTable[arr[i]] += 1
    }
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  for (let j = 0; j <= max; j++) {
    if (j in hashTable) {
      for (let i = 0; i < hashTable[j]; i++) {
        result.push(j)

      }
    }
  }
  return result
}
countingSort([2, 9, 5, 7])

时间复杂度对比

选择排序 O(n^2)

快速排序 O(n * log2 n)

归并排序 O(n * log2 n)

计数排序 O(n + max)