排序的稳定性：
相同数值的数字在排序前后的顺序位置不变
稳定性的优点和好处：
举个例子吧，比如我们把一个班级的学生按学号从小到大已经排序好了，现在要再按年龄段进行排序，如果排序是稳定的话，相同年龄的学生仍然是按学号从小到大排序的，不稳定的话则要重新再排序一次
排序分为比较类和非比较类：
比较类：冒泡，选择，插入，希尔，归并，堆，快排等等，复杂度通常为O(n2)或者O(nlogn)
非比较类：计数、桶、基数等等，复杂度通常可以达到O(n)，但是需要额外的空间开销
冒泡排序：相邻两两交换
优化：
①某一轮中两两均不交换，说明已排好，flag标记
②某一轮中的最后一次交换发生在index位置，这说明该位置之后是排好序的，则下一轮可以提前结束
都是减少冒泡比较次数
改进：鸡尾酒排序
与冒泡的不同之处是以双向在序列中进行排序。
选择排序：比冒泡排序更优的地方在于所需进行记录移动的操作次数较少
优化：
一次选择两个元素，一个最大放右边，一个最小放左边
堆排序：基于选择排序的改进
堆分为大根堆和小根堆，是完全二叉树或近似完全二叉树
那树又是什么呢？
形象的说，就是把自然界的树倒过来，有根，树干，叶。
完全二叉树，是二叉树的一种，所有节点都要靠左聚拢，并且除了最后一层，每一层都要满（1,2,4,8,16….）
大根堆：父节点都！比子节点大
小根堆：子节点都！比父节点小
堆排序的过程：
①建堆：核心内容是调整堆（把不是堆的完全二叉树调整成堆）
②调整堆：完成数据的非递减排序
插入排序：适合数据量较小的排序
优化：
①二分插入：传统是从后到前顺序遍历查找进行比较，为了减少比较次数，可采用二分查找
②希尔排序
希尔排序：递减增量排序，不稳定
步长选取：只要最终步长为1的任何步长序列都可以（步长<数组长度）
目前已知的最好步长序列：1,4,10,23,57,132,301,701,1750…
这样的步长序列的希尔排序比插入和堆排序都要快，甚至在小数据量排序中比快排还快
归并排序：稳定
可以用递归和非递归（迭代）实现
快速排序：二十世纪最伟大的十大算法之一
思想：
分治法，选择一个中轴点，将小于中轴点放在左边，大于中轴点的放在右边，直到序列为空或只有一个元素
优化：
①优化选取枢轴，三数取中法，来以此降低轴值选择的不好的可能性，分别在左端点，中点和右端点取样
②三路划分处理重复值
③并行处理（多线程引入）
快排为什么快？
①时间复杂度是近似得到的，忽略了系数，快排前的系数更小，性能更好
②因为快排是枢轴左边的元素都比中轴点小，右边的元素都比中轴点大，比较交换次数会比堆排少
桶排序：牺牲空间换时间
利用函数的映射关系，减少了计划所有的比较操作，可以用在海量数据处理中，是基数排序的一种归纳结果
基数排序：也可看作桶排序
对数据选择多种基数，对每一种基数使用桶排序
计数排序：限于整数排序
qsort的使用：
函数原型：
void qsort(void *base,int num,int width,int (*fcmp)(const void *a,const void *b));各参数意义：
①待排序数组首地址
②数组中待排序元素数量
③各元素的占用空间大小
④指向函数的指针，用于确定排序的顺序
int cmp(const void *a,const void *b){}的返回值大于0表示什么？
－－－
返回正数就是说cmp传入参数第一个要放在第二个后面,负数就是传入参数第一个要放第二个前面,如果是0, 那就无所谓谁前谁后多级排序：
int cmp(const void *p1,const void *p2)
{
struct Node *a=(Node*)p1;
struct Node *b=(Node*)p2;
if(a->x!=b->x)
{
return a->x - a->x;
}
else
{
return b->y - b->y;
}
} 今天的讲座讲了这么多的排序算法，鸭鸭了解了它们的基本思想和各种优化，学到了很多。至于具体的代码实现，需要进一步的思考练习。
——2017.7.24 22:09