排序算法

1.什么是排序

一般情况下最坏，最好时间复杂度，空间复杂度理解记忆

重要：插入，堆，归并，快速

宋词记忆法

选泡插，（选择，冒泡，插入） 快归堆希统计基，（快速，归并，堆，希尔，桶，计数，基数） N方N老N一三，（选泡插时间复杂度为N2，快归堆时间复杂度为NlogN，希尔排序时间复杂度为N1.3） 对N加KN乘K，（桶排序，计数排序时间复杂度为N+K，基数排序时间复杂度为N*K） 不稳稳稳不稳稳，（依次的稳定性） 不稳不稳稳稳稳！

2.选择排序

• 最简单，但是最没用（时间复杂度高，不稳定）
• 算法思想：多次遍历数组，每次都找到最小的数放到最前面。

function selectionSort(arr) {
  let len = arr.length;
  let minIndex, temp;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i; //假设第一个元素是最小的
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { //找到最小的值
        minIndex = j; //将最小的值的索引保存
      }
    }
    temp = arr[i]; //将最小的值与第一个元素交换
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

3.冒泡排序

• 简单，但是慢（时间复杂度高，稳定）
• 思路：每次遍历将最大的数移到末尾
• 复杂度分析：第一次迭代需要比较的次数为N次，第二次迭代为N-1次，依次类推，复杂度为N+（N-1）+（N-2）+……+1=N（N-1）/2=O（N^2）

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

4.插入排序

• 简单，但是慢（时间复杂度高，稳定）
• 思路：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

function insertionSort(arr) {
  let len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1; //前一个元素的索引
    current = arr[i]; //当前元素
    while (preIndex >= 0 && arr[preIndex] > current) { //前一个元素大于当前元素
      arr[preIndex + 1] = arr[preIndex]; //将前一个元素后移
      preIndex--; //索引前移
    }
    arr[preIndex + 1] = current; //将当前元素插入到合适的位置
  }
  return arr;
}
let arr = [1, 99, 3, 63, 5];
console.log(insertionSort(arr));

5.简单排序算法总结

• 冒泡排序：基本不用，太慢
• 选择排序：基本不用，不稳定
• 插入排序：样本小，基本有序的时候效率比较高，三种排序中最快的，常用。

6.快速排序

• 常用（时间复杂度低，不稳定）

• 思想：

  1.先从数列中取出一个数作为基准

  2.分区，该数左边的都比该数小，右边的都比该数大

  3.再对左右区间递归第二步

function quickSort(arr) {
  if (arr.length <= 1) { //如果数组长度小于等于1，直接返回
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2); //取中间的值作为基准
  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)); //递归调用
}

7.归并排序

• 常用（时间复杂度低，稳定）

• 思想：分治，将数据化成logN层级，每一层用O（N）的复杂度去解决

  第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

  第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

  第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

  重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾

function mergeSort(arr) {
  let len = arr.length;
  if (len < 2) { //如果数组长度小于2，直接返回
    return arr;
  }
  let middle = Math.floor(len / 2); //取中间的值
  let left = arr.slice(0, middle); //取左边的值
  let 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;
}

8.堆排序

• 常用（时间复杂度低，稳定）

• 思想：首先建立一个堆，然后不断地比较非叶子节点和堆顶元素的大小，同时调整堆，完成对元素的排序。

  堆排序主要用于动态数据的维护，如在1000000个元素中选出前100名这种N个元素中选出前M个元素的问题，用堆排序最好解决，其复杂度为NlogM

function heapSort(arr) {
  let len = arr.length;
  let i = Math.floor(len / 2 - 1); //取中间的值
  let k = len - 1;
  while (i >= 0) { //从中间开始调整
    heapify(arr, i, len);
    i--;
  }
  while (k >= 0) { //将堆顶元素与最后一个元素交换
    swap(arr, 0, k);
    heapify(arr, 0, k);
    k--;
  }
  return arr;
}
function heapify(arr, i, len) {
  let left = 2 * i + 1; //左子节点
  let right = 2 * i + 2; //右子节点
  let largest = i; //最大值
  if (left < len && arr[left] > arr[largest]) { //左子节点大于最大值
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) { //右子节点大于最大值
    largest = right;
  }
  if (largest != i) { //最大值不等于i
    swap(arr, i, largest); //交换
    heapify(arr, largest, len); //递归调用
  }
}
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

9.计数排序算法

• 常用（时间复杂度低，稳定）

function countingSort(arr) {
  let len = arr.length;
  let B = [];
  let C = [];
  let min = max = arr[0];
  for (let i = 0; i < len; i++) {
    min = min <= arr[i] ? min : arr[i]; //取最小值
    max = max >= arr[i] ? max : arr[i]; //取最大值
    C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1; //计数
  }
  for (let j = min; j < max; j++) {
    C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); //计数
  }
  for (let k = len - 1; k >= 0; k--) {
    B[C[arr[k]] - 1] = arr[k]; //排序
    C[arr[k]]--; //计数
  }
  return B;
}

10.桶排序算法

• 常用（时间复杂度低，稳定）

function bucketSort(arr, bucketSize) {
  let len = arr.length;
  if (len === 0) { //如果数组长度为0，直接返回
    return arr;
  }
  let i;
  let minValue = maxValue = arr[0];
  for (i = 1; i < len; i++) { //取最小值和最大值
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }
  let DEFAULT_BUCKET_SIZE = 5; //默认桶的大小
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; //桶的数量
  let buckets = new Array(bucketCount); //创建桶
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  for (i = 0; i < len; i++) { //将元素放入桶中
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }
  arr.length = 0;
  for (i = 0; i < buckets.length; i++) { //对每个桶进行排序
    insertionSort(buckets[i]);
    for (let j = 0; j < buckets[i].length; j++) { //将排序后的元素放入数组中
      arr.push(buckets[i][j]);
    }
  }
  return arr;
}
function insertionSort(arr) { //插入排序
  let len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}

11.希尔排序

• 常用（时间复杂度低，不稳定）

function shellSort(arr) {
  let len = arr.length;
  let temp;
  let gap = 1;
  while (gap < len / 3) { //动态定义间隔序列
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

12.基数排序

• 常用（时间复杂度低，稳定）

function radixSort(arr, maxDigit) {
  let mod = 10;
  let dev = 1;
  let counter = [];
  for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for (let j = 0; j < arr.length; j++) {
      let bucket = parseInt((arr[j] % mod) / dev);
      if (counter[bucket] == null) {
        counter[bucket] = [];
      }
      counter[bucket].push(arr[j]);
    }
    let pos = 0;
    for (let j = 0; j < counter.length; j++) {
      let value = null;
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value;
        }
      }
    }
  }
  return arr;
}

13.总结

1.排序算法的稳定性：如果a原本在b前面，而a=b，排序之后a仍然在b的前面，则为稳定的排序算法；否则为不稳定的排序算法。 2.排序算法的执行效率：排序算法的执行效率可从以下几个方面衡量：最好情况、最坏情况、平均情况时间复杂度、内存消耗、是否为原地排序算法、是否为稳定的排序算法。 3.排序算法的应用场景：不同的排序算法适用于不同的应用场景。如：冒泡排序适用于数据量小的排序场景，时间复杂度为O(n^2)；快速排序适用于数据量大的排序场景，时间复杂度为O(nlogn)。

1.冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定排序算法，原地排序算法，适用于数据量小的排序场景。 2.插入排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定排序算法，原地排序算法，适用于数据量小的排序场景。 3.选择排序：时间复杂度O(n^2)，空间复杂度O(1)，不稳定排序算法，原地排序算法，适用于数据量小的排序场景。 4.归并排序：时间复杂度O(nlogn)，空间复杂度O(n)，稳定排序算法，非原地排序算法，适用于数据量大的排序场景。 5.快速排序：时间复杂度O(nlogn)，空间复杂度O(1)，不稳定排序算法，原地排序算法，适用于数据量大的排序场景。 6.计数排序：时间复杂度O(n+k)，空间复杂度O(n+k)，稳定排序算法，非原地排序算法，适用于数据量大，且数据范围不大的排序场景。 7.桶排序：时间复杂度O(n+k)，空间复杂度O(n+k)，稳定排序算法，非原地排序算法，适用于数据量大，且数据范围不大的排序场景。 8.基数排序：时间复杂度O(n*k)，空间复杂度O(n+k)，稳定排序算法，非原地排序算法，适用于数据量大，且数据范围不大的排序场景。 9.希尔排序：时间复杂度O(nlogn)，空间复杂度O(1)，不稳定排序算法，原地排序算法，适用于数据量大的排序场景。 10.堆排序：时间复杂度O(nlogn)，空间复杂度O(1)，不稳定排序算法，原地排序算法，适用于数据量大的排序场景。

使用频率： 1.冒泡排序、插入排序、选择排序：适用于数据量小的排序场景。 2.归并排序、快速排序、堆排序：适用于数据量大的排序场景。 3.计数排序、桶排序、基数排序：适用于数据量大，且数据范围不大的排序场景。 4.希尔排序：适用于数据量大的排序场景。

使用最多的排序算法：快速排序、归并排序、计数排序、桶排序、基数排序。

在数据处理中，快速排序、归并排序、堆排序和计数排序等算法使用较多。在实际应用中，快速排序是最常用的排序算法之一，因为它的时间复杂度为O(nlogn)，在大多数情况下都是最快的。而归并排序和堆排序也是常用的排序算法之一，它们的时间和空间复杂度都是O(nlogn)，但在某些情况下比快速排序更高效。计数排序则适用于数据量较小的情况，它的时间复杂度为O(n+k)，其中k为整数位数。