一、冒泡排序（稳定排序）

思想：冒泡排序的思想就是比较当前数和后一个数的大小，将较大的数往后移动，这样可以确保一轮下来能将最大的数放在数组的最末端。然后重复此操作即可完成排序。

上面第一轮比较完，我们可以看到最大的数5已经被放在了最端，此时我们只需要将去掉最大的数的那部分（2，3，1，4）进行重复的操作。

class Solution {
public:vector MySort(vector& arr) {// 冒泡排序if(arr.size()==1)   return arr;for(int i=0;iarr[j+1]) swap(arr[j],arr[j+1]);}}return arr;}
};

如果数组一共有length个元素，则一共需要进行length-1轮比较，每轮完成后都会少一个进行比较。

若文件的初始状态是正序的，一趟扫描即可完成排序。所以，冒泡排序最好的时间复杂度为 O(n)

若初始文件是反序的，需要进行 n-1趟排序。每趟排序要进行 n-1 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置，冒泡排序的最坏时间复杂度为O(n2)。

综上，因此冒泡排序总的平均时间复杂度为O(n2)

 二、快速排序

快速排序(Quick Sort)：快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。快速排序又是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，速度较快，故称为“快速排序”。

快速排序的基本思想是：

1. 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最优的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
2. 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
3. 对左右两个分区重复以上步骤直到所有元素都是有序的。

void quickSort(vector& nums, int left, int right) {if (left < right){int base = nums[left];int low = left, high = right;while (low < high){while (low < high && nums[high] >= base){high--;}swap(nums[low], nums[high]);while (low < high && nums[low] <= base){low++;}swap(nums[low], nums[high]);}quickSort(nums, left, low - 1);	quickSort(nums, low + 1, right);}
}int main() {vector nums = { 2,3,5,1,4 };for_each(nums.begin(), nums.end(), [=](int x) {cout << x << " "; });cout << endl;quickSort(nums, 0, nums.size() - 1);for_each(nums.begin(), nums.end(), [=](int x) {cout << x << " "; });
}