选择排序

上一次我们了解了递归排序，详情可以点击链接进行观看。
https://www.yuque.com/u12173902/lyff6h/udswhi

通过递归我们发现，递归就是在不断调用自己，也就是说，它在不断的重复。那么说起重复你还会想到什么？没错，就是循环，并且，所有的递归都可以写成循环。

思路

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

重写递归

递归的算法中找最小值的下标的代码如下：

  1. let min = (numbers) => {
  2.     if (numbers.length > 2) {
  3.         return min(
  4.             [numbers[0], min(numbers.slice(1))]
  5.         )
  6.     } else {
  7.         return Math.min.apply(null, numbers)
  8.     }
  9. }
  10. let minIndex = (numbers) => numbers.indexOf(min(numbers))

我们直观的就可以感受到代码的繁琐，接下来我们就使用循环来重写它

  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.         }
  7.     }
  8.     return index
  9. }

这样代码就一目了然了，接下来我们把 sort 也用循环重写一下

递归写法：

  1. let sort = (numbers) => {
  2.     if (numbers.length > 2) {
  3.         let index = minIndex(numbers)
  4.         let min = numbers[index]
  5.         numbers.splice(index, 1)
  6.         return [min].concat(sort(numbers))
  7.     } else {
  8.         return numbers[0] < numbers[1] ? numbers : numbers.reverse()
  9.     }
  10. }

使用循环重写后：

  1. let sort = (numbers) => {
  2.     for (let i = 0; i < numbers.length; i++) {
  3.         let index = minIndex(numbers.slice(i)) + i
  4.         if (index !== i) { swap(numbers, index, i) }
  5.     }
  6.     return numbers
  7. }
  8. let swap = (array, i, j) => {
  9.     let temp = array[i]
  10.     array[i] = array[j]
  11.     array[j] = temp
  12. }

传参和传值的区别

在这里我们需要注意一个小细节，要明确 swap 的参数是什么

错误的实现 swap

  1. let swap = (a,b)=>{
  2.   let temp = a
  3.   a = b
  4.   b = temp
  5. }
  6. swap(numbers[1],numbers[2])

这样直接交换 numbers[1] 和 numbers[2] 是不行的。因为在正确的写法中，array[i] 是个对象，而对象存的是一个地址。当我们把 numbers 复制给 array 的时候，复制的是 numbers 的地址，变动的是同一个对象的内存，所以是可以操作成功的。如果 numbers 是一个非对象，是一个简单类型，你就会发现传参的时候只会复制 a,b 的值。我们要明确传值和传地址的区别。

时间复杂度

O(n^2)

优缺点

优点

可以知道循环的次数即（i-1）次

缺点

不稳定，比较的次数可能很少，也可能超级多

快速排序

思路都和递归是一样的

代码

  1. let sort = (numbers) => {
  2.     if (numbers.length <= 1) { return numbers }
  3.     let pivotIndex = Math.floor(numbers.length / 2)
  4.     let pivot = numbers.splice(pivotIndex, 1)[0];
  5.     let left = [];
  6.     let right = [];
  7.     for (let i = 0; i < numbers.length; i++) {
  8.         if (numbers[i] < pivot) {
  9.             left.push(numbers[i])
  10.         } else { right.push(numbers[i]) }
  11.     }
  12.     return sort(left).concat([pivot], sort(right))
  13. }

时间复杂度

O(nlogn)

优缺点

优点

快！

缺点

不稳定，可能会出现多次比较的情况