常见的排序算法

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。详解

• 比较相邻的元素，如果第一个比第二个大，就交换他们两个；
• 对每一对相邻元素做同样的工作，从开始的第一对到最后的一对，这样最后的元素应该会是最大的数；
• 针对所有的元素重复上述的操作，除了最后一个元素。

function bubbleSort(array) {
    const length = array.length
    for (let i = 0; i < length; i++) {
      for (let j = 0; j < length - 1 - i; j++) {
        if (array[j] > array[j + 1]) {
          [array[j], array[j + 1]] = [array[j + 1], array[j]]
        }
      }
    }
    return array
  }
  console.log(bubbleSort([3, 4, 5, 1, 2]))

算法分析

• 最佳情况：T(n) = O(n)

当输入的数据已经是正序时

• 最差情况：T(n) = O(n2)

当输入的数据是反序时

• 平均情况：T(n) = O(n2)

选择排序

在未排序的序列中找到最小（大）的元素，存放在排序序列的起始位置；再从剩余的未排序的元素中寻找最小（大）的元素，存放到已经排好序列的末尾； n - 1 趟结束后，数组有序化了。详解

function selectSort(array) {
    for (let i = 0; i < array.length; i++) {
      for (let j = i + 1; j < array.length; j++) {
        if (array[i] > array[j]) {
          [array[i], array[j]] = [array[j], array[i]]
        }
      }
    }
    return array
  }

算法分析

• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

插入排序

假设第一项已经是排序的了，和第二项比较，确定第二项的位置，依次类推。详解

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置。

function insertSort(array) {
    for (let i = 0; i < array.length; i++) {
      let temp = array[i]
      for (let j = (i - 1); j >= 0 && temp < array[j]; j--) {
        array[j + 1] = array[j]
        array[j] = temp
      }
    }
    return array
  }

算法分析

• 最佳情况：输入数组按升序排列。T(n) = O(n)
• 最坏情况：输入数组按降序排列。T(n) = O(n2)
• 平均情况：T(n) = O(n2)

希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，算法便终止。详解

function shellSort(array) {
    let len = array.length;
    gap = Math.floor(len / 2);
    while (gap !== 0) {
      for (let i = gap; i < len; i++) {
        let temp = array[i];
        let j;
        for (j = i - gap; j >= 0 && temp < array[j]; j -= gap) {
          array[j + gap] = array[j];
        }
        array[j + gap] = temp;
      }
      gap = Math.floor(gap / 2);
    }
    return array;
  }

算法分析

• 最佳情况：T(n) = O(nlog2 n)
• 最坏情况：T(n) = O(nlog2 n)
• 平均情况：T(n) =O(nlog n)

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

• 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

function mergeSort(arr) {
    let len = arr.length
    if (len < 2) {
      return arr
    }
    let middle = Math.floor(len / 2),
      left = arr.slice(0, middle),
      right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right))
  }

  function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
      if (left[0] <= right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }

    while (left.length)
      result.push(left.shift())

    while (right.length)
      result.push(right.shift())
    return result
  }

算法分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)

快速排序

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 "基准"（pivot）；

• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

function quickSort(arr) {
    if (arr.length <= 1) {
      return arr
    }
    const pivotIndex = Math.floor(arr.length / 2)
    const 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))
  }

算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(nlogn)

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1] <=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

  /*
    方法说明：维护堆的性质
    @param  arr 数组
    @param  x   数组下标
    @param  len 堆大小
  */
  function heapify(arr, x, len) {
    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {
      let l = 2 * x + 1, r = 2 * x + 2, largest = x, temp
      if (l < len && arr[l] > arr[largest]) {
        largest = l
      }
      if (r < len && arr[r] > arr[largest]) {
        largest = r
      }
      if (largest !== x) {
        temp = arr[x]
        arr[x] = arr[largest]
        arr[largest] = temp
        heapify(arr, largest, len)
      }
    } else {
      return 'arr is not an Array or x is not a number!'
    }
  }
  function heapSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
      //建堆
      let heapSize = array.length, temp
      for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
        heapify(array, i, heapSize)
      }

      //堆排序
      for (let j = heapSize - 1; j >= 1; j--) {
        temp = array[0]
        array[0] = array[j]
        array[j] = temp
        heapify(array, 0, --heapSize)
      }
      return array
    } else {
      return 'array is not an Array!'
    }
  }

算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)

参考文章

十大经典排序算法总结（JavaScript描述）