数据结构和算法总结

一、排序算法

1.1、排序分类

1.内部排序

指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。

2.外部排序法

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

1.2、十大排序算法总结

1872684-20201212184659097-857692168.png

1.3、冒泡排序

1.算法步骤

step1：比较相邻的元素，如果第一个比第二个大，就交换两个元素。

step2：对每一个相邻元素同样的工作，从开始到结尾，最后一个元素是已经排序好的元素。

step3：重复step1。

2.代码实现

public class BubbleSort {
 public static void s(int[] arr) {
 for (int i = 0; i < arr.length; i++) {
 // arr.length-i 重复遍历未排序的数列。
 for (int j = 1; j < arr.length-i; j++) {
 if (arr[j-1] > arr[j]) {
 int temp = arr[j-1];
 arr[j-1] = arr[j];
 arr[j] = temp;
 }
 }
 }
 }

3.冒泡排序改进

（1）设置一个标志性pos，记录每趟排序中最后一次交换的位置。由于pos位置之后的记录均已排序，故进行下一次排序扫描到pos位置即可。

（2）传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，可以利用再每趟排序中进行正向和方向两遍冒泡排序的方法一次可以得到两个最终值（最大值和最小值），从而使排序趟数几乎减少一半。

1.4、快速排序

1.算法步骤

略

2.代码实现

public class QuickSort {
 public static void quickSrot(int[] arr, int low, int high) {
 int i, j, stan;
 if (low > high) {
 return;
 }
 stan = arr[low];
 i = low;
 j = high;
 while (i < j) {
 while (i < j && stan <= arr[j]) {
 j--;
 }
 while (i < j && stan >= arr[i]) {
 i++;
 }
 // 满足条件交换
 if (i < j) {
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }
 // 当i==j，交换基准位
 arr[low] = arr[i];
 arr[i] = stan;
 // 递归调用小于基准数部分。
 quickSrot(arr, low, i-1);
 // 递归调用大于基准数部分。
 quickSrot(arr, i + 1, high);
 return;
 }

 public static void main(String[] args) {
 int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
 QuickSort quickSort = new QuickSort();
 // 注意high初始值
 quickSort.quickSrot(arr, 0, arr.length-1);
 for (int item : arr) {
 System.out.println(item);
 }
 }
}

3.快速排序改进

（1）选择基准元素的方式（a.固定基准元。b.随机基准元。c.三数取中）

（2）当原表有序直接使用插入排序和冒泡排序可以减少比较次数，时间复杂度O(n)

1.5、插入排序

1、算法步骤

step1：从第一个元素开始，该元素默认已经排序。

step2：取出下一个元素，在已经排序的元素序列中从后向前扫描。

step3：如果已排序中的元素大于新元素，已排序元素向下移动一位；重复step3，直到已排序的元素小于或等于新元素位置。

step4：将元素插入到该位置；重复step2~step5

2、代码实现

public class InsertSort {
 public static void s(int[] arr) {
 int len = arr.length;
 // 第一个元素默认已排好序
 for (int i = 1; i < len; i++) {
 int preIndex = i - 1;
 // 取出下一个元素，在已排序好的序列中从前向后扫描。
 int current = arr[i];
 while (preIndex >= 0) {
 // 如果该元素大于前一个元素，该元素向后移动
 if (arr[preIndex] > current) {
 arr[preIndex+1] = arr[preIndex];
 }
 preIndex--;
 }
 // 找到该元素小于或等于新元素的位置
 arr[preIndex+1] = current;
 }
 }
}

二、数组和链表

数组：固定长度，内存角度方便查找

从访问方式：数组利用下表索引方便访问；链表只能通过线性访问由前到后顺序访问。

一个单链表怎么判断有没有环？环的起点怎么找？ 如何找出环的连接点在哪里？带环链表的长度是多少？

1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。 2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。 3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。 该定理的证明可参考：http://fayaa.com/tiku/view/7/ 4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度

三、图

邻接矩阵与邻接表

邻接矩阵表示法：在一个一维数组中存储所有的点，在一个二维数组中存储顶点之间的边的权值

邻接表表示法：图中顶点用一个一维数组存储，图中每个顶点vi的所有邻接点构成单链表

四、哈希表

hashmap实现

解决哈希冲突的方法

1、线性探测法 2、平方探测法 3、伪随机数序列法 4、拉链法

五、栈区、堆区和队列

栈：限定只能在表的一端进行插入和删除操作的线性表。

队列：限定只能在表的一端插入和在另一端进行删除。