努力努力再努力xLg
前言
数组在Java中算是耳熟能详的了。但是在数据结构方面，它是一个非常基础，并且非常有意义的数据结构，接下来我们将一步一步，从易到难的研究所有在Java中运用到的数据结构，所带来的便利、和魅力。
不要小瞧了数组
在Java中提供的数组属于静态数组。不可动态扩容，在初始化时，需要指定大小或者容积。今天基于Java的静态数组，来实现一组动态数组。体会一下，不容小觑的数组-数据结构。
众所周知，在数组中，最大的一个特性就是在每一个元素下，都有属于自己的索引。
那么索引，在数组中，可以是有语义的，也可以没有语义；
有语义：可以用数组的索引代表排名。这样就体现得更加直观。
那么索引给数组带来了那些好处呢？
根据索引，查找数据非常快，时间复杂度为（O（1）级别）。但是在增删操作中，就显得力不从心了，因为在增删操作中需要额外的维护原有的数组的索引，并且需要维护数组的大小。在这里考虑到极端情况下，需要扩容。时间复杂度则为O（n）。
代码逻辑
package ch1_array.ch1;
import java.util.Objects;
/**
* 不要小瞧数组
* 自定义，动态数组
*
* @author by Mr. Li
* @date 2019/12/31 1:07
*/
public class MyArray<E> {
/**
* 初始容量 data
*/
private E[] data;
/**
* 当前数组中含有多少元素
*/
private int size;
/**
* 构造函数：定义一个capacity大小的数组
*
* @param capacity 默认数组的容量
*/
public MyArray(int capacity) {
data = (E[]) new Objects[capacity];
size = 0;
}
/**
* 无参构造：定义一个默认容量为8 的数组
*/
public MyArray() {
this(8);
}
/**
* 获取 数组元素大小
*
* @return 元素大小
*/
public int getSize() {
return size;
}
/**
* 判断是否为空
*
* @return 是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获取数组的容量
*
* @return Capacity
*/
public int getCapacity() {
return data.length;
}
/**
* 查看数组中是否包含该元素
*
* @param e
* @return
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (e == data[i]) {
return true;
}
}
return false;
}
/**
* 在数组中查找某个元素
*
* @param e 需要查找的元素
* @return 返回该元素的索引位置，如果没有则返回-1
*/
public int find(E e) {
for (int i = 0; i < size; i--) {
if (data[i] == e) {
return i;
}
}
return -1;
}
/**
* 修改 某索引的元素
*
* @param index
* @param e
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed.index should is index < 0 || index >= size");
}
data[index] = e;
}
/**
* 根据索引 获取元素
*
* @param index 索引
* @return 该元素
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed.index should is index < 0 || index >= size");
}
return data[index];
}
public void add(E e) {
add(size, e);
}
public E getLast() {
return get(size - 1);
}
public E getFirst() {
return get(0);
}
/**
* 删除某个某个索引上的元素
*
* @param index 指定的索引
* @return 返回被删除的元素
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed.index should is index < 0 || index >= size");
}
E res = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
// 考虑到内存优化问题，当数组内元素减少到一定程度时。进行缩容。
// 并且考虑到时间复杂度，最坏的情况下，如果在2倍的零界点一直做addLast和removeLast操作会使
// 两个时间复杂度为O(1)级别的操作变成了O(n)。
// 所以考虑到上述问题，在缩容时，我们要考虑到，容量确实没有必要那么大的时候，再进行缩容。
if (size <= getCapacity() / 4 && getCapacity() / 4 >= 8) {
// 当当前元素小于容积的4分之一时，进行缩容,但是容易不可以为0，所以这里控制最小容量为8
resize(getCapacity() / 2);
}
// 优化代码，将该位置指向空白地址，供垃圾回收机制回收。
data[size] = null;
return res;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
/**
* 移除某个元素
*
* @param e
*/
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
/**
* 添加元素
*
* @param index 添加元素的 索引位置
* @param e 添加的具体元素
*/
public void add(int index, E e) {
// 判断index 是否超过当前容量
// if (size == getCapacity()) {
// throw new IllegalArgumentException("Add failed. Array is full.");
// }
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Require index >=0 || index <= size");
}
// 使用动态扩容的技术，实现动态数组
if (size == getCapacity()) {
resize(getCapacity() * 2);
}
// 将添加的元素，添加到数组中，应该从后往前，遍历到需要插入的索引位置，并且遍历到的元素，都需要往后移一个位置
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
// 将新元素插入到数组中
data[index] = e;
// 维护 数组大小
size++;
}
/**
* 在最后索引处 添加元素
*
* @param e 新元素
*/
public void addLast(E e) {
add(size, e);
}
/**
* 在数组的头添加元素
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i != size - 1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
/**
* 实现动态数组，扩容！
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Objects[newCapacity];
// 复制数组中的元素到新的数组中
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
所有的代码逻辑都非常清楚的写在代码注解中。
动态数组
这里需要特别重点的说一下扩容与缩容，在动态数组中的重要地位。
在上述代码中我们看到add操作为在容量不足时，将数组容量扩容到当前容量的两倍。
我们来假设一种非常极端的情况。
在对数组进行操作时，如果刚好处在扩容的最后一个元素，在进行addLast操作，需要进行扩容，与此同时，在缩容时，也是在当前size时容积的一半时，进行缩容，那么问题就来了，就在刚刚做了扩容的时候，再删除一个元素，马上又要进行缩容，如此反复，时间复杂度成质数倍增长。可想而知带来的性能消耗有多大。所以这样的操作对于JVM来说太过于激进。
所以这里需要对缩容采取Lazy的方式，当程序发现确实有很大一部分空间被浪费时，再进行缩容，就如上述代码中，当Size为容积的1/4时再进行缩容为容积的1/2。这样程序就现得更加的合理，和健壮了。
使用数组实现各种排序
冒泡排序
比较相邻的两个元素，按需将大/或者小（升降序决定）往后移。一个一个遍历如下图
冒泡排序.gif
代码：
public static int[] arr = {55, 4, 7, 56, 89, 21, 2, 3, 0};
@Test
public void test_1() {
// 冒泡排序
int temp;
// 升序
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) { // 在这里升序降序改一下大于 小于就可以了
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
Arrays.stream(arr).forEach(System.out::println);
}
选择排序
将数组中所有元素一一对比，每一次遍历选出所有为遍历中的之最。则为选择排序
选择排序.gif
@Test
public void test_2() {
int temp;
int index;
for (int i = 0; i < arr.length; i++) {
index = i;
temp = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (temp > arr[j]) {
temp = arr[j];
// 记录最小的值的索引。
index = j;
}
}
arr[index] = arr[i];
arr[i] = temp;
}
Arrays.stream(arr).forEach(System.out::println);
}
插入排序
通常将第一个元素作为参考值，从第二个元素开始和这个参考值进行比较，比这个参考值大的时候放在这个参考值的后面，比这个参考值小的时候在和这个参考值的前一位进行比较，当比较至适当位置进行插入。
插入排序.gif
@Test
public void test_3() {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i + 1] < arr[i]) {
for (int j = i + 1; j > 0; j--) {
if (arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
Arrays.stream(arr).forEach(System.out::println);
}
归并排序
归并排序利用的是分治的思想实现的，对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的子序列，之后对子序列排序，最后再用递归方法将排好序的子序列合并成为有序序列。合并两个子序列时，需要申请两个子序列加起来长度的内存，临时存储新的生成序列，再将新生成的序列赋值到原数组相应的位置。
归并排序.gif
这里录制的
GIF有问题，看后面加速的则是归并排序
/**
* 归并排序
*/
@Test
public void test_4() {
merSort(arr, 0, arr.length - 1);
Arrays.stream(arr).forEach(System.out::println);
}
public static void merSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merSort(arr, left, mid);//左边归并排序，使得左子序列有序
merSort(arr, mid + 1, right);//右边归并排序，使得右子序列有序
merge(arr, left, mid, right);//合并两个子序列
}
}
private static void merge(int[] arr, int left, int mid, int right) {
//也可以从开始就申请一个与原数组大小相同的数组，因为重复new数组会频繁申请内存
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {//将左边剩余元素填充进temp中
temp[k++] = arr[i++];
}
while (j <= right) {//将右序列剩余元素填充进temp中
temp[k++] = arr[j++];
}
//将temp中的元素全部拷贝到原数组中
for (int k2 = 0; k2 < temp.length; k2++) {
arr[k2 + left] = temp[k2];
}
}
快速排序
//TODO
参考书籍
本文仅供本人学习，一起进步！
网友评论