冒泡排序：
从后往前，依次把相邻两个元素中值较小的元素往前挪。
每次比较的两个元素是相邻的两个元素。
第n次遍历结束后确定第n个位置的元素。
若比较的两个元素相等，则不交换，所以冒泡排序是稳定排序。
时间复杂度：O(n*n)
void BubbleSort(int *iData, int iSize)
{
int iTemp = 0;
for(int i=1; i<iSize; ++i) {
for(int j=iSize-1; j>=i; --j) {
if(iData[j] < iData[j-1]) {
iTemp = iData[j-1];
iData[j-1] = iData[j];
iData[j] = iTemp;
}
}
}
}
交换排序：
第n次以第n个位置为基准，依次将其与后面的元素比较，根据比较结果决定是否交换它们的值。
每次比较的两个元素都是基准位置的元素与当前遍历到的元素。
第n次遍历结束后确定第n个位置的元素。
时间复杂度：O(n*n)
void ExchangeSort(int *iData, int iSize)
{
int iTemp = 0;
for(int i=0; i<iSize-1; ++i) {
for(int j=i+1; j<iSize; ++j) {
if(iData[i] > iData[j]) {
iTemp = iData[i];
iData[i] = iData[j];
iData[j] = iTemp;
}
}
}
}
选择排序：
第n次遍历需要确定第n个位置的元素的值。
第n次遍历从第n+1个位置开始往后，遍历时记录遇到的最小元素的值和位置，一次遍历结束后，获得了当前最小元素的值与位置，将其与需要确定的位置的元素进行交换。
需要提供两个变量，记录当前遍历最小元素的值与位置。
例如：序列5 8 5 2 9， 第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是稳定排序。
时间复杂度：O(n*n)
void SelectSort(int *iData, int iSize)
{
int iTemp = 0;
int iPos = 0;
for(int i=0; i<iSize-1; ++i){
iTemp = iData[i];
iPos = i;
for(int j = i+1; j<iSize; ++j) {
if(iTemp > iData[j]) {
iTemp = iData[j];
iPos = j;
}
}
iData[iPos] = iData[i];
iData[i] = iTemp;
}
}
插入排序：
从第二个元素开始，从前往后依次判断每个元素，假设之前的元素都是已经排好序的。
针对每个判断的元素，从后往前遍历前面的已排好序的元素，根据比较结果移动以排序的元素位置，直到找到合适位置插入当前判断的元素。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，插入排序是稳定的。
时间复杂度：O(n*n)
void InsertSort(int* iData,int iSize) //O(n*n)
{
int iTemp = 0;
int iPos = 0;
for(int i=1; i<iSize; ++i) {
iPos = i-1;
iTemp = iData[i];
while((iPos>=0) && (iTemp<iData[iPos])) {
iData[iPos+1] = iData[iPos];
--iPos;
}
iData[iPos+1] = iTemp;
}
}
快速排序：
实现一：
1、取一个元素为枢纽元素。
2、分别从两边往中间遍历，交换两边元素（与枢纽元素相等的元素也需要交换），交换后指针向中间移动。
3、重复步骤2，直到左右指针交叉。
至此，右指针左边的元素都小于枢纽元素，左指针右边的元素都大于枢纽元素，递归。
时间复杂度：最坏情况为：O(n*n)，平均为：O(nlog2n)。
void Quick_Sort(int* iData, int iLeft, int iRight)
{
if(iLeft >= iRight)
return;
int iMiddle = iData[(iLeft+iRight)/2]; //取中间元素为枢纽元素
int iL = iLeft;
int iR = iRight;
while(iL <= iR) //如果iL=iR，则各自再前进一步，取[iLeft,iR]和[iL,iRight]递归
{
while(iData[iL] < iMiddle) //不能为等号，最后两个元素需要排序
++iL;
while(iData[iR] > iMiddle)
--iR;
if(iL<=iR)
{
int iTemp = iData[iL];
iData[iL] = iData[iR];
iData[iR] = iTemp;
++iL;
--iR;
}
}
Quick_Sort(iData, iLeft, iR);
Quick_Sort(iData, iL, iRight);
}
实现二：
1、取最右边元素为枢纽元素（最右边位置空出）。
2、将左边第一个大于枢纽元素的元素放到右边空出的位置（左边位置空出）。
3、将右边第一个小于枢纽元素的元素放到左边空出位置（右边位置空出）。
4、重复步骤2、3，直到左右指针交汇，将枢纽元素放到该位置。
至此，枢纽元素左右两边分别小于大于枢纽元素，对两边分别进行快速排序，递归。
例如：序列 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序不是稳定排序。
时间复杂度：最坏情况为：O(n*n)，平均为：O(nlog2n)。
//将元素分成两堆
int Partition(int* iData, int iLeft, int iRight)
{
int iMiddle = iData[iRight]; //取最右边的元素为枢纽元素
while(iLeft<iRight)
{
while((iLeft<iRight) && (iData[iLeft]<=iMiddle)) {
++iLeft;
}
iData[iRight] = iData[iLeft]; //左边大于枢纽元素的值赋给空出的右边位置
while((iRight>iLeft) && (iData[iRight]>iMiddle)) {
--iRight;
}
iData[iLeft] = iData[iRight]; //右边小于枢纽元素的值赋给空出的左边位置
}
iData[iRight] = iMiddle; //枢纽元素的值赋给左右指针交汇处
return iRight; //返回枢纽元素位置
}
void QuickSort(int* iData, int iLeft, int iRight)
{
if(iLeft < iRight) {
int iM = Partition(iData, iLeft, iRight);
//分别对枢纽元素左右两边进行快速排序
QuickSort(iData, iLeft, iM-1);
QuickSort(iData, iM+1, iRight);
}
}
堆排序：
大顶堆的定义：完全二叉树，任一非叶子结点都大于等于它的孩子，也就是说根结点是最大的。
完全二叉树可由数组实现。
1、创建大顶堆，从第n/2个节点往前一次维护大顶堆。
2、交换首尾元素，交换后，最大元素到了尾部位置。
3、针对除去尾部元素的数组，重建大顶堆，因为交换只是首元素改变了，所以左右子树依然分别是大顶堆。
4、重复步骤2、3，直至堆中只剩一个元素。
例如：序列 3 27 36 27，如果堆顶3先输出，则第三层的27（最后一个27）跑到堆顶，两个27相对顺序改变，所以堆排序不稳定。
时间复杂度：O(n*log2n)
//从ipos开始从上至下维护大顶堆
void TopHeap(int* pi, int iPos, int iLen)
{
int iChild = iPos * 2; //iPos的孩子，初始化为左孩子
while(iChild <= iLen)
{
int iMax = pi[iPos];
if(pi[iChild] > iMax)
iMax = pi[iChild];
if((iChild+1 <= iLen) && (pi[iChild+1] > iMax))
{
//若右孩子存在且值最大，则改变iMax，iChild指向最大的孩子
++iChild;
iMax = pi[iChild];
}
if(pi[iPos] != iMax)
{
//交换根与大孩子，更新iPos为大孩子，iChild指向其左孩子
swap(pi[iPos], pi[iChild]);
iPos = iChild;
iChild = iPos*2;
}
else
break;
}
}
//创建大顶堆
void BuildHeap(int* pi, int iLen)
{
//从后往前，依次维护第一个非叶子的节点
for(int i=iLen/2; i >0; --i)
{
TopHeap(pi, i, iLen);
}
}
//堆排序
void HeapSort(int* pi, int iLen)
{
//创建堆
BuildHeap(pi, iLen);
//将堆首最大元素与尾元素交换位置
//维护除去尾位置元素的集合为大顶堆，循环
while(iLen)
{
swap(pi[1], pi[iLen]);
--iLen;
TopHeap(pi, 1, iLen);
}
}
希尔排序：
和插入排序思路一样
1、先把数组分成size/2组，每组2个元素，且这两个元素相隔size/2距离，针对每组的两个元素进行插入排序。
2、把数组分成size/2/2组，每组4个元素，元素之间距离为size/2/2，针对每组的4个元素插入排序。
3、重复该步骤至把数组分成1组，插入排序。
由于这些数也越来越有序，所以排序速度也很快。
在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
时间复杂度：O(nLog2n)
void ShellSort(int* iData,int iSize)
{
int iTemp = 0;
int iPos = 0;
for(int gap= iSize/2; gap>0; gap/=2)
{
for(int i=gap; i<iSize; ++i)
{
iPos = i-gap;
iTemp = iData[i];
while((iPos>=0) && (iTemp<iData[iPos])) {
iData[iPos+gap] = iData[iPos];
iPos -= gap;
}
iData[iPos+gap] = iTemp;
}
}
}