tips：
冒泡排序
选择排序
插入排序
归并排序
//#include//编译速度慢#include #include #include using namespace std;//思考题： 给定一个序列，求如果用冒泡排序，需要交换多少次? 等价于求这个序列逆序对的个数void bubble_sort(vector &q){ for(int i = q.size()-1; i > 0; i--){ // 从小到大排，后面是有序的，就可以不用考虑了，所以倒着写方便；外层循环控制边界 bool flag = false; // 加优化， 记录有无进行交换操作 for(int j = 0; j+1 <= i; j++)// 用最靠近末端（边界）的下标去接近边界 if(q[j] > q[j+1]){ swap(q[j],q[j+1]); flag = true ; } if(!flag) break; //这个优化很重要 }}void select_sort(vector &q){ for(int i = 0; i < q.size(); i++){ int minIndex=i; for(int j = i + 1; j < q.size(); j ++) if(q[j] < q[minIndex]){ minIndex = j; } int tmp = q[i]; q[i] = q[minIndex]; q[minIndex] = tmp; }}void insert_sort(vector &q){ for(int i = 1; i < q.size(); i++ ){ //第一个元素相当于排好序了，从1开始 int t = q[i], j; for(j = i - 1; j >= 0; j--){ if(q[j] > t){ //注意这里是t，在动态过程中，考虑在中间操作过程中是否会被修改 q[j+1] =q[j]; } else break; } q[j+1] = t; }}//更多地使用归并排序的思路解决其他问题，比如求逆序对 T:O(nlogn)void merge_sort(vector &q, int l, int r){ if(l >= r) return; int mid = (l + r)/2; merge_sort(q, l, mid); merge_sort(q, mid+1, r); static vector w;//等价于全局变量，开一个静态的空间,辅助数组 w.clear(); //合并两个有序序列 int i = l,j = mid + 1;//定义两个指针，从两个序列的开始指 while(i <= mid && j <= r){ if(q[i] <= q[j]) w.push_back(q[i ++]); else w.push_back(q[j ++]); } while(i <= mid) w.push_back(q[i ++]); while(j <= r) w.push_back(q[j ++]); //把有序数组放回去 for(int i = l,j = 0; j < w.size(); i ++,j ++ ) q[i] = w[j];//推荐写两个变量，好debug //写代码要考虑思路的清晰性}//把问题分解，递归定义一个流程//设计模式，处理流程的思考//看问题的角度，如何把问题从组合计数的角度进行划分：比如求逆序对，左区间的逆序对(往下层递归解决)，右区间的逆序对，左右区间的逆序对//在该层是一个区间，到下一层时就不是一个区间了int merge_nixu(vector &q, int l, int r){ if(l >= r) return 0; int res = 0; int mid = (l + r) /2; res += merge_nixu(q, l, mid);//这个区间的逆序对在下一层被解决 res += merge_nixu(q, mid+1, r); static vector w; w.clear(); //关键操作，从底层往上传结果 int i = l, j = mid+1; while(i <= mid && j <= r){ if(q[i] <= q[j]){ w.push_back(q[i ++]); } else{ res += (mid - i + 1); w.push_back(q[j ++]); } } while(i <= mid ) w.push_back(q[i ++]); while(j <= r) w.push_back(q[j ++]); for(int i = l, j = 0; j < w.size(); i ++, j ++) q[i] =w[j]; return res;}int main(){ int n; vector q; cin >> n; for(int i = 0,t; i < n; i ++ ) { cin >> t; q.push_back(t); } //bubble_sort(q); //select_sort(q);、 //insert_sort(q); //merge_sort(q, 0, q.size() - 1); cout<
//#include//编译速度慢#include #include #include using namespace std;//思考题： 给定一个序列，求如果用冒泡排序，需要交换多少次void bubble_sort(vector &q){ for(int i = q.size()-1; i > 0; i--){ // 从小到大排，后面是有序的，就可以不用考虑了，所以倒着写方便；外层循环控制边界 bool flag = false; // 加优化， 记录有无进行交换操作 for(int j = 0; j+1 <= i; j++)// 用最靠近末端（边界）的下标去接近边界 if(q[j] > q[j+1]){ swap(q[j],q[j+1]); flag = true ; } if(!flag) break; //这个优化很重要 }}void select_sort(vector &q){ for(int i = 0; i < q.size(); i++){ int minIndex=i; for(int j = i + 1; j < q.size(); j ++) if(q[j] < q[minIndex]){ minIndex = j; } int tmp = q[i]; q[i] = q[minIndex]; q[minIndex] = tmp; }}void insert_sort(vector &q){ for(int i = 1; i < q.size(); i++ ){ //第一个元素相当于排好序了，从1开始 int t = q[i], j; for(j = i - 1; j >= 0; j--){ if(q[j] > t){ //注意这里是t，在动态过程中，考虑在中间操作过程中是否会被修改 q[j+1] =q[j]; } else break; } q[j+1] = t; }}//更多地使用归并排序的思路解决其他问题，比如求逆序对 T:O(nlogn)void merge_sort(vector &q, int l, int r){ if(l >= r) return; int mid = (l + r)/2; merge_sort(q, l, mid); merge_sort(q, mid+1, r); static vector w;//等价于全局变量，开一个静态的空间,辅助数组 w.clear(); //合并两个有序序列 int i = l,j = mid + 1;//定义两个指针，从两个序列的开始指 while(i <= mid && j <= r){ if(q[i] <= q[j]) w.push_back(q[i ++]); else w.push_back(q[j ++]); } while(i <= mid) w.push_back(q[i ++]); while(j <= r) w.push_back(q[j ++]); //把有序数组放回去 for(int i = l,j = 0; j < w.size(); i ++,j ++ ) q[i] = w[j];//推荐写两个变量，好debug //写代码要考虑思路的清晰性}int main(){ int n; vector q; cin >> n; for(int i = 0,t; i < n; i ++ ) { cin >> t; q.push_back(t); } //bubble_sort(q); //select_sort(q);、 //insert_sort(q); merge_sort(q, 0, q.size() - 1); for(auto x : q) cout << x << ' '; cout << endl; return 0;}