Java基础知识

1. 冒泡排序 BubbleSort

2. 选择排序 SelectionSort

3. 插入排序 InsertionSort

4. 希尔排序 ShellSort

   • 希尔排序，其实是优化的插入排序

5. 归并排序 MergeSort

   • Java对象的排序Arrays.sort(T[] a, Comparator<? super T> c)，里面调用的是TimSort.sort()，使用的是归并排序与插入排序结合。

6. 快速排序 QuickSort

7. 计数排序 CountSort

   • 不同与前面几种基于比较的排序，该算法不基于比较

   • 适用量大但范围小并且值为整数的情况，如一万人按年龄排序

8. 基数排序 RadixSort

   • 基数排序是一种多关键字排序，对于每个关键字，使用计数排序

9. 桶排序 BucketSort

   • 两个特例：计数排序、基数排序

10. 堆排序 HeapSort

1. 三种简单排序法：冒泡、选择、插入
   • 相同点：平均时间复杂度都是O(n^2)
   • 不同点：冒泡最慢，交换的次数是O(n^2)；选择交换次数是O(n)，但是不稳定；插入在基本有序的时候效率高，最好时间复杂度是O(n)，且是稳定的。
   • 这三种排序法中，插入排序相对较优，特别是样本量小且基本有序的时候效率高

1. ArrayList、HashMap、StringBuilder扩容

   集合	初始容量	扩容因子	扩容倍数
   ArrayList	10	1	1.5
   HashMap	16	0.75	2
   StringBuilder	16	1	length * 2 + 2