【算法复习4】C++ STL 中的 sort()和Java 语言中的 Collections.sort()通用的、高性能的排序函数
【算法复习4】C++ STL 中的 sort()和Java 语言中的 Collections.sort()通用的、高性能的排序函数
【算法复习4】C++ STL 中的 sort（）和Java 语言中的 Collections.sort（）通用的、高性能的排序函数
经典排序算法
首选时间复杂度是 O(nlogn)
堆排序和快速排序都有比较多的应用，
- Java 语言采用堆排序实现排序函数
- C 语言使用快速排序实现排序函数
问题是 快速排序 解决 复杂度恶化
补充八大排序
快排优化
1. 三数取中法
2. 随机法
快排避免堆栈溢出
为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。
评论区大佬的笔记
Arrays.sort
查看了下Arrays.sort的源码，主要采用TimSort算法, 大致思路是这样的： 1 元素个数 < 32, 采用二分查找插入排序(Binary Sort) 2 元素个数 >= 32, 采用归并排序，归并的核心是分区(Run) 3 找连续升或降的序列作为分区，分区最终被调整为升序后压入栈 4 如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阙值 5 每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并 6 最终栈内的分区被全部合并，得到一个排序好的数组
Timsort
Timsort的合并算法非常巧妙： 1 找出左分区最后一个元素(最大)及在右分区的位置 2 找出右分区第一个元素(最小)及在左分区的位置 3 仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的
谷歌V8 QuickSort排序
Google v8中对QuickSort的实现是: 数据规模在10以内的话使用快排; 数据规模在10到1000之间时选择中点作为pivot进行快排; 数据规模在1000以上时，每隔200到215个数选一个数，将选出来的数排序，选择中间值作为pivot进行快排； 而且还有几个细节： 1是折半的时候用的是位运算； 2是每一次遍历都会分成小于pivot，等于pivot，大于pivot的三个区间； 3是小于pivot和大于pivot这两个区间中数据规模比较小的会递归执行QuickSort，数据规模大的会先通过while循环减小数据规模。 附上源码链接: https://github.com/v8/v8/blob/master/src/js/array.js
思考过程比答案重要，有答案来验证自己的思考是否准确在初学时期也很重要
思考过程比答案重要这句话是不假，但是有答案来验证自己的思考是否准确在初学时期也很重要。 学习知识每个人的理解会不同，有的人可能这么理解有的人可能那样理解。如果没有一个标杆，有些同学就会按照自己错误的理解继续学习下去。 有了标准答案，同学就可以对照答案来反思自己的理解是否正确。也能够从别人的答案中看到更好的解答也是一种学习。 当然自己偷懒不思考，依赖标准答案，那肯定是学不好的