四种基本排序方法（C/C++实现）
设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：
冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；
二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；
快速排序一趟扫描的结果是 F H C D P A M Q R S Y X；
堆排序初始建堆的结果是 Y S X R P C M H Q D F A 。（大根堆）
快速排序的基本思想：
1任取一个元素 (如第一个) 为中心。
2所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表。
3对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。
注：
①每一趟的子表的形成是采用从两头向中间交替式逼近法；
②由于每趟中对各子表的操作都相似，可采用递归算法。
快速排序一趟扫描解析：取子序第一个数据项Q作为中心，指针low指向Q（Q被取出来，已经为空，待存放high指针值比Q小的数），指针high指向最后Y。
初始值 Q, H, C, Y, P, A, M, S, R, D, F, X
注：%代表low，&代表high
%, H, C, Y, P, A, M, S, R, D, F, X& //取出Q ，low指向%，high指向X&。
%, H, C, Y, P, A, M, S, R, D, F&, X //X比Q大，high往左移一位，指向F。
F, H%, C, Y, P, A, M, S, R, D, &, X //F比Q小，存入#的位置，
F, H, C%, Y, P, A, M, S, R, D, &, X
F, H, C, Y%, P, A, M, S, R, D, &, X
F, H, C, %, P, A, M, S, R, D&, Y, X
F, H, C, D, P%, A, M, S, R, &, Y, X
F, H, C, D, P, A%, M, S, R, &, Y, X
F, H, C, D, P, A, M%, S, R, &, Y, X
F, H, C, D, P, A, M, S%, R, &, Y, X
F, H, C, D, P, A, M, %, R&, S, Y, X
F, H, C, D, P, A, M, %&, R, S, Y, X
F, H, C, D, P, A, M, Q, R, S, Y, X
二趟扫描：Q分两个子序（F, H, C, D, P, A, M）和（R, S, Y, X ），这两个子序分别按照上面的思路排序，便是快排。
四种排序方法
注：为研究排序本身，我们的数组a[0]设为哨兵，数据从a[1]开始。
排序算法分类
规则不同
1.插入排序
2.交换排序（冒泡排序、快速排序）
3.选择排序
4.归并排序（二路归并排序、排序过程、两个有序子序列的归并、归并排序（递归）、C++实现、算法分析）
直接插入排序
冒泡排序
一趟冒泡排序：设要排序的数组是A[1]……A[N]，首先比较数组的第一个数和第二个数关系，逆序移动，正序不变，重复到第N-1个数，这个过程称为一趟快速排序。
原理：两两交换，大数据就慢慢往一个方向移动，就像水里的泡泡一样，该排序很简单，无需多言。
暴力代码
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
typedef int Status;
typedef struct
{
int *a;
int length;
}SqList;
Status BubbleSort(SqList &L)
{
int n=L.length,*a=L.a;
for(int i=1;i<=n-1;i++) //趟数n-1
{
for(int j=1;j<=n-i;j++) //比较次数n-i
{
if(a[j]>a[j+1]) //如果前面的数比后面的大，交换
{
int temp=a[j]; //定义t为整数型，用于暂时保存大的值
a[j]=a[j+1]; //交换次序，a[j+1]较小，放前面
a[j+1]=temp; //a[j+1]从暂时保存的大的值t取回来
}
}
}
return OK;
}
Status InitList(SqList &L)
{
L.a=new int(MAXSIZE);
L.length=0;
return OK;
}
Status Print(SqList L)
{
for(int i=1;i<=L.length;i++)
cout<<L.a[i]<<" ";
return OK;
}
int main()
{
int n=6,a[7]={0,21,25,49,25,16,8};//定义 n为整数，a为整数组
SqList l;
InitList(l);
l.a=a;
l.length=n;
BubbleSort(l);
Print(l);
return 0;
}
每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换，还可提前结束排序
优化代码
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
typedef int Status;
typedef struct
{
int *a;
int length;
}SqList;
Status BubbleSort(SqList &L)
{
int n=L.length,*a=L.a;
for(int i=1;i<=n-1;i++) //趟数n-1
{
int flag=1;
for(int j=1;j<=n-i;j++) //比较次数n-i
{
if(a[j]>a[j+1]) //如果前面的数比后面的大，交换
{
int temp=a[j]; //定义t为整数型，用于暂时保存大的值
a[j]=a[j+1]; //交换次序，a[j+1]较小，放前面
a[j+1]=temp; //a[j+1]从暂时保存的大的值t取回来
flag=0;
}
}
if(flag==1)//一趟结束没有交换，提前结束排序
break;
}
return OK;
}
Status InitList(SqList &L)
{
L.a=new int(MAXSIZE);
L.length=0;
return OK;
}
Status Print(SqList L)
{
for(int i=1;i<=L.length;i++)
cout<<L.a[i]<<" ";
return OK;
}
int main()
{
int n=6,a[7]={0,21,25,49,25,16,8};//定义 n为整数，a为整数组
SqList l;
InitList(l);
l.a=a;
l.length=n;
BubbleSort(l);
Print(l);
return 0;
}
冒泡排序（优化代码）总结：
时间复杂度：
平均情况O(n²)
最好情况O(n),只需 1趟排序，比较次数为 n-1，不移动
最坏情况O(n²),需 n-1趟排序，第i趟比较n-i次，移动3(n-i)次
Screen Shot 2018-12-19 at 10.18.59.png
空间度杂度：O(1)
稳定性：稳定
快速排序
一趟快速排序：设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
快速排序（Quicksort）是对冒泡排序（Bubblesort）的一种改进。
基本思想：
任取一个元素 (如第一个) 为中心
所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个
简单选择排序
二路归并排序
一趟2-路归并排序：设要排序的数组是A[1]……A[N]，首先划分n/2个子序，每个子序正序不变，逆序移动，这个过程叫一趟2-路归并排序。
归并：将两个或两个以上的有序表组合成一个新有序表
2-路归并排序
排序过程
初始序列看成n个有序子序列，每个子序列长度为1
两两合并，得到n/2个长度为2或1的有序子序列
再两两合并，重复直至得到一个长度为n的有序序列为止
两个有序子序列的归并
l设两个有序表存放在同一数组中相邻的位置上：R[low..mid]和R[mid + 1..high]
l每次分别从两个表中取出一个记录进行关键字的比较，将较小者放入T[1ow..high]中
l重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
int i=low;int j=mid+1;int k=low;
while(i<=mid&&j<=high) //将R中记录由小到大地并入T中
{
if(R[i].key<=R[j].key)
T[k++]=R[i++];
else
T[k++]=R[j++];
}
while(i<=mid) T[k++]=R[i++]; //将剩余的R[low..mid]复制到T中
while(j<=high) T[k++]=R[j++];//将剩余的R[j.high]复制到T中
}
归并排序（递归）
2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时，递归结束，否则：
u① 将当前序列一分为二，求出分裂点mid= ë(low+high)/2û；
u②对子序列R[low..mid]递归，结果放入S[low..mid]中；
u③对子序列R[mid + 1..high]递归，结果放入S[mid + 1..high]中；
u④调用算法Merge，将S[low..mid]和S[mid + 1..high]归并为T[low..high]。
void MSort(RedType R[],RedType T[],int low,int high)
{
RedType S[MAXSIZE];
if(low==high)
{
T[low]=R[low];
}
else
{
int mid=(low+high)/2; //将当前序列一分为二，求出分裂点mid
MSort(R,S,low,mid); //R[low..mid]递归，结果放入S[low..mid]
MSort(R,S,mid+1,high);//R[mid+1..high]递归，结果放入S[mid+1..high]
Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..high]归并到T[low..high]
}
}
C++实现
#include<iostream>
using namespace std;
#define MAXSIZE 100
typedef struct
{
int key;
}RedType;
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
int i=low;int j=mid+1;int k=low;
while(i<=mid&&j<=high) //将R中记录由小到大地并入T中
{
if(R[i].key<=R[j].key)
T[k++]=R[i++];
else
T[k++]=R[j++];
}
while(i<=mid) T[k++]=R[i++]; //将剩余的R[low..mid]复制到T中
while(j<=high) T[k++]=R[j++];//将剩余的R[j.high]复制到T中
}
void MSort(RedType R[],RedType T[],int low,int high)
{
RedType S[MAXSIZE];
if(low==high)
{
T[low]=R[low];
}
else
{
int mid=(low+high)/2; //将当前序列一分为二，求出分裂点mid
MSort(R,S,low,mid); //R[low..mid]递归，结果放入S[low..mid]
MSort(R,S,mid+1,high);//R[mid+1..high]递归，结果放入S[mid+1..high]
Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..high]归并到T[low..high]
}
}
int main()
{
RedType R[MAXSIZE];
RedType T[MAXSIZE];
R[1].key=3;
R[2].key=2;
R[3].key=1;
MSort(R,T,1,3);
for(int i=1;i<=3;i++) cout<<T[i].key<<" ";
return 0;
}
//3 2 1
//2 3 1
//1 2 3
算法分析
时间效率：O(nlog2n)
空间效率：O（n）
稳 定 性：稳定
