Loser 博客第十章-数据结构和算法
1、怎么理解时间复杂度和空间复杂度
时间复杂度和空间复杂度一般是针对算法而言，是衡量一个算法是否高效的重要标准。先纠正一个误区，时间复杂度并不是算法执行的时间，再纠正一个误区，算法不单单指冒泡排序之类的，一个循环甚至是一个判断都可以称之为算法。其实理解起来并不冲突，八大排序甚至更多的算法本质上也是通过各种循环判断来实现的。
**时间复杂度：**指算法语句的执行次数。O(1),O(n),O(logn),O(n2)
**空间复杂度：**就是一个算法在运行过程中临时占用的存储空间大小，换句话说就是被创建次数最多的变量，它被创建了多少次，那么这个算法的空间复杂度就是多少。有个规律，如果算法语句中就有创建对象，那么这个算法的时间复杂度和空间复杂度一般一致，很好理解，算法语句被执行了多少次就创建了多少对象。
2、数组和链表结构简单对比
**数组：**相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标
数组的特性：
1.数组必须先定义固定长度，不能适应数据动态增减
2.当数据增加时，可能超出原先定义的元素个数，当数据减少时，造成内存浪费
3.数组查询比较方便，根据下标就可以直接找到元素，时间复杂度 O(1)；增加和删除比较复杂，需要移动操作数所在位置后的所有数据，时间复杂度为 O(N)
**链表：**是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的特性：
1.链表动态进行存储分配，可适应数据动态增减
2.插入、删除数据比较方便,时间复杂度 O(1)；查询必须从头开始找起，十分麻烦，时间复杂度 O(N)
常见的链表:
1.单链表：通常链表每一个元素都要保存一个指向下一个元素的指针
2.双链表：每个元素既要保存到下一个元素的指针，还要保存一个上一个元素的指针
3.循环链表：在最后一个元素中下一个元素指针指向首元素
链表和数组都是在堆里分配内存
应用：
如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了
4、怎么遍历一个树
笔试题
四种遍历概念
先序遍历：先访问根节点，再访问左子树，最后访问右子树。
后序遍历：先左子树，再右子树，最后根节点。
中序遍历：先左子树，再根节点，最后右子树。
层序遍历：每一层从左到右访问每一个节点。（借助队列来实现的）
每一个子树遍历时依然按照此时的遍历顺序。可以采用递归实现遍历。
4、冒泡排序（Bubble Sort）手写
算法描述：
● 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
● 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
● 针对所有的元素重复以上的步骤，除了最后一个；
● 重复步骤 1~3，直到排序完成。
如果两个元素相等，不会再交换位置，所以冒泡排序是一种稳定排序算法。
//代码实现
package com.atguigu.interview.chapter02;
/**
* @author atguigu
* @since 2019/7/22
* 冒泡排序
*/
public class BubbleSort {
/**
* @param data 被排序的数组
*/
public static void bubbleSort(int[] data) {
int arrayLength = data.length;
for (int i = 1; i < arrayLength; i++) {//第i次排序
for (int j = 0; j < arrayLength - i; j++) {//从索引为j的数开始
if (data[j] > data[j + 1]) { //相邻元素两两对比
int temp = data[j + 1]; // 元素交换
data[j + 1] = data[j];
data[j] = temp;
}
}
System.out.println("第" + i + "次排序：\n" + java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}5、快速排序（Quick Sort）手写
算法描述：
使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
● 从数列中挑出一个元素，称为 “基准”（pivot）；
● 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
● 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
key 值的选取可以有多种形式，例如中间数或者随机数，分别会对算法的复杂度产生不同的影响。
package com.atguigu.interview.chapter02;
/**
* @author atguigu
* @since 2019/7/22
* 快速排序
*/
public class QuickSort {
public static void quickSort(int[] data, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
//temp就是基准位
temp = data[low];
System.out.println("基准位：" + temp);
while (i < j) {
//先看右边，依次往左递减
while (temp <= data[j] && i < j) {
j--;
}
//再看左边，依次往右递增
while (temp >= data[i] && i < j) {
i++;
}
//如果满足条件则交换
if (i < j) {
System.out.println("交换：" + data[i] + "和" + data[j]);
t = data[j];
data[j] = data[i];
data[i] = t;
System.out.println(java.util.Arrays.toString(data));
}
}
//最后将基准位与i和j相等位置的数字交换
System.out.println("基准位" + temp + "和i、j相遇的位置" + data[i] + "交换");
data[low] = data[i];
data[i] = temp;
System.out.println(java.util.Arrays.toString(data));
//递归调用左半数组
quickSort(data, low, j - 1);
//递归调用右半数组
quickSort(data, j + 1, high);
}
public static void main(String[] args) {
int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data, 0, data.length - 1);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}5、二分查找（Binary Search）手写
算法描述：
● 二分查找也称折半查找，它是一种效率较高的查找方法，要求列表中的元素首先要进行有序排列。
● 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
● 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
● 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
package com.atguigu.interview.chapter02;
/**
* @author atguigu
* @since 2019/7/22
*/
public class BinarySearch {
/**
* 二分查找 时间复杂度O(log2n);空间复杂度O(1)
*
* @param arr 被查找的数组
* @param left
* @param right
* @param findVal
* @return 返回元素的索引
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
if (left > right) {//递归退出条件，找不到，返回-1
return -1;
}
int midIndex = (left + right) / 2;
if (findVal < arr[midIndex]) {//向左递归查找
return binarySearch(arr, left, midIndex, findVal);
} else if (findVal > arr[midIndex]) {//向右递归查找
return binarySearch(arr, midIndex, right, findVal);
} else {
return midIndex;
}
}
public static void main(String[] args){
//注意：需要对已排序的数组进行二分查找
int[] data = {-49, -30, -16, 9, 21, 21, 23, 30, 30};
int i = binarySearch(data, 0, data.length, 21);
System.out.println(i);
}
}拓展需求：
当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到。
package com.atguigu.interview.chapter02;
import java.util.ArrayList;
import java.util.List;
/**
* @author atguigu
* @since 2019/7/22
*/
public class BinarySearch2 {
/**
* {1, 8, 10, 89, 1000, 1000, 1234}
* 一个有序数组中，有多个相同的数值，如何将所有的数值都查找到，比如这里的 1000.
* 分析：
* 1. 返回的结果是一个列表 list
* 2. 在找到结果时，向左边扫描，向右边扫描 [条件]
* 3. 找到结果后，就加入到ArrayBuffer
*
* @return
*/
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
//找不到条件?
List<Integer> list = new ArrayList<>();
if (left > right) {//递归退出条件，找不到，返回-1
return list;
}
int midIndex = (left + right) / 2;
int midVal = arr[midIndex];
if (findVal < midVal) {//向左递归查找
return binarySearch2(arr, left, midIndex - 1, findVal);
} else if (findVal > midVal) { //向右递归查找
return binarySearch2(arr, midIndex + 1, right, findVal);
} else {
System.out.println("midIndex=" + midIndex);
//向左边扫描
int temp = midIndex - 1;
while (true) {
if (temp < 0 || arr[temp] != findVal) {
break;
}
if (arr[temp] == findVal) {
list.add(temp);
}
temp -= 1;
}
//将中间这个索引加入
list.add(midIndex);
//向右边扫描
temp = midIndex + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {
break;
}
if (arr[temp] == findVal) {
list.add(temp);
}
temp += 1;
}
return list;
}
}
public static void main(String[] args){
//注意：需要对已排序的数组进行二分查找
int[] data = {1, 8, 10, 89, 1000, 1000, 1234};
List<Integer> list = binarySearch2(data, 0, data.length, 1000);
System.out.println(list);
}
}