【算法复习4】C++ STL 中的 sort()和Java 语言中的 Collections.sort()通用的、高性能的排序函数_java中有没有像c加加里面的设置排序类似这样的函数

作者：Gausst松鼠会 | 2024-04-19 01:39:16

踩

java中有没有像c加加里面的设置排序类似这样的函数

【算法复习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

思考过程比答案重要，有答案来验证自己的思考是否准确在初学时期也很重要

思考过程比答案重要这句话是不假，但是有答案来验证自己的思考是否准确在初学时期也很重要。

学习知识每个人的理解会不同，有的人可能这么理解有的人可能那样理解。如果没有一个标杆，有些同学就会按照自己错误的理解继续学习下去。

有了标准答案，同学就可以对照答案来反思自己的理解是否正确。也能够从别人的答案中看到更好的解答也是一种学习。

当然自己偷懒不思考，依赖标准答案，那肯定是学不好的

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/449306