1.冒泡排序
听名字还挺可爱的，冒泡(●’◡’●)。
为啥叫冒泡呢？
算法原理是：
对N个元素进行排序，进行N-1次循环。
在对第K次循环中，对前N-K个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素，就交换，否则保持位置不变（就是实现了把前N-K个中最大放到了最后）。
所以每次排序一定能保证当前第k大的回落到第N-K个位置，称为第K趟的冒泡。
代码：
void BubbleSort(int a[],int n)
{
int i,j,temp;
bool flag; //相对来说能减少一定的时间复杂度
for(i=n-1;i>=0;i--) //为什么这么写呢？其实很简单啊，我每次是排最大，那么当然是从大排到小。
{
flag=false;
for(j=0;j<i;j++) //每次是找最大的往后跑。
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
flag=true; //如果有交换就标记
}
if(!flag) break;
}
} 2.快速排序
快速排序的原理：
将未排序元素根据基准分为两个子序列，其中一个子序列的记录均大于基准，而另一个子序列均小于基准，然后递归的对两个子序列用类似的方法进行排序。
本质上，快速排序使用的是分治法，将问题的规模减小一半左右，然后再分别进行处理。（看不懂没关系，看下面的流程）
快速排序的流程：
对于一趟基准调整的过程：
①：选择一个基准，并与最后一个元素进行交换；
②：设置两个指针Low和High，初值（这个“初值”讲的很妙啊，指针嘛，存的是地址啊）分别指向第一、倒数第二个元素；
③：重要： 先Low从左往右（顺序）扫描，如果遇到比基准（此时在数组最后位置）大，Stop；High指向的位置开始从右往左（倒序），如果遇到比基准小，Stop；
④：这是第③步结果的执行：1.如果High和Low没有错位（High>Low），High和Low指向的元素互换位置；
⑤：重复③④两步，直到High和Low错位，然后基准和数组元素A[Low]交换。
可以看到，Low和High执行过程中，Low位置之前的元素一定比基准小，High位置之后的元素一定比基准大，这样就完成了一次划分，分成了小于和大于基准的两个子序列。
⑥：递归地对两个子序列用同样的方法进行快速排序算法流程。
感觉是可以随便拿几个数模拟一下一趟快速排序，快速排序算法也达到了分而治之的算法目的。
代码：
void Swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void QSort(int a[], int Low, int High)//对Low到High区间内进行一趟快速排序
{
int Pivot = a[Low]; //随便挑了首元素作为基准;
int left=Low,right=High;
if(Low>=High) return;
Swap(&a[Low],&a[High]);
while(1)
{
while((Low<High)&&(Pivot>=a[Low])) Low++;
while((Low<High)&&(Pivot<=a[High])) High--;
if(Low<High)
Swap(&a[Low],&a[High]);
else
break;
}
Swap(&a[Low],&a[right]);//把基准放到正确的位置。
//递归对两个子序列进行快速排序
QSort(a,left,Low-1);
QSort(a,Low+1,right);
}
void QuickSort(int a[], int n)
{
QSort(a,0,n-1);
}快速排序算法的考点Just for the qimo(final) test(还是exam)：
时间复杂度：最好的情况下，每次划分都划分成两个基本等长的序列，那么递归层次（即深度）是O(logN)，每一次递归层次上的比较总次数都是O(N)，所以最好时间复杂度是O(NlogN)。但是如果每次划分都是1和N-1，则快速排序的执行时间就会接近于冒泡排序，可能导致O(N^2)的时间效率。
基准：在A[Low],A[High],A[(Low+High)/2]三个的中值作为基准，这样有可能避免时间复杂度出现的最坏情况。
快速排序是不稳定的。
归并排序
前言：
归并排序是建立在归并操作上的一种排序方法。
归并操作是将两个已经排列好的序列合并成一个有序序列的过程。
归并排序算法的原理：
把长度为N的序列看成N个长度为1的字序列，接下来就是把相邻两个字序列合并，形成［N／2］个长度为2的有序字序列；然后继续合并两两归并，如此一直下去直到剩下一个长度为N的序列。
原理非常简单易懂，直接进行代码实现吧。
归并排序到代码：
void Merge(int a[],int temp[],int Left,int Mid,int Right)
{
int tp,dis,i,Leftend;
Leftend=Mid-1; //左边序列终止位置
dis=Right-Left+1;//dis为间距
tp=Left; //有序序列的起始位置
while(Left<=Leftend&&Mid<=Right)
if(a[Left]<=a[Mid]) temp[tp++]=a[Left++];
else temp[tp++]=a[Mid++];
while(Left<=Leftend) temp[tp++]=a[Left++];//如果左边还有多
while(Mid<=Right) temp[tp++]=a[Mid++];//如果右边还有多
for(int i=0;i<dis;i++,Right--)
a[Right]=temp[Right]; //赋值
}
void MSort(int a[],int temp[],int Left,int Right)
{
if(Left<Right)
{
MSort(a,temp,Left,(Left+Right)/2);
MSort(a,temp,(Left+Right)/2+1,Right);
Merge(a,temp,Left,(Left+Right)/2+1,Right);
}
}
void MergeSort(int a[],int n)
{
int temp[110];
MSort(a,temp,1,n);
}
考点just for the final test:
时间复杂度：进行O(logn)次递归，每次递归有n次比较，所以是O(nlogn)的；
空间复杂度：O(N);
稳定的排序算法。