Java10

数组

一.数组定义
1.数组(Array)是相同数据类型的数据的有序集合。
2.数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成。其中,每一个数据称作一个数组元素(item),每个数组元素可以通过一个下标/索引来(index)访问它们.
3.数组是引用数据类型。
4.数组的三个特点
[1]数组长度是确定。数组一旦申请完空间，长度不能发生变化，用length属性访问。
[2]数组的元素都是同一数据类型。
[3]数组是有序的 。每个元素通过下标/索引标记,索引从0开始。
二.数组算法
（1）.插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O。是稳定的排序方法。直接插入排序的算法思路：
1、设置监视哨temp，将待插入记录的值赋值给temp
2、设置开始查找的位置j
3、在数组arr中进行搜索，搜索中将第j个记录后移，直至temp≥arr[j]为止；
4、将temp插入arr[j+1]的位置上

（2）冒泡排序
在一组数据中，相邻元素依次比较大小，最大的放后面，最小的冒上来。
冒泡排序算法的算法思路：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

（3）简单选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。
它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
简单选择排序的算法思路：
1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾3.以此类推，直到所有元素均排序完毕。

（4）堆排序
堆排序（英语：Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。
堆排序的算法思路：
1.最大堆调整（Max Heapify）：将堆的末端子节点作调整，某个节点的值最多和其父节点的值一样大
2.创建最大堆（Build Max Heap）：将堆中的所有数据重新排序,堆中的最大元素存放在根节点中；
3.堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。