8.Java内置排序算法

10. Java内置算法>排序算法

算法>排序算法的分类

如何写一个通用的算法>排序算法
排序元素比较
分治算法思想

算法>排序算法选择的建议

O(n²)算法>排序算法的选择

1.插入排序性能最好、其次是选择排序，冒泡排序性能最差
2.选择排序不是稳定的算法>排序算法
3.插入排序是最好的选择
4.对于大规模的乱序数组的排序，可以使用希尔排序

O(nlogn)算法>排序算法的选择

1.快排时间复杂度最坏情况下是O(n2)，合理选择分区点
2.归并排序在任何情况下的时间复杂度都是O(nlogn)
3.归并排序的空间复杂度是O(n)，快排空间复杂度是O(nlogn)
4.但是快排不是稳定的算法>排序算法，归并排序是稳定的算法>排序算法

O(n)算法>排序算法的选择

都是对数据有要求的
1.桶排序：桶与桶之间有序、元素均匀的划分到桶中
2.计数排序：应用在数据范围不大的场景
3.基数排序：排序数据可以分割出独立的“位”而且每一位的数据范围不能太大

O(n²)算法>排序算法对比O(nlogn)算法>排序算法

在这里插入图片描述

如何写一个通用的算法>排序算法

不能选择线性时间复杂度的桶排序、计数排序、基数排序
小规模数据，可以使用O(n2)的插入排序
大规模数据，可以使用O(nlogn)的算法>排序算法

Java内置的算法>排序算法Arrays.sort(int[] data)

对于小数据量（小于47）的话使用插入排序
然后小数据量（大于47而小于286）的话使用递归实现的快速排序
对于大数据量使用迭代（自底朝上）实现的归并排序

引用类型实现Comparable可比较

基本类型数据比较：天然支持，< > <= >=
引用类型数据比较
a. java.lang.Comparable

java">//实现Comparable接口，重写compareTo方法
@Override
public int compareTo(Person o) {if(this.age<o.age){//说明当前对象比o对象小//实际上只要是返回负数就可以，不一定是-1return -1;}else if(this.age>o.age){//说明当前对象比o对象大//实际上只要是返回正数就可以，不一定是-1return 1;}//说明当前对象和o对象一样大return 0;
}//等同于
@Override
public int compareTo(Person o) {return this.age - o.age;    //升序
}

b.java.util.Comparator

java">Comparator<Person> comparator1 = new Comparator<Person>() {@Overridepublic int compare(Person o1, Person o2) {return o1.getAge()-o2.getAge();}
};
int compare1 = comparator1.compare(p1, p2);
System.out.println(compare1);

引用类型数组排序

java">package com.xiaoyi.line.algo.sort.compare;import com.xiaoyi.line.algo.sort.Sorter;import java.util.Arrays;
import java.util.Comparator;public class ThreeWayQuickSorter<E extends Comparable<E>> extends Sorter {public void sort(E[] data) {if (data == null || data.length <= 1) return;sort(data, 0, data.length - 1);}private void sort(E[] data, int lo, int hi) {if (lo >= hi) return;// 分区E pivot = data[hi];int less = lo;int great = hi;int i = lo;while (i <= great) {if (data[i].compareTo(pivot) < 0) {swap(data, i, less);less++;i++;} else if (data[i].compareTo(pivot) > 0) {swap(data, i, great);great--;} else {i++;}}sort(data, lo, less - 1);sort(data, great +1, hi);}//使用比较器比较public void sort(E[] data, Comparator<E> c) {if (data == null || data.length <= 1) return;sort(data, 0, data.length - 1, c);}private void sort(E[] data, int lo, int hi, Comparator<E> c) {if (lo >= hi) return;// 分区E pivot = data[hi];int less = lo;int great = hi;int i = lo;while (i <= great) {if (c.compare(data[i], pivot) < 0) {swap(data, i, less);less++;i++;} else if (c.compare(data[i], pivot) > 0) {swap(data, i, great);great--;} else {i++;}}sort(data, lo, less - 1, c);sort(data, great +1, hi, c);}public static void main(String[] args) {Person p1 = new Person("douma", 40);Person p2 = new Person("laotang", 30);Person p3 = new Person("douma1", 32);Person p4 = new Person("laotang2", 33);Person[] people = new Person[]{p1, p2, p3, p4};Comparator<Person> comparator = ((o1, o2) -> o2.getAge() - o1.getAge());new ThreeWayQuickSorter().sort(people, comparator);System.out.println(Arrays.toString(people));}
}

Java内置算法>排序算法

在这里插入图片描述

引用类型数组排序强调使用稳定算法>排序算法，因此不能用快排
在这里插入图片描述

java">public class JavaSorter {public static void main(String[] args) {int[] data = new int[]{12,23,36,9,24,42};Arrays.sort(data); // 通用的排序System.out.println(Arrays.toString(data));Person p1 = new Person("douma", 40);Person p2 = new Person("laotang", 30);Person p3 = new Person("douma1", 32);Person p4 = new Person("laotang2", 33);Person[] people = new Person[]{p1, p2, p3, p4};//Arrays.sort(people);Comparator<Person> comparator = ((o1, o2) -> o1.getAge() - o2.getAge());//Arrays.sort(people, comparator);// 小规模数据的话选择插入排序// 大规模数据的话选择归并排序//      (老版本使用的是递归实现的归并，而新版本使用的则不是递归实现的归并)//System.out.println(Arrays.toString(people));ArrayList<Person> list = new ArrayList<>();list.add(p1);list.add(p2);list.add(p3);list.add(p4);//动态数组排序Collections.sort(list, comparator);// 底层：Arrays.sortSystem.out.println(list);}
}