明确：实际应用中，直接用sort()函数就好了，但是学习过程还是多了解点东西比较好，而且排序过程中运用的思想也很重要
例1.直接插入排序
从左往右处理数据，每处理一个数据，就将这个数据从当前位置的前一个位置开始往前比较，直到找到小于它的数据，然后插在它的前面（以从小到大排序为例）。稳定。
void InsertionSort(int R[],int n){ //对R[1]...R[n]排序
for(int i=2; i<=n; i++){
int K=R[i], j=i-1;
while(j>=1 && R[j]>K){
R[j+1]=R[j];
j--;
}
R[j+1]=K;
}
}例2.冒泡排序
每次循环找到当前最大的，并把它放到队尾相应的位置。然后进行多次循环。稳定。
void SimpleBubbleSort(int R[], int n){
for(int bound=n; bound>=2; bound--)
for(int i=1; i<bound; i++)
if(R[i] > R[i+1])
swap(R[i],R[i+1]);
}例3.直接选择排序
每次选出除了已经排好序外的最大的数值，最后进行一次交换。进行n-1次该操作。不稳定。
例4.希尔排序
将元素分为d组，对每组使用直接插入排序，将直接插入排序的步调定为d，然后d值逐渐减小，直至为1。在逻辑上感觉复杂度没有很大变化，但是在执行过程中会变快。
void ShellSort(int R[], int n){ //对R[1]…R[n]递增排序
for(int d=n/2; d>0; d/=2) //d为增量值
for(int i=d+1; i<=n; i++){ //.....R[i-3d], R[i-2d], R[i-d] <-R[i]
//把直接插入排序的步调换成了d
int K=R[i],j=i-d; //指针j从右往左扫描本组元素
while(j>0 && R[j]>K){//在本组从右往左找第1个<=K的元素
R[j+d]=R[j];
j-=d;
}
R[j+d]=K;
}
}例5.堆排序
按照二叉树的结构，每次选出最大的，只要logn的时间，这样时间复杂度就会降到nlogn
选出最大的就是在二叉树中从叶结点的父节点开始将该结点与它左右孩子结点的值进行比较，将最大值与父结点进行交换。这样一层一层往上，就可以保证根结点是最大的。同时完全二叉树的结点编号与数组有着对应关系。比如，结点i的左孩子是2i，右孩子是2i+1。这样就可以确定最大的不是叶结点的编号是n/2。
void ShiftDown(int R[], int n, int i) {
//堆元素R[i]下沉, 数组R[ ]存储堆, n为堆包含的元素个数
while(i <= n/2){ //i最多下行至最后一个非叶结点
int maxchd = 2*i; // 假定最大孩子为左孩子
if(maxchd+1<=n && R[maxchd]<R[maxchd+1])
maxchd++; //i的右孩子是最大孩子
if(R[i] >= R[maxchd]) return;
swap(R[maxchd],R[i]); // R[i]的最大孩子比R[i]大
i = maxchd; // 结点i继续下沉
}
}
void BuildHeap(int R[],int n){
for(int i=n/2; i>=1; i--)
ShiftDown(R,n,i); //建立以i为根的堆，即下沉i
}
void HeapSort(int R[],int n){ //堆排序R[1]…R[n]
BuildHeap(R, n); //将R建为堆
for(int i=n; i>1; i--){ //i为当前堆的堆尾
swap(R[1], R[i]); //前i个元素的最大者R[1]与R[i]交换
ShiftDown(R,i-1,1); //下沉R[1]使R[1]...R[i-1]重建为堆
}
}例6.快速排序
快速排序就是选取基准元素，然后将数组的元素分割成，小于等于该元素的，和大于该元素的。每次循环，将小于等于该元素的往左放，大于该元素的往右放，这样每次循环就可以确认出该元素的位置，同时将数组分成两个小数组再次处理。
这种处理数据的方式还可以转化到多个方面方面，比如三路分划。
int Partition(int R[], int m, int n){ //对子数组Rm…Rn分划
int K=R[m], L=m+1, G=n; //Rm为基准元素
while(L<=G) {
while(L<=n && R[L]<=K) L++; //从左向右找第一个>K的元素
while(R[G]>K) G--; //从右向左找第一个K的元素
if(L<G) {swap(R[L],R[G]); L++; G--;}
}
swap(R[m],R[G]);
return G;
}
void QuickSort(int R[], int m, int n){ //对Rm…Rn递增排序
if(m < n){
int k=Partition(R, m, n);
QuickSort(R, m, k-1);
QuickSort(R, k+1, n);
}
}例7.归并排序
归并排序就是把数组分成两部分，递归调用，然后对这两部分进行归并。就是再开一个数组，然后从小到大对该数组进行合并。像单链表的排序就非常适合归并排序。
void Merge(int R[],int low, int mid, int high){
//将两个相邻的有序数组(Rlow,…,Rmid)和(Rmid+1,…,Rhigh)合并成一个有序数组
int i=low, j=mid+1, k=0;
int *X=new int[high-low+1];
while(i<=mid && j<=high)
if(R[i]<=R[j]) X[k++]=R[i++];
else X[k++]=R[j++];
while(i<=mid) X[k++]=R[i++]; //复制余留记录
while(j<=high) X[k++]=R[j++];
for(i=0; i<=high-low; i++) //将X拷贝回R
R[low+i]=X[i];
delete []X;
}
void MergeSort(int R[], int m, int n){
if(m < n){
int k = (m+n)/2; //将待排序序列等分为两部分
MergeSort(R, m, k);
MergeSort(R, k+1, n);
Merge(R, m, k, n);
}
}还可以变形，进行非递归调用。两种方法考题经常会问非递归调用的方法。
void Merge(int R[],int low, int mid, int high){
//将两个相邻的有序数组(Rlow,…,Rmid)和(Rmid+1,…,Rhigh)合并成一个有序数组
int i=low, j=mid+1, k=0;
int *X=new int[high-low+1];
while(i<=mid && j<=high)
if(R[i]<=R[j]) X[k++]=R[i++];
else X[k++]=R[j++];
while(i<=mid) X[k++]=R[i++]; //复制余留记录
while(j<=high) X[k++]=R[j++];
for(i=0; i<=high-low; i++) //将X拷贝回R
R[low+i]=X[i];
delete []X;
}
void MergePass(int R[], int n, int L){
int i;
for(i=1; i+2*L-1<=n; i+=2*L)
Merge(R, i, i+L-1, i+2*L-1);
//处理余留的长度小于2*L的子数组
if(i+L-1<n)
Merge(R, i, i+L-1, n); //L<剩余部分长度<2L
}用这种方法还可以求逆序对的个数，就是在不满足前一个数组小于后一个数组时，用全局变量cnt+=mid-i+1这样就可以求解了。不过这种方法就是，在求逆序对的时候很好用，但是平时我也想不出来它还能有什么应用。