软考-算法-排序（下）

答案

1.1 - 1.6：A D A A A B
2.1 - 2.3：C C C
3.1 - 3.8：4 2 5 1 3 3 2 1

知识点分析

《概念》
学习基础算法的好处：跨平台，不然就需要记不同语言封装的不同的排序方法，Java、js、dart、swift、go、oc、php……
代码工具：https://tool.lu/coderunner/
使用建议参考java sort：https://www.cnblogs.com/aspirant/p/10497163.html
参考菜鸟教程：https://www.runoob.com/w3cnote/sort-algorithm-summary.html

image.png
【最好情况】基本有序
【最坏情况】基本无序
【n较小】O(n) < O(n^2) < O(nlog2n)
【n较大】O(n) < O(nlog2n) < O(n^2)
【空间足够的情况】 O(d(r+n)) = O(n)
【稳定排序】相同的两个值，排序后与排序前位置保持不变。（实例：比如大屏项目后台配置商品位置策略，要求的就是稳定排序。）

《稳定排序》
【冒泡排序】BubbleSort
特点：相邻位置交换。频繁交换。
推荐场景：基本有序 n较小（平方阶(O(n2))排序）
【插入排序】InsertionSort
特点：从未排序的序列中依次取出一个元素与排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上。
推荐场景：基本有序 n较小（平方阶(O(n2))排序）
【归并排序】MergeSort
特点：归并就是将两个或两个以上的有序表组合成一个新的有序表。设三趟归并中每次归并x个有序表，则有 /x^3=1，x=3。所以选取的归并路数为3。
推荐场景：基本无序 n较大（线性对数阶(O(nlgn))排序）
【基数排序】RadixSort
特点：个位、十位、百位……依次比较入桶。位数不够补0
推荐场景：位数少，如：排序的最终结果为递增。（O(d(r+n))）

《不稳定排序》
【选择排序】SelctionSort
特点：每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放待排序序列的起始位置(或末尾位置），直到全部待排序的数据元素排完。
推荐场景：基本有序 n较小（平方阶(O(n2))排序）
【快速排序】Quicksort
特点：先从数列中取出一个数作为key值；将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；对左右两个小数列重复第二步，直至各区间只有1个数。
推荐场景：不要求稳定的情况，且位数不确定很大。则此方法是八种排序里速度最快的方法。
【希尔排序】ShellSort
特点：1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
【堆排序】HeapSort
特点：在左右子节点中寻找最小的、较大节点下移。

工作注意

【用稳定排序】工作中尽量用稳定的冒泡排序这种，减少出bug的概率

image.png