双端冒泡排序

双端冒泡排序是对传统冒泡排序的改进，其主要改进在于同时从两端开始排序，相对于传统冒泡排序每次只从一端开始排序，这样可以减少排序的遍历次数。

传统冒泡排序从一端开始，每次将最大（或最小）的元素冒泡到序列的一端，然后再从剩余的元素中继续冒泡。这个过程需要进行 n-1 次遍历，每次遍历需要比较相邻的元素并进行交换。

而双端冒泡排序则从序列的两端同时开始，同时将最大和最小的元素冒泡到序列的两端，然后再缩小序列的范围，继续从两端开始冒泡。这样在一次遍历中可以确定两个边界的正确位置，从而减少了排序的遍历次数。

总体上来说，双端冒泡排序减少了比较和交换的次数，从而相对于传统冒泡排序有更好的性能。然而，双端冒泡排序的时间复杂度仍然是 O(n^2)，因此对于大规模数据集，仍然不是最优选择。但在某些特定情况下，双端冒泡排序可能比传统冒泡排序略快一些。

class Solution {
public:void swap(int &a, int &b) {int tmp = a;a = b;b = tmp;}vector<int> sortArray(vector<int>& nums) {int left = 0;int right = nums.size() - 1;bool flag = true;while(left < right && flag) {for (int i = left; i < right - 1; i++) {if (nums[i] > nums[i+1]) {swap(nums[i], nums[i+1]);flag = true;}}left++;for (int i = right; i >= left; i--) { // 注意这个边界条件，这里不会越界if (nums[i-1] > nums[i]) {swap(nums[i-1], nums[i]);flag = true;}}right--;}return nums;}
};