常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
数组概念
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。这里我们要抽取出三个跟数组相关的关键词：线性表，连续内存空间，相同数据类型；数组具有连续的内存空间，存储相同类型的数据，正是该特性使得数组具有一个特性：随机访问。但是有利有弊，这个特性虽然使得访问数组边得非常容易，但是也使得数组插入和删除操作会变得很低效，插入和删除数据后为了保证连续性,要做很多数据搬迁工作。
查找数组中的方法有两种：
线性查找：线性查找就是简单的查找数组中的元素
二分法查找：二分法查找要求目标数组必须是有序的。
无序数组
实现类：
public class MyArray { //声明一个数组 private long[] arr; //有效数据的长度 private int elements; //无参构造函数，默认长度为50 public MyArray(){ arr = new long[50]; } public MyArray(int maxsize){ arr = new long[maxsize]; } //添加数据 public void insert(long value){ arr[elements] = value; elements++; } //显示数据 public void display(){ System.out.print("["); for(int i = 0;i < elements;i++){ System.out.print(arr[i] + " "); } System.out.println("]"); } //根据下标查找数据 public long get(int index){ if(index >= elements || index < 0){ throw new ArrayIndexOutOfBoundsException(); }else{ return arr[index]; } } /** * 根据值查询 * @param value 需要被查询的值 * @return 被查询值的下标 */ public int search(int value){ //声明一个变量i用来记录该数据的下标值 int i ; for(i = 0;i < elements;i++){ if(value == arr[i]){ break; } } //如果查询到最后一个元素依然没有找到 if(i == elements){ return -1; }else{ return i; } } //根据下标删除数据 public void delete(int index){ if(index >= elements || index < 0){ throw new ArrayIndexOutOfBoundsException(); }else{ //删除该元素后，后面所有元素前移一位 for(int i = index; i < elements;i++){ arr[i] = arr[i+1]; } elements--; } } /** * 替换数据 * @param index 被替换的下标 * @param newvalue 新的数据 */ public void change(int index,int newvalue){ if(index >= elements || index < 0){ throw new ArrayIndexOutOfBoundsException(); }else{ arr[index] = newvalue; } } }
优点：插入快（时间复杂度为：O(1)）、如果知道下标，可以很快存储
缺点：查询慢（时间复杂度为：O(n)）、删除慢
有序数组
实现类：
public class MyOrderArray { private long[] arr; private int elements; public MyOrderArray(){ arr = new long[50]; } public MyOrderArray(int maxsize){ arr = new long[maxsize]; } //添加数据 public void insert(int value){ int i; for(i = 0;i < elements;i++){ if(arr[i] > value){ break; } } for(int j = elements;j > i;j--){ arr[j] = arr[j -1]; } arr[i] = value; elements++; } //删除数据 public void delete(int index){ if(index >=elements || index <0){ throw new ArrayIndexOutOfBoundsException(); }else{ for(int i = index;i < elements; i++){ arr[i] = arr[i+1]; } elements--; } } //修改数据 public void change(int index,int value){ if(index >= elements || index < 0){ throw new IndexOutOfBoundsException(); }else{ arr[index] = value; } } //根据下标查询数据 public long get(int index){ if(index >= elements || index < 0){ throw new IndexOutOfBoundsException(); }else{ return arr[index]; } } //展示数据 public void display(){ System.out.print("["); for(int i = 0; i < elements;i++){ System.out.print(arr[i] + " "); } System.out.println("]"); } //二分法查找数据 public int binarySearch(long value){ //声明三个指针分别指向数组的头，尾，中间 int low = 0; int pow = elements; int middle = 0; while(true){ middle = (low + pow) / 2; //如果中指针所指的值等于带查询数 if(arr[middle] == value){ return middle; }else if(low > pow){ return -1; }else{ if(arr[middle] > value){ //待查询的数在左边,右指针重新改变指向 pow = middle-1; }else{ //带查询的数在右边，左指针重新改变指向 low = middle +1; } } } } }
优点：查询快（时间复杂度为：O(logn)）
缺点：增删慢（时间复杂度为：O(n)）
