感觉自己好磨蹭，1月3号建的文章题目，2个月之后还是没有深得精髓，对自己好失望！！

冒泡排序 bubbleSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
export const bubbleSort = (arr) => {
  const {length} = arr
  // let flag = false
  if (length < 2) {
    return arr
  }
  for(let i = 0; i < length; i ++) {
    // flag = false
    for(let j = 0; j < length - 1 - i; j ++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        // flag = true
      }
    }
    // if (!flag) break
  }
  return arr
}

选择排序 selectionSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 选择排序 找到数据结构中的最小的那个并将放到首位，接着找第二个放到第二位
export const selectionBubble = (arr) => {
  const {length} = arr
  let indexMin
  for(let i = 0; i < length - 1; i ++) {
    indexMin = i
    for (let j = i; j < length; j ++) {
      if (arr[indexMin] > arr[j]) {
        indexMin = j
      }
    }
    if( i !== indexMin) {
      swap(arr, i, indexMin)
    }
  }
  return arr
}

插入排序 insertionSort

复杂度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 插入排序
export const insertionSort = (arr) => {
  const len = arr.length
  let temp
  for (let i = 1; i < len; i ++) {
    console.log('i', i)
    let j = i
    temp = arr[i]
    while( j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1]
      j --
    }
    arr[j] = temp
  }
  return arr
}

归并排序 mergeSort

复杂度O(nlog(n))

分治法典型应用，分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。

处理过程是由下到上的，先处理子问题，然后再合并

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
// 归并排序
var mergeSort = (arr) => {
  var merge = (right, left) => {
    const res = []
    let i = 0, j = 0;
    while(
      i < left.length && 
      j < right.length
    ) {
      if (right[j] > left[i]) {
        res.push(left[i++])
      } else {
        res.push(right[j++])
      }
    }
    while(i < left.length) {
      res.push(left[i++])
    }
    while(j < right.length) {
      res.push(right[j++])
    }
    return res
  }
  const sort = (arr) => {
    if (arr.length === 1) {return arr}
    const middle = Math.floor(arr.length/2)
    const left = (arr.slice(0, middle))
    const right = (arr.slice(middle, length))
    return merge(mergeSort(left), mergeSort(right))
  }
  return sort(arr)
}
mergeSort([22,22,1,4,222,55,6,777,7,8])

快速排序 qucikSort

快速排序也是分治法的应用，处理过程是由上到下的，先分区，然后再处理子问题。

快速排序通过遍历数组，将待排序元素分隔成独立的两部分，一部分记录的元素均比另一部分的元素小，则可以分别对这两部分记录的元素继续进行排序，直到排序完成。

最开情况下: 时间复杂度O(nlog(n)) 最坏情况下O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function quickSort(arr) {
  if (arr.length < 2) {
      return arr;
  }
  var base = arr[0]
  var left = []
  var right = []
  // 基数从1 开始的！！！
  for (let i = 1; i < arr.length; i ++) {
      if(arr[i] > base) {
          right.push(arr[i])
      } else {
          left.push(arr[i])
      }
  }
  return [...quickSort(left), base, ...quickSort(right)]
}
quickSort([2,3,44,5,1,2])

计数排序 countingSort

第一个分布式排序，一个整数排序算法，事件复杂度O(n+k), K是临时计数数组的大小，需要更多的内存来存放临时数组

桶排序 bucketSort

箱排序，也是分布式排序算法

基数排序 radixSort

分布式排序算法，根据数字的有效位或基数将整数分不到桶中