排序算法

image.png

• 排序的稳定性

  
  image.png

影响排序算法的几个因素

• 时间性能
• 辅助空间
• 算法复杂性

冒泡排序

时间复杂度 O(n^2)
正宗的

image.png

选择排序

image.png

直接插入排序

将一个数字插入到已经排序好的数组。

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)

时间复杂度均为O(nLog(N))，

空间复杂度

归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)

桶排序（基数排序）

function bubbleSort(arr) {
  //从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
  //将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
  //直至构建出大顶堆（升序为大顶，降序为小顶）
  const length = arr.length;
  if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
    return arr;
  }
  const mid = Math.floor(length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid, length);

  return merge(bubbleSort(left), bubbleSort(right));
}

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

  //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
  while (il < left.length) {
    result.push(left[il]);
    il++;
  }
  
  while (ir < right.length) {
    result.push(right[ir]);
    ir++;
  }

  return result;
}

希尔排序

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

大顶堆 和 小顶堆

• 大顶堆：每个结点的值都大于或等于其左右孩子结点的值

• 小顶堆：每个结点的值都小于或等于其左右孩子结点的值

快速排序

在初始序列有序的情况下，快排的效率最差。O(n^2)

拓扑排序

拓扑排序是图中判断是否有环的算法，在图中查找一个无环的所有的节点，不是用来数据排序的

所有排序

image.png image.png image.png