7种排序算法

悠悠 2022-01-18 22:27 165阅读 0赞

### 冒泡排序 ###

自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

### 选择排序 ###

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

### 插入排序 ###

在要排序的一组数中，假设前面(n-1) \[n>=2\] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

### 堆排序 ###

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

**小顶堆 与 大顶堆**

对应的数组为：\[100, 19, 26, 17, 3, 25, 1, 2, 7\] 该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是： \_\_大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]  \_\_ \_\_小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]  \_\_

堆排序原理的动画：

// 重新调整为大顶堆
    function heapify(arr, size, index) {
      let largest = index; // 父级节点
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      if (left < size && arr[left] > arr[largest]) {
          largest = left;
      }
      if (right < size && arr[right] > arr[largest]) {
          largest = right;
      }
      if (largest !== index) {
        swap(arr, index, largest);
        heapify(arr, size, largest);
      }
    }
    function swap(a, i, j) {
      let tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }
    //这里的堆排序用的是最大堆
    function heapSort(originalArray) {
      const arr = [...originalArray];
      const size = arr.length;
      // 建立大顶堆
      // Math.floor(size / 2 - 1) 为父级节点index
      for (let i = Math.floor(size / 2 - 1); i >= 0; i--) {
        heapify(arr, size, i);
      }
      for (let i = size - 1; i >= 0; i--) {
        // 将堆顶元素与末尾元素进行交换，使末尾元素最大
        swap(arr, 0, i);
        // 重新调整为大顶堆,直到整个堆序列有序。
        heapify(arr, i, 0);
      }
      return arr;
    }
    复制代码

### 归并排序 ###

归并排序应用递归来把数组分解成左右两半的一个小数组，直到这个小数组被拆分成的元素个数<=1;然后再将小数组两两合并而成有序的大数组。这里面就是应用到分治策略。

### 快速排序 ###

*  **在数组中找到一个基准数（pivot）**
 *  **分区，将数组中比基准数大的放到它的右边，比基准数小的放到它的左边**
 *  **继续对左右区间重复第二步，直到各个区间只有一个数，这时候，数组也就有序了。**

### 希尔排序 ###

首先取 gap = Math.floor(arr.length / 2), 将数组分为 4 组，如下图中相同颜色代表一组：

然后分别对 4 个小组进行插入排序，排序后的结果为：

然后，取gap = Math.floor(gap / 2)，将原数组分为 2 小组，如下图：

然后分别对 2 个小组进行插入排序，排序后的结果为：

最后，取 d~3~ = 1，进行插入排序后得到最终结果：

**附：7种数组排序算法的复杂度：**

转载于:https://juejin.im/post/5c9ae7a3e51d452fbb6f82de