6.22面试问题【1】长链表排序选择归并还是快排
先问快排和归并的思路？
- 快速排序
快速排序的基本思想是通过一个划分操作，将待排序的数组分为两个部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再递归地对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤如下：
选择基准值（Pivot）：从数组中选择一个元素作为基准值，选择方法有多种，如选择第一个元素、最后一个元素、中位数等。
分区操作（Partitioning）：重新排列数组，比基准值小的元素放在基准值的前面，比基准值大的元素放在基准值的后面。分区结束后，基准值所处的位置就是其最终排序后的位置。
递归排序：递归地将基准值前后的两部分数组进行排序。
快速排序的平均时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。 - 归并排序
归并排序的基本思想是将待排序的数组分成若干个子序列，先让每个子序列有序，再让子序列段间有序。归并排序采用了经典的分治策略，分为“分”和“治”两个过程。
步骤如下：
分：将数组从中间分成前后两部分，然后递归地对这两部分分别进行归并排序。
治：将两个排序好的子序列合并成一个最终的排序序列。
归并过程需要额外的空间来合并两个有序数组，这是归并排序的一个特点。
归并排序的时间复杂度始终为O(n log n)，它比快速排序的最坏情况要好，但是由于其需要额外的存储空间，空间复杂度为O(n)。
链表适合归并排序而不是快速排序的原因主要有以下几点：
内存访问模式：快速排序的效率主要来源于引用的局部性，计算机硬件在这里得到了优化，因此访问彼此相邻的内存位置往往比访问分散在内存中的内存位置更快。然而，链表单元格经常分散在内存中，所以访问相邻的链表单元格没有局部性的好处。因此，快速排序的一个大的性能优势在链表排序中就被削弱了。
空间复杂度：快速排序是原地排序，不需要创建任何辅助数组来保存临时值。这在数组排序中是一个巨大的优势，因为分配和释放辅助数组所需的时间是显而易见的。然而，对于链表来说，归并排序的链表算法并不需要任何额外的辅助存储空间。
排序效率：归并排序往往更快，因为它更平均地将列表一分为二，并且在每次迭代中进行归并比执行分区步骤所做的工作更少。
参考：点击
我不太理解为什么快排依赖局部性原理，我更偏向于的解答：
快速排序和归并排序的操作特性不同：
快速排序：快速排序涉及大量的元素交换（如果是数组）和需要随机访问元素以进行分区操作。在链表上执行这些操作相对低效，因为每次访问或找到一个特定的节点都需要从头开始遍历链表。
归并排序：归并排序主要是分治和合并操作，这些操作对链表来说非常自然和高效。分治操作通过递归将链表分成两半，不需要额外空间；合并两个有序链表也非常高效，只需要调整节点的指针。归并排序不需要随机访问链表节点，这使得它在链表上的实现比快速排序更为适合。
这题有待商榷。
链表两种排序代码
数组两种排序代码