1、冒泡排序：
排序过程像是水中的气泡上升，越大的气泡升的越快，所以叫冒泡排序，从第一个数据开始，让前后相邻的数据进行比较，如果Ki>Ki+1则交换它们，每一趟排序完成一个数据，反复这个过程，直接待排序的数据为1，则结束排序。
和经典排序相比，冒泡排序对数据的有序性敏感，如果一趟排序没有发生交换，则说明所前面的数据都比它的后继数据要小，则可以立即停止，提前结束排序。
注意：如果待排序的数据基本有序，则使用冒泡排序速度最快，因为它数据的有序性敏感可以提前结束。
// 最优时间复杂度：O(N)，最差时间复杂度：O(N^2)，平均时间复杂度：O(N^2)，空间复杂度：O(1)，稳定性：稳定
void bubble_sort(int* arr,size_t len)
{
bool flag = true;
for(int i=len-1; flag&&i>0; i--)
{
flag = false;
for(int j=0; j<i; j++)
{
if(arr[j] > arr[j+1])
{
swap(arr[j],arr[j+1]);
flag = true;
}
}
}
}
2、选择排序：
从第i个待排序的数据开始，假定它是最小值，并用min记录它的下标，然后与用arr[min]与它后面的数据进行比较，如果有它还小的数据，则更新min的值，排序一趟后，如果min==i，则说明第一个数据是最小值，不需要交换，如果min!=i则交接第一个数据与arr[min]，然后i++，重复这个步骤直到待排序的数据为1（i=len-1），排序结束。
和经典排序相比，它的数据比较次数没有减少，但是它的数据交换数次大大降低(O(N-1))，节约了很多数据交换的时间，虽然时间复杂度没有变化，排序效率比经典排序提高了很多。
注意：选择排序最突出的特点是数据的交换次数最少，如果待排序的数据字节数较多，如：结构、类对象，则使用选择排序速度最快。
// 时间复杂度：O(N^2)，空间复杂度：O(1)，稳定性：不稳定
void select_sort(int* arr,size_t len)
{
for(int i=0; i<len-1; i++)
{
int min = i;
for(int j=i+1; j<len; j++)
{
if(arr[min] > arr[j])
min = j;
}
if(min != i)
swap(arr[min],arr[i]);
}
}
3、插入排序：
往有序的序列中添加新的数据，使序列继续保持有序，具体步骤是：假定新的数据存放在i=len位置，val与它前面的数据逐一进行比较val<arr[i-1]，如果前面的数据大于tmp大，则把前面数据的向后拷贝一下，然后i自减1重复以比较，直到arr[i-1]<=tmp或0==i，则位置i就是tmp应该存放的位置，新插入的数据就排序完成。
可以使用以上方法对无序序列进行排序，把序列看作两个总分，已经有序的部分（数量为1）和待插入的部分（len-1），把待插入部分的数据逐个向前面有序部分插入，就完成了对无序序列进行排序。
注意：顾名思义，插入排序算法适合往有序的序列中添加新的数据，优点是排序过程中没有进行数据交换，节约了大量时间。
// 时间复杂度：O(N^2)，空间复杂度：O(1)，稳定性：稳定
void _insert_sort(int* arr,size_t len,int val)
{
int i = len;
while(i>0 && arr[i-1]>val)
{
arr[i] = arr[i-1];
i--;
}
arr[i] = val;
}
void insert_sort(int* arr,size_t len)
{
for(int i=1; i<len; i++)
{
_insert_sort(arr,i,arr[i]);
}
}
void insert_sort(int* arr,size_t len)
{
for(int i=1; i<len; i++)
{
int tmp = arr[i], j = i;
while(j-1>=0 && arr[j-1]>tmp)
{
arr[j] = arr[j-1];
j--;
}
arr[j] = tmp;
}
}
4、希尔排序：
设计该算法的作者叫希尔，所以叫希尔排序，它在插入排序的基础上引入了增量概念(数据在插入时，每次移动的距离)，插入排序默认一次只移动一个位置，当数据量比较大时，移动的速度比较慢，希尔排序先以数量的一半为移动增量，进行插入排序，对数据进行大致排序，然后再减小增量对数据进行微调，进而完成插入排序。
注意：希尔排序适合在数量比较大的时候，向有序的序列中添加新的数据。
// 时间复杂度：O(NlogN)，空间复杂度：O(1)，稳定性：不稳定
void shell_sort(int* arr,size_t len)
{
for(int k=len/2; k>0; k/=2)
{
for(int i=k; i<len; i+=k)
{
int tmp = arr[i], j = i;
while(j-k>=0 && arr[j-k]>tmp)
{
arr[j] = arr[j-k];
j-=k;
}
arr[j] = tmp;
}
}
}
5、快速排序：
先在待排序的序列中找出一个标杆，然后与剩余的数据进行比较，比标杆小的数据放在标杆的左边，比标杆大的数据放在它右边，这样就做到以标杆为准的大致有序，然后再次同样的方法对标杆左边的数据进行排序、标杆右边的数据进行排序，直到整个序列完全有序。
注意：快速排序之所以叫快速排序，综合各种情况它的表示最好，速度最快，如果对待排序的数据不了解，建议优先选择快速排序。
// 时间复杂度：O(NlogN)，空间复杂度：O(1)，稳定性：不稳定
void _quick_sort(int* arr,int left,int right)
{
// 备份左右边界
int l = left, r = right;
// 把最右边的数据作为标杆，前记录标杆下标
int pv = arr[left], pi = left;
while(l<r)
{
// 从右向左寻找比标杆小的数据
while(l<r && arr[r]>=pv) r--;
// 找到比标杆小的数据
if(l<r)
{
// 把它移动标杆的左边
arr[pi] = arr[r];
// 记录标杆的新位置
pi = r;
}
// 从左向右寻找比标杆大的数据
while(l<r && arr[l]<=pv) l++;
// 打到比标杆大的数据
if(l<r)
{
// 把它移动到标杆的右边
arr[pi] = arr[l];
// 记录标杆的新位置
pi = l;
}
}
// 把标杆的值存放到最新位置
arr[pi] = pv;
// 快速排序标杆左边的数据
if(pi-left>1)
_quick_sort(arr,left,pi-1);
// 快速排序标杆右边的数据
if(right-pi>1)
_quick_sort(arr,pi+1,right);
}
void quick_sort(int* arr,size_t len)
{
_quick_sort(arr,0,len-1);
}
6、堆排序：
所谓堆排序就是把待排序的数据当作一个大根堆，然后逐步把堆顶的最大值弹出存储在序列的末尾，也就是借助大根堆这一数据结构完成的排序。
注意：理论上来说堆排序的速度不比快排序慢，但是对无序的序列排序需要先创建堆，时间复杂度是O(N)，然后再逐一出堆完成排序时间复杂度是O(NlogN)，所以对无序的序列排序快速排序比堆的速度要快，所以一般在实际应用中不使用堆排序，只活在教课书中。
// 时间复杂度：O(NlogN)，空间复杂度：O(1)，稳定性：不稳定
void _heap_sort(int* arr,int root,size_t len)
{
while(root*2+1<len)
{
// 假定左子树是左右子树中的最大值
int max = root*2+1;
// 判断右子树是否大于左子树，如果大于则更新最大值下标
if(max+1<len && arr[max+1]>arr[max])
max++;
// 如果最大子树依然小于根，则结束
if(arr[max] < arr[root])
return;
// 把最大子树与根交换
swap(arr[max],arr[root]);
root = max;
}
}
void heap_sort(int* arr,size_t len)
{
// 创建大根堆
for(int i=len/2-1; i>=0; i--)
_heap_sort(arr,i,len);
for(int i=len-1; i>0; i--)
{
// 把堆的根与末尾的数据交换，数量减-1
swap(arr[0],arr[i]);
// 调整堆
_heap_sort(arr,0,i);
}
printf("%s:",__func__);
}
