快速排序
给定你一个长度为 n n n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n n n。
第二行包含 n n n 个整数（所有整数均在 1 ∼ 1 0 9 1∼10^9 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n n n 个整数，表示排好序的数列。
数据范围
1 ≤ n ≤ 100000 1≤n≤100000 1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
解题思路
思路分析：
每一次找一个分界点x，小于它的数放到x左边,大于x的数放到x右边，完成之后可以得到两个有序数组，然后再递归，直至所有元素都完成排序。
模拟：
假设对6,1,2,7,9,3,4,5,10,8这10个数进行排序：
本次模拟的分界点是数组的第一个元素。
1、从后向前扫描,i去向右找第一个大于基准6的数字,j向左查找第一个小于基准6数字：
这里注意，i先走，如果遇到比x大的，停下来，然后j再往左走，遇到比x小的停下来，再交换i，j，之后i，j都中间移动继续上述操作。
2、找到7和5,交换7和5
3、继续前进,找到9和4,然后交换
4、i>=j，交换6和3
交换之后：3,1,2,5,4,6,9,7,10,8 一趟排序结束。
划分的两堆数据，继续进行递归操作，完成所有数据排序。
AC_Code
#include<iostream> using namespace std; const int N = 1e6 +10;//1000010 int n; int q[N]; //快排模板 void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r);//递归迭代 } int main(){ scanf("%d",&n); for(int i = 0;i<n;i++) scanf("%d",&q[i]); quick_sort(q,0,n-1); for(int i = 0;i<n;i++) printf("%d ",q[i]); return 0; }
注意：这里面的x 不能取到q[r]，否则会死循环
二分查找
用二分法求 平方根
//浮点数二分 #include<iostream> using namespace std; int main() { double x; cin>>x; double l = 0,r = x; while(r - l > 1e-6) { double mid = (l+r)/2; if(mid * mid >= x) r = mid; else l = mid; } printf("%.3f",l); return 0; }
#include<iostream> using namespace std; int main() { double x; cin>>x; double l = 0,r = x; //while(r - l > 1e-5)//要求保留三位有效数字--->精度到1e-5就可以了，多出两位 for(int i = 0;i < 100;i++)//直接迭代100次 { double mid = (l+r)/2; if(mid * mid >= x) r = mid; else l = mid; } printf("%.3f",l); return 0; }
二分模板
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)