文章序

排序算法作为算法的入门，也是在日常开发中十分常用的，故在此整理出十大排序算法，方便自己和需要的朋友查阅

先定义交换函数

  //不使用额外空间交换算法,不能自己跟自己换
  function swap(array, i, j) {
    if (i === j) {
      return array;
    }
    let arr = array;
    arr[i] = arr[i] + arr[j];
    arr[j] = arr[i] - arr[j];
    arr[i] = arr[i] - arr[j];
    return arr;
  }

  //使用额外空间交换算法,可以自己跟自己换
  function swap(array, i, j) {
    let arr = array;
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    return arr;
  }

1冒泡排序

原理：数组长度为 n，遍历 n - 1 趟，每趟从第 1 个元素向后两两比较，如果左边的元素大于右边的元素则将两个元素据交换，直到左边的元素为第 n - 1 个元素，交换完毕后，此时数组最右端的元素即为该数组中最大的元素。接着对该数组剩下的 n-1 个元素继续冒泡排序，直到整个数组有序排列
特性：时间复杂度：O(n^2)，空间复杂度：O(1) ，稳定排序 ，原地排序
方法：两层循环嵌套，外层共遍历 n - 1 趟，内层遍历从第 1 个元素到 n - 1 - i 个元素，进行两两比较交换

  function bubbleSort(arr) {
    let res = arr;
    let n = arr.length;
    for(let i = 0; i < n - 1; i++) {
      for(let j = 0; j < n - 1 - i; j++) {
        if(res[j] > res[j + 1]) {
          res = swap(res, j, j + 1);
        }
      }
    }
    return res;
  }

2选择排序

原理：遍历 n - 1 趟，每趟遍历找到剩余最小的元素放在前面，依次类推，直到数组有序排列
特性：时间复杂度：O(n^2) ，空间复杂度：O(1) ，非稳定排序，原地排序
方法：两层循环嵌套，外层共遍历 n - 1 趟，内层遍历从第 i 个元素开始，找到最小的元素和第 i 个元素交换

  function selectionSort(arr) {
    let res = arr;
    let n = arr.length;
    let minIndex = 0;
    for(let i = 0; i < n - 1; i++) {
      minIndex = i;
      for(let j = i + 1; j < n; j++) {
        if(res[j] < res[minIndex]) {
          minIndex = j;
        }
      }
      if(minIndex !== i) {
        res = swap(res, i, minIndex);
      }
    }
    return res;
  }

3插入排序

原理：从第 1 个元素开始，将后面的元素与该元素比较，大则放在右边，小则放在左边，此时该两元素构成数组有序，剩余元素构成的数组无序，依次将剩余的元素向前面已有序数组中插入，直到整个数组有序
特性：时间复杂度：O(n^2)，空间复杂度：O(1) ，稳定排序 ，原地排序
方法：两层循环嵌套，外层共遍历 n - 1 趟代表插入 n - 1 个元素，内层遍历前面已有序数组直到找到合适的插入的元素的位置

  function insertSort(arr) {
    let res = arr;
    let n = arr.length;
    for (let i = 1; i < n; i++) {
      for (let j = i - 1; j >= 0; j--) {
        if (res[j] < res[j + 1]) {
          break;
        }
        swap(res, j, j + 1);
      }
    }
    return res;
  }

4希尔排序

原理：定义增量(gap) h，将待排数组分割成为 h 个子数组分别进行插入排序，操作之后减小 h 的值，再次分别进行插入排序，直到 h = 1，则再进行最后一次插入排序，完成后整个数组排序完成
特性：时间复杂度：O(nlogn) ，空间复杂度：O(1) ，非稳定排序，原地排序
方法：三层遍历，最外层每次减少增量h的值，内两层做插入排序，注意间隔不再是 1 而是增量 h

  function shellSort(arr) {
    let res = arr;
    let n = arr.length;
    let h = parseInt(n / 2);
    while (h >= 1) {
      //进行插入排序
      let i = 0;
      let temp = 0;
      while(temp < h) {
        for (let j = i - h; j >= 0; j = j - h) {
          if (res[j] < res[j + h]) {
            break;
          }
          swap(res, j, j + h);
        }
        i = i + h;
        if(i >= n) {
          temp++;
          i = temp;
        }
      }
      h = parseInt(h / 2);
    }
    return res;
  }

5快速排序

原理：选择一个元素，将比他大的都放到右侧，比它小的都放在左侧，此时数组分成两个数组，再次对两个数组进行快排，这样递归下去直到整个数组有序
特性：时间复杂度：O(nlogn)，空间复杂度：O(nlogn) ，非稳定排序，原地排序
方法：设指针 cur 指向第 1 个元素开始，指针 i 从 cur 指向元素向右走，指针 j 从最后一个元素向前走，j 先走，当 j 找到比 cur 小的元素停止，当 i 找到比 cur 大的元素停止，交换 i j指向的元素，直到i j相遇，交换此时cur 和 i 指向元素的位置，对此时指针左右两侧数组递归进行快排

  function quickSort(arr) {
    let n = arr.length;
    handleSort(arr, 0, n - 1);
    return arr;
  }
  const handleSort = (arr, start, end) => {
    if (start >= end) {
      return;
    }
    let cur = start,
      i = start + 1,
      j = end;
    let mid = start;
    while (true) {
      while (j >= start && j > i) {
        if (arr[j] < arr[cur]) {
          break;
        }
        j--;
      }
      while (i <= end && i < j) {
        if (arr[i] > arr[cur]) {
          break;
        }
        i++;
      }
      if (i === j) {
        if (arr[i] < arr[cur]) {
          swap(arr, cur, i);
          mid = i;
        }
        break;
      }
      swap(arr, i, j);
    }
    handleSort(arr, start, mid - 1);
    handleSort(arr, mid + 1, end);
  };

6归并排序

原理：将数组除2拆分，直到拆分到仅有一个元素的数组，此时该数组有序，将该数组与上一次拆分的另一个数组合并，此时本次拆分的数组有序，继续向上和上一次拆分的另一个数组合并，直到整个数组合并完毕，整个数组有序
特性：时间复杂度：O(nlogn)，空间复杂度：O(n)，稳定排序，非原地排序
方法：递归操作，先定义拆分函数mergeSort，再定义合并函数merge，拆分函数负责将入参数组除2拆分，并对拆分过的数组继续调用拆分函数，当两次拆分函数都调用完毕返回结果则调用合并函数

  function mergeSort(arr) {
    let n = arr.length;
    if (n < 2) {
      return arr;
    }
    let mid = parseInt(n / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid, n);
    let sortedLeft = mergeSort(left);
    let sortedRight = mergeSort(right);
    return merge(sortedLeft, sortedRight);
  }
  const merge = (left, right) => {
    let res = [];

    while (left.length > 0 && right.length > 0) {
      if (left[0] < right[0]) {
        res.push(left.shift());
      } else {
        res.push(right.shift());
      }
    }
    if (left.length > 0) {
      res = res.concat(left);
    }
    if (right.length > 0) {
      res = res.concat(right);
    }
    return res;
  };

7堆排序

原理：大顶堆为二叉树数结构，任意节点的值均大于左右子节点，数组可以构建一颗二叉树结构，将此数组调整为二叉树符合大顶堆的顺序，再依次交换第 0 个元素和第 n 个元素，并重新调整堆使之符合大顶堆定义，n依次递减直到n = 1，此时排序完成
特性：时间复杂度：O(nlogn)，空间复杂度：O(1)，非稳定排序，原地排序
方法：parseInt(n / 2)该元素为最后一个非叶子节点的数据，从这里开始遍历，构建大顶堆。大顶堆构建完成后将第 0 个元素和最后一个元素交换，此时剩下的堆不符合大顶堆定义，调整堆使符合大顶堆定义，再次交换第 0 个元素和此时最后一个元素，循环 n - 1 次结束获得有序数组

  function heapSort(arr) {
    let n = arr.length;

    //从最后一个非叶子节点开始遍历，构建大顶堆
    for (let i = parseInt(n / 2); i >= 0; i--) {
      heapify(arr, i, n);
    }
    //大顶堆构建完毕，开始从最后一个元素开始交换
    for (let j = arr.length - 1; j > 0; j--) {
      n--;
      swap(arr, 0, j);
      heapify(arr, 0, n);
    }
    return arr;
  }
  function heapify(arr, i, n) {
    //调整堆
    let leftChild = 2 * i + 1;
    let rightChild = 2 * i + 2;
    let largest = i;

    if (leftChild < n && arr[leftChild] > arr[largest]) {
      largest = leftChild;
    }
    if (rightChild < n && arr[rightChild] > arr[largest]) {
      largest = rightChild;
    }

    if (largest !== i) {
      swap(arr, i, largest);
      heapify(arr, largest, n);
    }
  }

8计数排序

原理：开辟新的数组 newArray，长度为 k，将待排数组内的元素值作为 newArray 的下标，将数组 newArray 从头遍历依次输出赋值给原数组即完成排序
特性：时间复杂度：O(n + m)，空间复杂度：O(n + m)，稳定排序，非原地排序
方法：

  function countingSort(arr) {
    let newArray = [];
    let k = 0;
    for (let i = 0; i < arr.length; i++) {
      newArray[arr[i]] = arr[i];
    }
    for (let j = 0; j < newArray.length; j++) {
      if (newArray[j]) {
        arr[k] = newArray[j];
        k++;
      }
    }
    return arr;
  }

9桶排序

原理：创建多个桶空间用来存放一定范围内的数据，每个桶内再排序，将数据按顺序从非空桶中取出，排序完成
特性：时间复杂度：O(n + m)，空间复杂度：O(n + m)，稳定排序，非原地排序
方法：创建一个数组，该数组内元素为数组表示不同的桶

  function bucketSort(arr) {
    let n = arr.length;
    let max = arr[0];
    let min = arr[0];
    //找到最大最小值
    arr.forEach(item => {
      if (max < item) {
        max = item;
      } else if (min > item) {
        min = item;
      }
    });
    //设数组长度为桶长度，获取桶数量
    let bucketCount = parseInt((max - min) / n);
    let bucketList = new Array(bucketCount + 1);
    for (let i = 0; i < bucketList.length; i++) {
      bucketList[i] = [];
    }
    //将每一个数据放入到合适的桶
    for (let j = 0; j < n; j++) {
      let index = parseInt((arr[j] - min) / n);
      bucketList[index].push(arr[j]);
    }
    //对每一个桶进行排序，这里选择计数排序
    bucketList.forEach(bucket => {
      countingSort(bucket);
    });
    for (let k = 0; k < bucketList.length; k++) {
      if (k === 0) {
        arr = [];
      }
      arr = arr.concat(bucketList[k]);
    }
    return arr;
  }

10基数排序

原理：将数组按照从低位到高位的顺序排序，当每一趟都排序完成之后整个数组有序
特性：时间复杂度：O(nm)，空间复杂度：O(n + m)，稳定排序，非原地排序
方法：先找到最大的数并获取其位数 n，然后从个位开始向上遍历，共 n 次，每次遍历获取该数当前位的数并和桶里的数的当前位的数比较，没有当前位则补 0

  function radixSort(arr) {
    let max = arr[0];
    //找到最大的数并获取其位数
    arr.forEach(number => {
      if (number > max) {
        max = number;
      }
    });
    const n = max.toString().length;
    // let divide = Math.pow(10, n);
    let divide = 1;

    for (let i = 0; i < n; i++) {
      let bucket = new Array(arr.length);
      for (let j = 0; j < arr.length; j++) {
        let tempNum = parseInt(arr[j] / divide);
        while (tempNum >= 10) {
          tempNum %= 10;
        }
        for (let k = 0; k < bucket.length; k++) {
          if (bucket[k]) {
            let tempBucketNum = parseInt(bucket[k] / divide);
            while (tempBucketNum >= 10) {
              tempBucketNum %= 10;
            }
            if (tempNum < tempBucketNum) {
              bucket.splice(k, 0, arr[j]);
              bucket.pop();
              break;
            }
          } else {
            bucket[k] = arr[j];
            break;
          }
        }
      }
      divide *= 10;
      arr = bucket;
    }
    return arr;
  }