一.数组
1.数组的概念
数组：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表：就是数据排成一条线一样的结构，每个线性表上的数据最多只有前后两个方向。数组，链表，栈，队列等
非线性表：数据之间不是简单的前后关系，如：二叉树，图，堆等
连续的内存空间和相同的数据类型：正是因为两个要求，才使数组具有随机访问的能力。
随机访问的实现：a[i]_address = base_address + i * data_type_size
计算机想要随机访问数组中的元素的时候，通过上面的寻址公式，计算出元素的内存地址。其中base_address是数组的首地址，i是元素的下标，data_type_size是元素的大小
2.数组的插入 删除
数组为了保证内存的连续性，所以插入和删除都会导致数据的搬移，导致插入，删除操作的低效性。
为了避免数据的迁移，在插入操作的时候，我们向k位置插入数据，同时将原来k位置的数据移到数组的末尾；删除操作的时候，不直接删除元素，将元素标记为删除，当数组的空间不足的时候，将所有被标记的元素的统一删除。这种操作很像jvm标记清除算法的思想。
3.数组下标越界
java本身会做下标越界检查：抛出异常。java.lang.ArrayIndexOutOfBoundsException
4.容器和数组
java将数组分装成容器;arraylist
arraylist的优点：将很多数组操作的细节分装起来，最大的优点就是支持动态扩容 1.5倍。当然动态扩容是很耗时，如果我们知道数组的大小，直接初始化的时候指定好。
arraylist不能存储基本类型，只能存储Integer，long等对象，涉及到封装与解封装，性能有所降低。
一般工作中容器已经足够使用，只有在对性能要求比较高的时候，才需要考虑使用数组。
5.数组下标为何从0开始
从上面的寻址公式中可以看出，如果下标从1开始的话，cpu每次进行寻址的时候都要进行下标 - 1的操作，对于数组这种基础的数据结构，性能要做到最优。
当然，还有很大的原因是历史缘故。
6.有序数组和无序数组的比较
1.有序数组要比无序数组在查找上更快，可以使用二分法查找
2.有序数组在插入时较慢，有序数组需要找插入的位置
3.有序数组和无序数组在删除时都比较慢，因为都需要进行补位（用后面的元素填补删除的空当）。
7.数组的复杂度分析
数组支持随机访问，随机访问的时间复杂度为O（1）
数组的删除和插入操作的时间复杂度为O（n）
二.冒泡排序
1.冒泡排序的时间复杂度O(n^2)
2.代码
1 public static void sort(int[] arr){ 2 for(int i=arr.length-1;i>0;i--){ 3 for(int j=0;j<i;j++){ 4 if(arr[j]>arr[j+1]){ 5 int temp = arr[j]; 6 arr[j] = arr[j+1]; 7 arr[j+1] = temp; 8 } 9 } 10 } 11 }
三.选择排序
1.选择排序的时间复杂度O(n^2),操作的次数要比冒泡排序少
2.代码
1 public static void sort1(int[] arr){ 2 for(int i = 0;i<arr.length-1;i++){ 3 int min = i; 4 for(int j = i+1;j<arr.length;j++){ 5 if(arr[j]<arr[min]){ 6 min = j; 7 } 8 } 9 if(i!=min){ 10 int temp = arr[min]; 11 arr[min] = arr[i]; 12 arr[i] = temp; 13 } 14 } 15 }
四.插入排序
1.插入排序的算法时间复杂度为O(n^2)
2.代码
1 public static void sort2(int[] arr){ 2 int in,temp; 3 for(int i = 1;i<arr.length;i++){ 4 temp = arr[i]; 5 in = i; 6 while(in>0 && arr[in-1]>=temp){ 7 arr[in] = arr[in-1]; 8 --in; 9 } 10 arr[in] = temp; 11 } 12 }
五.总结
1.冒泡排序是效率最低，也是最简单的。
2.选择排序虽然减少了交换的次数，但比较的次数仍然很大。
3.插入排序是三种算法中应用最多的排序，当部分有序的时候，插入排序是个好的选择。
4.这三种算法的时间复杂度都是O(n^2)。