https://leetcode-cn.com/problems/sort-an-array/

    每一轮(size-1轮)遍历比较相邻元素，当一个元素大于右边元素时，交换它们的位置，这样每一轮都将一个最大元素冒泡到数组中的最右端。

    • 时间复杂度 O(n2)
    • 优化
      • 数组左部分元素都小于右边元素，经过n(n<size-1)后，整个数组已经有序了
        • 如果在一轮冒泡中元素没有发生交换，break
      • 右边元素有序，前几轮冒泡无用
        • 每一轮交换后，记下最后一次元素交换的位置，该位置为无序数组的边界。
          1. // 模板
          2. class Solution {
          3. public:
          4. vector<int> sortArray(vector<int>& nums) {
          5. // 外部循环控制遍历的轮数
          6. for (int i = nums.size() - 1; i > 0; i--) {  // i的右边已经有序
          7.     for (int j = 0; j < i; j++) {
          8.         // 内部循环实现每一轮的冒泡
          9.         if (nums[j] > nums[j+1]) swap(nums[j], nums[j+1]);
          10.     }
          11. }
          12. return nums;
          13. }
          14. };
          // 优化
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
// 外部循环控制遍历的轮数
int sortBoard = nums.size() - 1;  // 优化2
for (int i = nums.size() - 1; i > 0; i--) {
    // 内部循环实现每一轮的冒泡
    i = sortBoard;
    bool isSorted = true;  // 优化1
    for (int j = 0; j < i; j++) {
        if (nums[j] > nums[j+1]) swap(nums[j], nums[j+1]);
        isSorted = false;
        sortBoard = j;  // 不断更新边界的位置
    }
    if (isSorted) break;
}
return nums;
}
};