排序

插入排序

每次将一个待排序的记录按照关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

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

const nums = [13, 38, 49, 27, 3];
const sortedNums = insertSort(nums);
console.log(sortedNums);

• 空间复杂度：$O(1)$
• 时间复杂度：
  • 最好：$O(n)$ 数组本身就是有序的
  • 最坏：$O(n^2)$ 数组是逆序的
  • 平均：$O(n^2)$
• 稳定性：稳定

希尔排序

思想：先追求表中元素部分有序，再逐渐逼近全局有序。

基于插入排序，当处理的数组本身就有序的时候，插入排序的时间复杂度最低。

希尔元素基于的思想就是数组本身基本有序。

TIP

先将待排序表分割成子表，对各个子表分别进行插入排序。再缩小增量 d（每次缩小一半），重复上述过程，直到 d = 1 为止。

function shellSort(nums) {
  const n = nums.length;
  for (let gap = Math.floor(n / 2); gap >= 1; gap = Math.floor(gap / 2)) {
    // 对每个间隔为 gap 的子序列进行插入排序
    for (let i = gap; i < n; i++) {
      if (nums[i] < nums[i - gap]) {
        let temp = nums[i];
        let j;
        for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) {
          nums[j + gap] = nums[j];
        }
        nums[j + gap] = temp;
      }
    }
  }
  return nums;
}
const nums = [13, 38, 49, 27, 3];
const sortedNums = shellSort(nums);
console.log(sortedNums);

• 空间复杂度：$O(1)$
• 时间复杂度：
  • 最坏：$O(n^2)$
• 稳定性：不稳定
• 适用性：仅适用于顺序表，不适用于链表

冒泡排序

如果想要最终得到一个升序的序列，冒泡排序的思想就是让最小的不断向前冒，或者让最大的不断向后冒。

function bubbleSort(nums) {
  const n = nums.length;
  for (let i = 0; i < n - 1; i++) {
    // 从后向前
    for (let j = n - 1; j > i; j--) {
      if (nums[j - 1] > nums[j]) {
        let temp = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = temp;
      }
    }
  }
  return nums;
}

const nums = [13, 38, 49, 27, 3];
const sortedNums = bubbleSort(nums);
console.log(sortedNums);

这里有一个优化的思路：如果一趟冒泡中没有进行交换，就代表当前数组是有序的了，就可以提前结束函数。

• 空间复杂度：$O(1)$
• 时间复杂度：
  • 最好：$O(n)$ 数组本身就是有序的
  • 最坏：$O(n^2)$ 数组是逆序的
  • 平均：$O(n^2)$
• 稳定性：稳定

快速排序

基本步骤：

1. 从数组中选择一个元素作为基准点
2. 排序数组，所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。
3. 最后利用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。

var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var 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));
};