minIndex

  1. let minIndex = numbers => {
  2.   let index = 0
  3.   for (let i = 1; i < numbers.length; i++) {
  4.     if (numbers[i] < numbers[index])
  5.       index = i
  6.     }
  8.   return index
  9. }

任何递归都可以改写成for循环

swap

  1. let swap = (array,i,j) => {
  2.   let temp = array[i]
  3.   array[i] = array[j]
  4.   array[j] = temp
  5. }

sort选择排序

  1. let sort = numbers => {
  2.   for (let i = 0; i < numbers.length - 1; i++) {
  3.     console.log('----')
  4.     console.log(`i:${i}`)
  5.     let index = minIndex(numbers.slice(i)) + i
  6.     console.log(`index:${index}`)
  7.     if (numbers[index] < numbers[i])
  8.       swap(numbers, index, i)
  9.     console.log(numbers)
  10.   }
  12.   return numbers
  13. }

quickSort快速排序

  1. // 以一个数为基准，小的往前，大的往后
  3. let quickSort = numbers => {
  4.   if (numbers.length <= 1) return numbers
  5.   console.log('-----')
  6.   let pivotIndex = Math.floor(numbers.length / 2)
  7.   console.log(`baseIndex:${pivotIndex}`)
  8.   let pivot = numbers.splice(pivotIndex,1)[0]    // splice返回的是数组
  9.   console.log(`base:${pivot}`)
  10.   let left = []
  11.   let right = []
  12.   for (let i = 0; i < numbers.length; i++) {
  13.     if (numbers[i] < pivot) left.push(numbers[i])
  14.     else right.push(numbers[i])
  15.   }
  16.   console.log(`left:${left}`)
  17.   console.log(`right:${right}`)
  18.   return quickSort(left).concat([pivot], quickSort(right))
  19. }

merge归并排序

  1. /*
  2. 1. 左右分别排好序
  3. 2. 合并
  4. */
  6. let mergeSort = (numbers) => {
  7.   let k = numbers.length
  8.   if (k === 1) return numbers
  9.   let left = numbers.slice(0, Math.floor(k/2))   // slice(0, length)
  10.   let right = numbers.slice(Math.floor(k/2))
  11.   return merge(mergeSort(left), mergeSort(right))
  12. }
  14. let merge = (a, b) => {
  15.   if (a.length === 0) return b
  16.   if (b.length === 0) return a
  18.   return a[0] < b[0] ?
  19.     [a[0]].concat(merge(a.slice(1), b)) :
  20.     [b[0]].concat(merge(a, b.slice(1)))
  21. }

count计数排序(最快)

  1. /*
  2. 遍历数组
  3. 把计数存入哈希表，记录max值
  4. 用for循环打印出哈希表里的key
  5. */
  6. let countSort = numbers => {
  7.   let hashTable = {}, result = [], max = 0
  8.   for (let i = 0; i < numbers.length; i++) {
  9.     if (!(numbers[i] in hashTable)) {
  10.       hashTable[numbers[i]] = 1
  11.     }else {
  12.       hashTable[numbers[i]] += 1
  13.     }
  15.     if (numbers[i] > max) 
  16.       max = numbers[i]
  17.   }
  19.   for (let i = 0; i <= max; i++){
  20.     if (i in hashTable) 
  21.       for (let j = 0; j < hashTable[i]; j++)
  22.         result.push(i)
  23.   }
  25.   return result
  26. }

时间复杂度

选择排序 O(n)

  1. 第一次对比 n 次，找出最小值
  2. 第二次对比 n-1次
  3. ….
  4. 最后 1 次

总共比较了 1 + 2 + … + n = n(n + 1) / 2次，复杂度为 O(n)

快速排序 O(n*logn)

  1. 从中间分，小的往左，大的往右，对比了 n/2 * 2次
  2. 每一半重复1操作， 对比了 n / 4 * 4
  3. 每一部分重复1操作， 对比了 n / 8 * 8
  4. 最后一共对比了（n / logn logn） logn = n logn

    归并排序 O(n*logn)

  • 第一次merge 对比了 n/2 * 2
  • 每一半重复1操作， 对比了 n / 4 * 4
  • 每一部分重复1操作， 对比了 n / 8 * 8
  • 最后一共对比了（n / logn logn） logn = n logn

    计数排序 O(n + max)

    其他排序

    https://visualgo.net/en/sorting