基础知识
什么是算法
算法指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
算法的5个基本特征
正确性，有穷性，确定性，输入，输出
- 正确性：能按设计要求解决具体问题，并得到正确的结果。
- 有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。
- 确定性：算法中每条指令的含义必须明确，不允许由二义性
- 可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。
- 输入：一个算法的输入可以包含零个或多个数据。
- 输出：算法有一个或多个输出
评价算法好坏的标准有哪些
- 正确:算法应能满足设定的功能和要求 。
- 可读:思路清晰、层次分明、易读易懂 。
- 健壮：输入非法数据时应能作适当的反应和处理。
- 高效(时间复杂度)：解决问题时间越短，算法的效率就越高。
- 低存储量(空间复杂度):完成同一功能，占用存储空间应尽可能少。
数据的逻辑结构（线性结构与非线性结构）和存储结构有哪些
顺序存储结构；链式存储结构；索引存储结构；散列式存储结构
什么是线性表，有什么特点
是一种可以在任意位置进行插入删除数据元素操作的有序列表
特点：除第一个和最后一个元素外，其他元素都有一个直接前驱和后继元素
什么是顺序表，什么是链表，顺序表和链表的优缺点有哪些
- 顺序表：使用顺序存储结构存储数据的线性表
优：随机读取；内存空间利用率高
缺：需要预先估计表容量；插入和删除操作时需移动大量的数据元素 - 链表：用链式存储结构存储数据的线性表
优：无限量存储数据；效率高
缺：空间利用率低
什么是栈和队列，它们有什么特点
栈：是一种允许在表的一端（栈顶）进行插入删除操作的线性表；特点 先进后出
队列：允许在表的一端进行插入操作，在另一端删除操作的线性表；特点 先进先出
树与图结构有什么特点
树形结构是一对多的结构
图形结构是多对多结构，每个结点都可能有多个直接前驱和直接后继
给定一棵二叉树，会进行二叉树的遍历
二叉树的三种遍历：
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
例子：
那么
先序（根左右）：A B D H E I C F J K G
中序（左根右）：D H B E I A J F K C G
后序（左右根）：H D I E B J K F G C A
给定一组关键字，会构造哈希表（给定哈希函数和解决冲突的方法）
给定一组权值，会构造哈夫曼编码
折半查找对查找表有什么要求。给定一个有序查找表，会利用折半查找分析查找过程
折半查找法要求查找表中各元素的键值必须是递增或递减排列
算法部分(查找 和 排序)
排序
冒泡排序
public class BubbleSort3 {
public static void main(String[] args) {
int[] arr = {-12,3,5,8,9,21,45,67};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length -1; j++) {
if (arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 10,2,45,65,32,12,35,12,45,78,5 };
quickSort(arr,0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(" ");
System.out.print(arr[i]);
}
}
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i = low;
j = high;
//temp就是基准位（参考数）
temp = arr[low];
while (i<j){
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j){
j--;
}
//再看左边，依次往右递增
while (temp>=arr[j]&&i<j){
i++;
}
//如果满足条件则交换
if (i<j){
t =arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j - 1);
//递归调用右半数组
quickSort(arr,j + 1,high);
}
}
查找
二分查找
public class BinarySearch{
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9,10};
int key = 8; //查找的数
int p = BinarySearch(arr,key,0,arr.length - 1);
if(p == -1){
System.out.println("查找的是"+key+",序列中没有该数！");
}else{
System.out.println("查找的是"+key+",找到位置为："+p);
}
}
/**
* 功能描述: 递归实现二分算法
* @Param: 参数 [key, array, low, high]
* @Return: int
* @Author: Liu
* @Date: 1/9/2021 7:01 PM
*/
public static int BinarySearch(int[] arr,int key,int low,int high){
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
int mid = (low + high) / 2; //初始中间位置
if(arr[mid] > key){
//比关键字大则关键字在左区域
return BinarySearch(arr, key, low, mid - 1);
}else if(arr[mid] < key){
//比关键字小则关键字在右区域
return BinarySearch(arr, key, mid + 1, high);
}else {
return mid;
}
}
}
顺序查找
public class SeqSearch {
public static void main(String[] args) {
int[] array = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62};
System.out.println("输入查找的数：");
Scanner scanner = new Scanner(System.in);
int input = scanner.nextInt();
SeqSearch(array,input);
}
/**
* 功能描述:
* @Param: 参数 [arr, input]
* @Return: void
* @Author: Liu
* @Date: 1/9/2021 10:47 PM
*/
public static void SeqSearch(int[] arr,int input){
for (int i = 0; i < arr.length; i++) {
if (arr[i]==input){
System.out.println(input+"的位置是："+i);
break;
}
if (i == arr.length-1){
System.out.println("没有该数");
}
}
}
}
