排序API

---

1. Arrays类中的静态排序API

• **Arrays.sort(数据类型[] a)中的排序是用的是快速排序，时间复杂度是O(nlogn)

对指定的 类型数组按数字升序进行排序。不稳定

• Arrays.sort(T[],Comparator<? super T> c) 、Arrays.sort(Object[] a)

根据指定比较器产生的顺序对指定对象数组进行排序，当c=null时按自然序排列

该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n*log(n) 性能。 稳定

2. Collections静态排序API

Collections.sort(List list)、和Collections.sort(List list，Comparator<？super T> c);

使用的排序是稳定的，主要是对list排序

该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n log(n) 性能。
此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图原地对链接列表进行排序而产生的
n2 log(n) 性能。

3. ArrayList的排序API

list.sort(Comparator<? super T> c);对list排序，当c=null时，按自然序排列

---

1，对list排序，可以使用list自己的sort方法，也可以使用Collections的静态排序方法，且Collections的排序方法都是稳定的

2，Arrays的静态sort，一个是快排，一个归并排序（稳定的）

补充：常见的排序方法

分类

1. 插入排序：直接插入排序、二分法插入排序、希尔排序。
2. 选择排序：简单选择排序、堆排序。
3. 交换排序：冒泡排序、快速排序。
4. 归并排序
5. 基数排序