JS排序算法（一）

1.冒泡排序

简介

冒泡排序（Bubble Sort）是最易懂的排序算法，但是效率较低，生产环境中很少使用。

它的基本思想是：

1. 依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍比较下来，能够保证最大（或最小）的数排在最后一位。

2. 再对最后一位以外的数组，重复前面的过程，直至全部排序完成。

由于每进行一次这个过程，在该次比较的最后一个位置上，正确的数会自己冒出来，就好像“冒泡”一样，这种算法因此得名。

算法实现

Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    //循环第一次之后数组最后一位就是最大的，下一次循环到最后一位的前i位就行，所有-i,这样每次冒泡排序的区间都会把已排序好的区间减掉
    for (let j = 0; j < this.length - 1 - i; j++) {
      //第一位和第二位比较，如果第一位比第二位大，则交换位置
      if (this[j] > this[j + 1]) {
        const temp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = temp;
      }
    }
  }
  return this;
};
const arr = [5, 4, 3, 2, 1];
console.log(arr.bubbleSort());


function bubbleSort(arr) {
  let length = arr.length;
  for (let i = 0; i < length - 1; i++) {
    //循环第一次之后数组最后一位就是最大的，下一次循环到最后一位的前i位就行，所有-i,这样每次冒泡排序的区间都会把已排序好的区间减掉
    for (let j = 0; j < length - 1 - i; j++) {
      //第一位和第二位比较，如果第一位比第二位大，则交换位置
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
const arr = [5, 5, 7, 2, 8, 1, 0, 4, 5, 1];
console.log(bubbleSort(arr));

时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：冒泡排序是稳定的排序算法，因为可以实现值相等的元素的相对位置不变

2.选择排序

简介

选择排序（Selection Sort）与冒泡排序类似，也是依次对相邻的数进行两两比较。不同之处在于，它不是每比较一次就调换位置，而是一轮比较完毕，找到最大值（或最小值）之后，将其放在正确的位置，其他数的位置不变。

算法实现

let sort = (numbers) => {
            for (let i = 0; i < numbers.length - 1; i++) {
                let index = minIndex(numbers.slice(i)) + i
                if (index !== i) {
                    swap(numbers, index, i)
                }
            }
            return numbers
        }

        let swap = (array, i, j) => {
            let temp = array[i]
            array[i] = array[j]
            array[j] = temp
        }
        let minIndex = (numbers) => {
                let index = 0
                for (let i = 1; i < numbers.length; i++) {
                    if (numbers[i] < numbers[index]) {
                        index = i
                    }
                }
                return index
            }
            //调用
        sort([12, 5, 8, 7, 9, 77, 6, 33])

时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：选择排序是不稳定的排序算法，因为无法保证值相等的元素的相对位置不变.

3.快速排序

简介

快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。

它的基本思想很简单：先确定一个“支点”（pivot），将所有小于“支点”的值都放在该点的左侧，大于“支点”的值都放在该点的右侧，然后对左右两侧不断重复这个过程，直到所有排序完成。

算法实现

let quickSort = arr => {
            if (arr.length <= 1) {
                return arr
            }
            let pivotIndex = Math.floor(arr.length / 2) //pivotIndex基准
            let pivot = arr.splice(pivotIndex, 1)[0]
            let left = []
            let 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))
        }

时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn) 空间复杂度:O(logn)（递归调用消耗） 稳定性：不稳定，无法保证相等的元素的相对位置不变

4.归并排序

简介

它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

算法实现

let mergeSort = arr => {
            let k = arr.length
            if (k === 1) {
                return arr
            }
            let left = arr.slice(0, Math.floor(k / 2))
            let right = arr.slice(Math.floor(k / 2))
            return merge(mergrSort(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))
        }

时间复杂度：O(nlogn)，递归劈成两半logn,循环n次，所以nlogn 空间复杂度:O(n) 稳定性：归并排序是稳定的排序算法

5.计数排序

简介

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法实现

let countSort = 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
            } //遍历哈希表，如果在就打出来

时间复杂度：n+max