排序
快速排序(Quick Sort)
快速排序实际上使用的是分治的思想。实现该算法需任取一个元素（随机，如第一个）为中心，所有比它小的元素置前，比它大的元素一律置后，成左右两组.对各子组重新选择中心元素并再次分治，直到每个组的元素只剩一个.当然，这一过程我们使用递归完成。
例如，我们获取的是一个随机大小排列的原初数组，于是取第一个元素x的大小作为中心，然后依次判断后方元素是否大于等于x或小于等于x。
y总还提到了一个双指针做法，十分优美： 设有两个指针i,r最初分别指向数组的最左端和最右端. i指向的数若小于等于x，那么继续向右走(向右遍历检查数组元素大小和x的关系)，若大于X,那么指针i停下.j指向的数若大于x，继续向左走，直到j指向的数小于等于x,此时交换i,j指向的数，往中间移动一位；那么，该排在x右边的数和左边的数都归位了一组；此时i,j指针再继续向中间走，但此时i检验的就是之前j检验的小于x的数，
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
typedef long long ll;
const int MAXN = 2e5 + 10;
const int N = 105;
using namespace std;
int q[MAXN];
int n;
void quicksort(int q[], int l, int r)
{
if (l >= r)
return;//数组里面没有数了.
int x = q[l], i = l - 1, j = r + 1;//数组下标从0开始故进一位.方便调整
while (i < j)
{
do { i++; } while (q[i] < x);
do { j--; } while (q[j] > x);
if (i < j)//指针前进
swap(q[i], q[j]);//指针位置不移动。交换数值
}
quicksort(q, l, j);//指针
quicksort(q, j + 1, r);
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> q[i];
}
quicksort(q,0,n-1);
for (int i = 0; i < n; ++i)
{
cout << q[i] << " ";
}
return 0;
}
归并排序(Merge Sort)
归并排序的本质是把一个随机序列分为n个小序列，之后两两合并成一个新的有序表，最后将n/2个新的有序表一步步合并成一个总的有序表。
算法实现： 算法的最后比较两个有序表的元素的大小，从第一个开始，谁小就先取谁，取了就在原数列里删，时间复杂度O(n)：
void merge(int a[],int n,int b[],int m,int c[])
{
//将a[]和b[]合并到新的c[]中.
int i,j,k;
i=j=k=0;
while(i<n&&j<m)
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
}
while(i<n)
c[k++]=a[i++];
while(j<m)
c[k++]=b[j++];
}
单数组也可以，尤其是求逆序对个数这样的经典归并题：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
typedef long long ll;
const int MAXN = 2e5 + 10;
const int N = 105;
using namespace std;
int a[MAXN],c[MAXN];
//将有序数组a[]和b[]合并到c[]中
//log P1908
ll sum = 0;
void solve(int k,int n)
{
if (n == 1)
return;
else
{
int mid = (k+n) / 2, i = k, j = mid + 1, o=k;
solve(1, mid);
solve(mid + 1, n);
while (i <= mid && j <= n)
{
if (a[i] <= a[j])
c[k++] = a[i++];
else
{
c[k++] = a[j++];//记录了更小的那个数，于是从小到大排一次，更大的那个数继续比较
sum+=mid-i+1;//前面的比后面的大就能计数
}
}
while(i<mid+1)
c[k++]=a[i++];//补位
while(j<n)
c[k++]=a[j++];
for(int l=k;l<n;++l)
{
a[l]=c[l];
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
solve(0,n);
cout<<sum<<endl;
return 0;
}
整数二分
二分的本质并不是单调性，他们之间存在的是“有单调性就可以二分”这种关系。整数二分的两个区间无交点。
bool check(int x) {/* ... */} // 检查x是否满足某种性质
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
冒泡排序(Bubble Sort)
时间复杂度较大，比较传统的一种排序。 主打一个大小互换。
int arr[80];
void bubble(int a[],int n)
{
int end =n;
while(end)
{
int flag = 0;
for(int i=1;i<end;++i)
{
if(arr[i-1]>arr[i])
{
int tem =arr[i];
arr[i]=a[i-1];
arr[i-1]=tem;
flag=1;
}
}
if(!flag)
break;
end--;
}
}
希尔排序（Shell's Sort）
也称缩小增量排序。初始增量为数组长度/2，整个数组被分成a[1]和a[6],a[2]和a[7]等5组。这5组里面比对，如果a[1]>a[6]那么交换值。然后增量缩到5/2=2。数组被分为a[1]/a[3]/a[5]/a[7]/a[9]和a[2]...两组。以此类推，增量缩到2/2=1。然后对这个单独的子序列进行排序。
void shellsort(int n,int arr[])
{
for(int gap=arr.length/2;gap>0;gap=gap/2)
{
for(int i=gap;i<arr.length;++i)
{
for(int j=i-gap;j>=0;j-=gap)
{
if(arr[j]>arr[j+gap])
{
int temp=arr[j];
arr[j]=arr[j+gap];
arr[j+gap]=temp;
}
}
}
}
}