O(n²) 算法

1. 冒泡排序 (稳定)

   • 一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
   • 经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；
   • 进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

2. 选择排序 (不稳定)

   双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。

void selectionSort(vector<int>& nums) {
  int n = nums.size(), minIndex;
  for (int i = 0; i < n; i++) {
    minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (nums[minIndex] > nums[j]) {
        // 记录最小值的下标
        minIndex = j;
      }
    }
    // 将最小元素交换至首位
    swap(nums[i], nums[minIndex]);
  }
}

3. 插入排序 (稳定)

   插入排序是指在待排序的元素中，假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 n 个数的这个序列也是排好顺序的。

   • 交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
   • 移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。

void insertSort(vector<int>& nums) {
  int n = nums.size();
  // 从第二个数开始，往前插入数字
  for (int i = 1; i < n; ++i) {
    // j 记录当前数字下标
    int j = i;
    // 当前数字比前一个数字小，则将当前数字与前一个数字交换
    while (j > 1 && nums[j] < nums[j - 1]) {
      swap(nums[j], nums[j - 1]);
      --j;
    }
  }
}