快速排序
根据这个思路, 可以从左边和右边一起往中间遍历, 直到两个指针相遇, 交换二者的值
实现方法.
1. 取一个值 x = q[l+r>>2], 定义两个指针 i = l-1,j = r+1;
2. 根据思路进行遍历
3. 递归处理左右两边
- #include <iostream>
- using namespace std;
- const int N = 100010;
- int q[N],n;
- void quick_sort(int q[],int l,int r)
- {
- if(l>= r) return ;
- int x = q[l+r>>1],i = l-1,j = r+1;
- while(i <j)
- {
- do i++; while(q[i] < x);
- do j--; while(q[j]> x);
- if(i <j)
- {
- int a = q[i];
- q[i] = q[j];
- q[j] = a;
- }
- }
- quick_sort(q,l,j);
- quick_sort(q,j+1,r);
- }
- int main()
- {
- cin>> 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;
- }
快速排序
来源: http://www.bubuko.com/infodetail-3414600.html