1 基本概念
排序是处理数据的一种最常见的操作,所谓排序就是将数据按某字段规律排列,所谓的字段就是数据节点的其中一个属性。比如一个班级的学生,其字段就有学号、姓名、班级、分数等等,我们既可以针对学号排序,也可以针对分数排序。
稳定性 在一组无序数据中,若两个待排序字段一致的数据,在排序前后相对位置不变,则称排序算法是稳定的,否则是不稳定的。(应该是原先有序的在排序中会不会出现改变)
内排序与外排序 如果待排序数据量不大,可以一次性全部装进内存进行处理,则称为内排序,若数据量大到无法一次性全部装进内存,而需要将数据暂存外存,分批次读入内存进行处理,则称为外排序。
2 选择排序
遍历两层,复杂度较高
3 插入排序
减少队列和构建新的队列,新的队列插入算法可以优化。
4 希尔排序
插入排序的升级版,一开始分成几组,每组内部排序,逐步减少分组数量。
5 冒泡排序
复杂度比选择排序好一些
6 快速排序
几个做法:
两端往中间走:在l>k>r时交换;
挖坑移树法:也是两端往中间走,将Key位腾出来,存放L和R碰到的大和小的数据,
前后指针(交换小的在前):如图,重点讲,是前面两种做法的进化版,目前也是用的比较多的。
思路:
大原则(跟前面一样):用一个Key来分割所有数据成为“<K<”,然后继续前后分别递归继续;
分割时:用一个cur游标,从头找到尾,找出小的数据放到“后面队列”,用一个Prev(后面队列的车头)来推动大的数据将cur发现的小数交换到后面。