排序
Arrays.sort()方法, 对于基本数据类型采用 DualPivotQuicksort(多路快排)进行排序, 对于引用类型的数组, 采用 MergeSort(归并排序)进行排序, 下面我们分别来讲一下这两类排序算法.
对基本类型数组的排序
Java 中的八种基本数据类型, 除了 boolean, 其它七种都是可以且有需求进行排序的, 如果一个数组是单一的基础类型, 形如 int[] data, long data[]都可以直接使用 Arrays.sort()进行排序. 对于所有可排序的基本类型, 都是采用 DualPivotQuicksort 来进行排序的. 首先来看个例子:
- package com.adam.java.algo.arrays;
- import java.util.Arrays;
- import org.junit.Test;
- public class ArraysBasicTest {
- @Test
- public void testSortInteger() {
- int data[] = {
- 10, 8, 9, 1, 2, 5, 98, 3, 7, 66
- };
- Arrays.sort(data);
- for (int i : data) {
- System.out.print(i + " ");
- }
- }
- @Test
- public void testSortChar() {
- char data[] = {
- 'D', 'B', 'E', 'C', 'H', 'A', 'Y', 'G', 'I', 'O'
- };
- Arrays.sort(data);
- for (char i : data) {
- System.out.print(i + " ");
- }
- }
- }
输出:
- 1 2 3 5 7 8 9 10 66 98
- A B C D E G H I O Y
这里我们要看一下 Arrays.sort()采用的算法了, 我们查看下 JDK 源码.
- /**
- Sorts the specified array into ascending numerical order.
- <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
- by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
- offers O(n log(n)) performance on many data sets that cause other
- quicksorts to degrade to quadratic performance, and is typically
- faster than traditional (one-pivot) Quicksort implementations.
- @param a the array to be sorted
- */
- public static void sort(int[] a) {
- DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
- }
发现所有的基本排序都是直接使用 DualPivotQuicksort.sort()进行的, 因此, 我们有必要了解一下 DualPivotQuicksort 的原理. 基本思想就是:
元素个数从 1-47, 则直接使用插入排序进行排序.
元素个数从 47-286, 则使用多路快速排序.
元素个数大于 286, 则使用归并排序
这里我们研究下多路快排的原理, 首先我们回顾一下经典快排是怎么实现的.
经典快排实现思路:
找一个中轴, 一般情况选取数组的第一个元素.
定义两个指针, 分别指向最左边和最右边, 从右边开始遍历, 如果大于中轴, 则右边指针左移一位, 如果小于中轴, 则互换位置; 同理再从左边开始和中轴比较, 如果小于中轴, 指针向右移动, 如果大于中轴, 则互换位置.
一趟排序下来, 中轴左边的都小于中轴, 右边的都大于中轴.
4. 递归的对子数组进行如上操作, 不稳定, 时间复杂度最优情况 O(nlogn), 最坏情况为基本有序时为 O(n2). 关于快排的详细说明, 请参考另一篇博文.
多路快排实现思路:
选取两个中轴 P1, P2.
假设 P1<P2, 否则交换.
过程中原数组会分为四个部分: 小于中轴 1, 大于中轴 2, 介于两个中轴之间, 未排序部分(刚开始除了两个中轴, 其它元素都属于这部分).
开始后, 从未排序部分选取一个数, 和两个中轴作比较, 然后放到合适的位置, 一直到未排序部分无数据, 结束一趟排序.
递归地处理子数组, 稳定排序, 时间复杂度稳定为 O(nlogn).
对引用类型的数组排序
我们举个例子, 对 User 类型的数组, 根据年龄进行排序, 此处用到 Comparator 接口, 更多关于 Comparator 的介绍, 请点击.
新建一个 User 类:
- package com.adam.java.algo.arrays;
- public class User {
- private String name;
- private String gender;
- private int age;
- public User(String name, String gender, int age) {
- this.name = name;
- this.gender = gender;
- this.age = age;
- }
- /**
- @return the name
- */
- public String getName() {
- return name;
- }
- /**
- @param name
- the name to set
- */
- public void setName(String name) {
- this.name = name;
- }
- /**
- @return the gender
- */
- public String getGender() {
- return gender;
- }
- /**
- @param gender
- the gender to set
- */
- public void setGender(String gender) {
- this.gender = gender;
- }
- /**
- @return the age
- */
- public int getAge() {
- return age;
- }
- /**
- @param age
- the age to set
- */
- public void setAge(int age) {
- this.age = age;
- }
- }
再建一个排序类:
- package com.adam.java.algo.arrays;
- import java.util.Comparator;
- public class UserComparator implements Comparator<User> {
- @Override
- public int compare(User o1, User o2) {
- return o1.getAge() - o2.getAge();
- }
- }
测试:
- package com.adam.java.algo.arrays;
- import java.util.Arrays;
- public class ArraysTest {
- public static void main(String[] args) {
- User[] users = new User[]{
- new User("egg", "male", 26), new User("Kity", "Female", 25), new User("Pole", "male", 23), new User("Jack", "male", 28)
- };
- Arrays.sort(users, new UserComparator());
- for (User user : users) {
- System.out.println("name:" + user.getName() + ",age:"+user.getAge());
- }
- }
- }
输出:
- name: Pole ,age: 23
- name: Kity ,age: 25
- name: egg ,age: 26
- name: Jack ,age: 28
这就是一个简单的对引用类型的数组排序的例子, 在 JDK1.8 中, 对引用类型的排序, 采用的归并排序的算法.
在 JDK1.8 中, 对于排序方法, 还引入了 parallelSort(), 每个 sort()都有对应的并行排序方法, 当数组元素个数大于 2 的 13 次 (8196) 后采用 parallelSort().
搜索
在用二分搜索对一个已经有序的数组进行查找, 如果存在, 返回 key 在该数组中的位置, 如果不存在, 返回负数, 值为:- 插入点 - 1, 举个例子:
假设一个排好序的数组是: 1,6,8,10,12, 如果 key 为 7, 则返回值为 - 3, 因为 7 应该插入到 6,8 之间, 所以插入点为 2(下标从 0 开始), 所以返回值为 - 2-1=-3.
ArrayToList
这方面, 是将一个数组, 转换成一个 list 形式, 注意: 通常情况下, 如果该数组是 int 型的, 如 int[[ data, 这种情况会出现并不是直接将该数组中的所有元素转成新的 list 的所有元素, 而是将整个数组, 转成 list 的一个元素, 这是一种特殊情况, 将类型 int 改成 Integer 就可以避免了. 此处感谢网友 @Java 我人生指正!
- /**
- Returns a fixed-size list backed by the specified array. (Changes to
- the returned list "write through" to the array.) This method acts
- as bridge between array-based and collection-based APIs, in
- combination with {
- @link Collection#toArray
- }. The returned list is
- serializable and implements {
- @link RandomAccess
- }.
- <p>This method also provides a convenient way to create a fixed-size
- list initialized to contain several elements:
- <pre>
- List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
- </pre>
- @param <T> the class of the objects in the array
- @param a the array by which the list will be backed
- @return a list view of the specified array
- */
- @SafeVarargs
- @SuppressWarnings("varargs")
- public static <T> List<T> asList(T... a) {
- return new ArrayList<>(a);
- }
根据注释得知, 返回的新 list 是个定长的 list, 而且并不可以就行添加或者删除元素, 否则报: java.lang.UnsupportedOperationException 异常. 这是为什么? 因为此处的 ArrayList 并非我们常用的 java.util.ArrayList 类, 而是 Arrays 类的一个内部类, 因为继承了 AbstractList, 所有可以和 list 相互转换, 但是不具备 add 和 remove 等操作.
CopyOf
Arrays.copyOf()用来进行数组的复制, 返回一个全新的数组, 可以传入一个参数来定义新数组的大小, 如果传入的数小于原来的数组长度, 则直接把原数组多余的部分剪掉, 如果传入的值大于原数组, 则新数组多余的部分补默认值(对于 int 类型的, 补 0).
来源: http://www.bubuko.com/infodetail-2991719.html