一、快速排序
1、确定分界点：q [ l ] , q [ ( l + r ) / 2 ] , q [ r ] ,或者其它区间之中的随机数。（左 l 右 r ）
2、调整区间：（较难理解的部分）
（1）、暴力做法
（1）开两个数组a[ ] b[ ]
（2）扫描 q [ l ] ---> q [ r ]整个区间
q [ i ]<=x , x ---> a[ ]
q [ i ]>x , x ---> b[ ]
（2）、优雅做法hhh
用两个指针 : 左边 i 指针 右边 j 指针
(1) i <= x 就右移，直到 i >= x 时停下
(2) j >= x 就左移，直到 j <= x 时停下
(3) swap ( i 指向的数， j 指向的数）
重复上述（1）（2）（3）操作
3、递归处理左右两段
void quick_sort(int q[], int l, int r){
if(l>=r)return;
int x= q[(l+r)/2], i=l-1, j=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);
}二、归并排序
归并排序——分治
步骤一、确定分界点（中点）
mid = ( l + r ) / 2 （左 l 右 r ）
步骤二、递归排序左右两段
步骤三、归并（较难理解的部分）
运用双指针算法 将左右两个有序序列合并成一个有序序列
void merge_sort(int q[],int l,int r){
//递归的终止情况
if(l>=r)return;
//第一步：分成子问题
int mid = l+r>>1;
//第二步：递归处理子问题
merge_sort(q, l, mid), merge_sort(q, mid+1, r);
//第三步：合并子问题
int k = 0, i = l, j = mid+1;
while( i<=mid && j<=r )
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for( i=l,j=0; i<=r; i++,j++ ) q[i]=tmp[j];
}
三、库函数处理排序问题
在C++中使用sort()函数需要使用
#include<algorithm>头文件三个参数
sort(begin, end, cmp)其中 begin为指向待sort()的数组的
第一个元素的指针
end为指向待sort()的数组的最后一个元素的下一个位置的指针
cmp参数为排序准则，cmp参数可以不写（如果不写的话，默认从小到大进行排序）
下面我们用这三种方法来实现一个简单例题 输出样例
一、快速排序
#include<iostream>
using namespace std;
const int N=1e6+10;
int n;
int q[N];
void quick_sort(int q[],int l,int r){
if(l>=r) return;
int x=q[(l+r)/2];
int i=l-1;
int j=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(){
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;
} 二、归并排序
#include <iostream>
using namespace std;
const int N=1e6+10;
int q[N];
int n;
int tmp[N]; //归并排序除了快排的参数，还需要tmp[]数组辅助
void merge_sort(int 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);
int k=0; //k表示现在tmp里面已经有几个数了
int i=l; //i指针指向left的起点
int j=mid+1;//j指针指向right的终点
while(i<=mid&&j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++]; //如果左边还没有循环完就补齐
while(j<=r) tmp[k++]=q[j++]; //如果右边还没有循环完就补齐
for(i=l,j=0;i<=r;i++,j++){
q[i]=tmp[j]; //将tmp[]中的内容移植到q[]中
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
merge_sort(q,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
return 0;
}三、库函数处理排序问题(非常easy)
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int q[N];
int n;
int main(){
cin>>n;
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
sort(q,q+n);
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
return 0;
}
