关于交换，王道考研数据结构书里是这样说的：
有一个博主讲的也不错：交换排序 (冒泡排序 && 快速排序)_跳动的bit的博客-CSDN博客
总之就是比较并移位。并且最经典的交换排序算法是冒泡与快速排序。
一、冒泡排序顾名思义，就是跟冒泡泡一样，不断地比较交换把最大的值冒到当前的最顶层。
动图演示--摘抄自：1.1 冒泡排序 | 菜鸟教程
void BubbleSort(int nums[], int n) {//正的冒泡
//从最底不断往上冒
for (int i = 0; i < n; ++i) {//用于更新冒出的泡所能到达的最顶层
for (int j = 1; j < n - i; ++j) {//从j=1开始冒，冒到当前的最顶层n-i
//交换气泡，保证冒到当前的气泡是在当前层最大的
if (nums[j - 1] > nums[j])swap(nums[j - 1], nums[j]);
}
}
for (int i = 0; i < n; ++i)cout << nums[i] << endl;
}
当然也可以反着冒泡，嗷不，应该叫沉底排序了
void BubbleReverseSort(int nums[], int n) {//反的冒泡
for (int i = n - 1; i > 0; --i) {
for (int j = n - 1; j >= n - i; --j) {//从最上面不停往下沉
if (nums[j] < nums[j - 1])swap(nums[j - 1], nums[j]);
}
}
for (int i = 0; i < n; ++i)cout << nums[i] << endl;
}
冒泡的复杂度是稳定的。时间复杂度为一个等差数列的前n项和，为n²复杂度。
时间复杂度：O(n²)
空间复杂度：O(1)
二、快速排序快排是基于分治的，直接理解概念还是挺好理解的，但是处理边界条件倒挺难的，什么时候该放等号不该放等号，如果不亲自跑通一遍挺容易出错的。
下面是动图，摘自：1.6 快速排序 | 菜鸟教程
快排包含一个分割函数跟一个不断调用分割函数的sort函数。
1.分割函数首先在分割函数中随机选取一个基准pivot(通常是取第一个数为基准)，然后用前后双指针两头遍历。保证右边的一定是大于等于基准，左边的一定是小于等于基准的。而双指针相碰的时候就是pivot所在的位置了。
int Partition(int nums[],int l,int r) {
int pivot = nums[l];//基准的选取，此时l位置保存的数是可覆盖的
while (l= pivot&&r>l) {
--r;//保证基准右边不小于基准
}
nums[l] = nums[r];//将右边比基准小的赋给l，此时r位置的数是可覆盖的
while (nums[l] <= pivot && r > l) {
++l;//保证基准左边不大于基准
}
nums[r] = nums[l];//将左边比基准大的赋给r，此时l位置的数是可覆盖的
}//l==r，两指针相撞，此时代表找到了基准的位置了
nums[r] = pivot;//将基准放到其对应的位置
return r;//返回基准所在的位置，此时将数组以基准为分界线分割成了两部分
}
2.排序函数
在sort函数中调用分割函数并不断缩小区间(由大到小的过程)，直到每一个基准都安排到了自己的固定位置了，那么这个数组便排序好了。
void QuickSort(int nums[], int n) {
auto dfs = [&](int l,int r,auto&& me)->void {
if (r <= l)return;//递归终止条件
int pivot= Partition(nums,l,r);
me(l, pivot - 1, me);//基准前半部分再排序
me(pivot+1,r , me);//基准后半部分再排序
};
dfs(0, n - 1, dfs);
for (int i = 0; i < n; ++i)cout << nums[i] << endl;
}
3.复杂度分析
快速排序是不稳定的排序。
1）最好的情况。即每次都能很好地将区间划分成均等的两部分。这样的话第一次可以扣掉1个数，第二次扣掉两个数...，最后是一个等比数列的前n项和。
此时其时间复杂度为O(nlogn)。
空间复杂度为O(logn)(空间复杂度来自于递归函数的调用深度)
2）最坏的情况。这是一个已经排序好的数列了，每次基准都是在边界上面，这时候是一个等差数列前n项和了。
时间复杂度为O(n)
空间复杂度为O(n²)
3）平均复杂度。这个比较复杂，具体参考：快速排序时间复杂度分析 - 知乎
算法 | 快速排序平均时间复杂度分析 - 知乎
关于空间复杂度可参考：究竟为什么，快速排序的时间复杂度是n*lg(n)？ | 经典面试题_58沈剑的博客-CSDN博客
