一.交换类
冒泡排序：
void BubbleSort(int*src, int n)//冒泡
{
int i, j, flag = 0;
for (i = 0; i < n-1; i++)//最后一次不需要，因为出最后最后只剩一个元素待排
{
flag = 0;
for (j = 0; j < n - i - 1; j++)
{
if (src[j] > src[j + 1])
{
int tmp = src[j];
src[j] = src[j + 1];
src[j + 1] = tmp;
flag = 1;
}
}
if (0 == flag)
{
break;
}
}
}
冒泡排序类似于海浪，一波一拨，每次将无序中的最值冒到最边上，一趟一趟重复进行。
选择排序：
void SelectSort(int* src, int n)//选择排序
{
int i, j;
int min;//始终标记接下来遍历中最小的数据下标
for (i = 0; i < n-1; i++)
{
min = i;
for (j = i; j < n; j++)
{
if (src[min] > src[j])
{
min = j;
}
}
if (min != i)
{
int tmp = src[i];
src[i] = src[min];
src[min] = tmp;
}
}
}
该算法是从头开始不断遍历后面的未排序列，找到最值，并与本节点交换，每次得到未排序列的最值
二.插入排序类
直接插入排序：
void InsertSort(int*src, int n)//插入排序
{
int i, j;
for (i = 1; i < n; i++)
{
int tmp = src[i];
if (src[i - 1] > tmp)//前面已经有序，如果当i-1小于等于tmp，则说明前面所有数据均小于等于tmp，故不用找位置插入
{
for (j = i; j > 0 && src[j - 1]> tmp; j--)//j前面数据已经有序，只需要找到第一个比tmp小的数据，插在它之后
{
src[j] = src[j - 1];
}
src[j] = tmp;
}
}
}
直接插入排序是从第二个元素为基准点，然后在前面已经有序的数列中寻找合适的位置插入，若没有合适位置就保持不动，基准点后移。图解：
注意：
- 当数据规模越小，直接插入排序越优
- 当数组越接近于有序，该排序算法越快
希尔排序：
void ShellSort(int* src, int n)//希尔排序:分组插排
{
int gap = n / 2;
int i, j;
for (gap=n /2; gap >= 1; gap /= 2)//gap为每次分的组数
{
for (i = gap; i < n; i++)
{
int tmp = src[i];
for (j = i; j - gap >= 0 && src[j -gap] > tmp; j -= gap)
{
src[j] = src[j-gap];
}
src[j] = tmp;
}
}
}
希尔排序是直接插入排序进阶版本，它先将数据分组插排，使得数组趋于有序化，当分得组内个数特别小时，数组排序完成。图解
三.选择排序类
堆排序：
//向下调整算法，将下标为i的节点向下调整
void adjustDown(int* arr, int size, int n)//n为下标c
{
int cur = n;
while ((cur + 1) * 2 <= size)//只要有左孩子存在就要进入循环
{
if ((cur + 1) * 2 + 1 > size)
{
n = cur * 2 + 1;//没有右孩子，左孩子为孩子节点的最大值
}
else
{
if (arr[cur * 2 + 1] > arr[cur * 2 + 2])//找出右节点和左节点中的较大节点，并用n标记
{
n = cur * 2 + 1;
}
else
{
n = cur * 2 + 2;
}
}
if (arr[cur] < arr[n])//当左右孩子节点大于该节点时，向下调整该节点，否则，就已经形成大顶根，不再继续循环
{
int tmp = arr[cur];
arr[cur] = arr[n];
arr[n] = tmp;
cur = n;//每次交换完之后将cur更新到n下标,使后面继续向下调整
}
else
{
break;//孩子节点均小于根节点，已经构成大顶堆
}
}
}
void HeapSort(int* src, int n)
{
int i = n / 2 + 1;
//int j ;
for (i = n / 2-1; i >= 0; i--)
{
adjustDown(src, n, i); //构成大顶堆
}
//每次将堆中最大的元素（对顶）换下来放在最后，然后再调整一个大的上去，重复
for (i = n - 1; i > 0; i--)
{
SwapArgs(src + i, src);
adjustDown(src, --n, 0);//每次对交换后的节点向下调整，n--
}
}
主要借助向下调整算法构造大根堆，再不断将最大元素出堆，得到排序。图助理解：
四.分治类排序
归并排序：
void Merging(int* src,int* tmp,int start,int end)
{
if (start >= end)
{
return;
}
int mid = start + (end - start) / 2;
int i = start, j = mid+1;
int k = start;
Merging(src, tmp, start, mid );
Merging(src,tmp,mid+1,end);
while (i<=mid && j<=end)
{
if (src[i] < src[j])
{
tmp[k] = src[i];
i++;
k++;
}
else
{
tmp[k] = src[j];
k++;
j++;
}
}
while (i <= mid)
{
tmp[k] = src[i];
i++;
k++;
}
while (j <= end)
{
tmp[k] = src[j];
k++;
j++;
}
for (i = start; i <= end; i++)//将合并好的数据回执到src内
//这里end最后的下标，start是第一个下标，下标范围易错
{
src[i] = tmp[i];
}
}
void MergeSort(int* src, int n)//归并排序
{
int* tmp = (int*)malloc(sizeof(int)*n);
Merging(src, tmp, 0, n-1);
free(tmp);
}
归并思路类似与树的后序遍历，先调整左右，再有序归并在一起。相比于其他排序有一定的空间牺牲。
快速排序：
int PointerWay(int* src, int start, int end)
{
int point = src[start];
while (start<end)
{
while (start< end && src[end] >= point)
{
end--;
}
SwapArgs(&src[start], &src[end]);
while ( start<end && src[start] <= point)
{
start++;
}
SwapArgs(&src[start], &src[end]);
}
return start;
}
void Quicking(int*src, int start, int end)
{
int mid;//作为基准点
if (start < end)//满足条件，快速排序递归调用
{
mid = PointerWay(src,start,end);
Quicking(src, start, mid-1);
Quicking(src, mid + 1, end);
}
}
void QuickSort(int* src, int n)//快速排序
{
Quicking(src,0, n-1);
}
快速排序基础实现如上将第一个作为基准值，后续比较，将比基准值小的放在一侧，比基准值大的放在另一侧，再缩小排序范围将左右已同样方法排序。
最后说一个细节，对于插入排序，有的地方说不稳定，有地方说稳定，我通过简短的学习认为选择排序的是否稳定与实现方法有关。例如上面的实现就是稳定的，而如果将第六行和第八行代码中的src[i - 1] > tmp改为src[i - 1] >= tmp之后，稳定性就不一定了！