[数据结构与算法]几种经典的排序算法

排序算法

排序算法包含内部排序和外部排序

• 内部排序一般在内存中实现
• 外部排序在数据量很大且内存有限时使用

冒泡排序（Bubble Sort）

冒泡，像水中的气泡一样，从下往上会越来越大。
算法：

• 遍历所有数据，每一次都对相邻的两个元素进行比较，判断是否按照规定的顺序（升序|降序）排列，如果不是则进行交换位置，否则继续下一个元素。
• 遍历一次之后，最大值或最小值来到顶端，重复操作，直至全部有序。

平均时间复杂度：O(n^2)
空间复杂度：O(1)

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

选择排序（Select Sort）

算法：选择数据中最大或最小的元素，需要排序数列中的起始位置；然后在剩余的元素中继续寻找
平均时间复杂度：O(n^2)
空间复杂度：O(1)

function selectSort(nums) {
  let n = nums.length;
  for (let i = 0; i < n; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (nums[minIdx] > nums[j]) {
        minIdx = j;
      }
    }
    let temp;
    temp = nums[i];
    nums[i] = nums[minIdx];
    nums[minIdx] = temp;
  }
  return nums;
}

插入排序（Insert Sort）

算法：先将第一个元素看为有序,然后依次将后面的未排序元素插到有序序列的适当位置,直至所有元素完成排序
平均时间复杂度：O(n^2)
空间复杂度：O(1)

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

希尔排序（Shell Sort）

是插入排序的改进版本,效率高,但是不稳定。
算法:先将整个数列分割成若干个子序列,然后对每个子序列进行插入排序,当每个子序列有序时,再对全部数据进行直接插入排序.
平均时间复杂度：O(n*log n)
空间复杂度：O(1)

function shellSort(nums) {
  let n = nums.length;
  let step = (n / 2) >> 0;
  while (step > 0) {
    for (let i = step; i < n; i++) {
      let temp = nums[i];
      let j = i - step;
      while (j >= 0 && nums[j] > temp) {
        nums[j + step] = nums[j];
        j = j - step;
      }
      nums[j + step] = temp;
    }
    step = (step / 2) >> 0;
  }
  return nums;
}

归并排序（Merge Sort）

算法:采用分治法。

• 将数列拆分直至成为每个子序列只包含两个元素，
• 然后将最小的子序列排序后合并为更大一点的子序列，
• 不断重复拆分和合并，最后得到有序序列。
  平均时间复杂度:O(n * log n)
  空间复杂度:O(n)

function mergeSort(nums) {
  // 递归出口
  if (nums.length < 2) {
    return nums;
  }
  let n = nums.length;
  let mid = (n / 2) >> 0;
  // 先将序列进行拆分
  let left = nums.slice(0, mid);
  let right = nums.slice(mid);
  // 然后对拆分的序列排序合并
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let res = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  // 将两个子序列中剩余的元素直接加入到res中
  while (left.length) {
    res.push(left.shift());
  }
  while (right.length) {
    res.push(right.shift());
  }
  return res;
}

快速排序（Quick Sort）

算法：

• 从序列中选取一个元素作为基准（一般选择第一个元素），
• 重新排列元素，将小于基准元素的放在基准前面，大于基准元素的放在基准后面，直至基准元素处于中间位置。
• 将基准左右两侧的子序列进行上述步骤，直至整个序列有序

平均时间复杂度:O(n * log n), 最坏时（O(n^2)）
空间复杂度:O(log n)

function quickSort(nums, left, right) {
  if (left < right) {
    // 获取基准元素下标
    let pivot = partition(nums, left, right);
    // 对基准元素左右子序列递归排序
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
  }
  return nums;
}

// 分区操作
function partition(nums, left, right) {
  // 获取当前子序列的基准元素
  let pivot = nums[left];
  // 当左右指针指向不同元素时
  while (left < right) {
    //如果右指针元素是大于基准元素，则指针往前移一位
    while (left < right && nums[right] > pivot) {
      right--;
    }
    // 此时右指针元素小于基准元素，左指针元素替换为右指针元素
    nums[left] = nums[right];
    // 然后开始移动左指针，当左指针元素小于等于基准元素时，左指针右移
    while (left < right && nums[left] <= pivot) {
      left++;
    }
    // 此时左指针元素大于基准元素，右指针元素替换为左指针元素
    nums[right] = nums[left];
  }
  //此时左右指针指向同一个位置，将此位置赋值为基准元素
  nums[left] = pivot;
  //返回此时基准元素的位置
  return left;
}