性质记忆
1、关于稳定性
不稳定： 快选堆希（快速排序、选择排序、堆排序、希尔排序）
稳 定： 插冒归计基（简单插入排序、冒泡排序、归并排序、计数排序、基数排序）
2、关于时间复杂度
平方阶 (O(n2)) 排序
各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序
快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数
希尔排序
线性阶 (O(n)) 排序
基数排序，此外还有桶、箱排序。
3、关于移动次数和关键字顺序无关的排序
堆排序、归并排序、选择排序、基数排序
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
冒泡排序
每次遍历，都将最大的元素移到最后。
相邻两个元素之间的比较。
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
public void bulbSort(int[] arr) { // 当前个与后一个相比，所以外循环只需n-1次 for (int i = 0; i < arr.length-1; i++) { // 内循环比较大小，因为当第i次循环完后，最后的i+1个已排完序，下一次可以不用参与 // 如：3 1 4 2 // 第i=0次循环完(4-1-0=3次)：1 3 2 4，最后一个排完序，下一次可以不用参与 // 第i=1次循环完(4-1-1=2次)：1 2 3 4，最后两个排完序，下一次可以不用参与 for (int j = 0; j < arr.length - i - 1; j++) { // 相邻元素两两对比，如果第一个比第二个大，就交换他们两个 if (arr[j]>arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
复制代码在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
public void selectionSort(int[] arr) { // 当前个与后一个相比，所以外循环只需n-1次 for (int i = 0; i < arr.length - 1; i++) { // 每次循环，i前面的都是已经排完序了的 // 初始将当前i位置的数认为是最小的 int minIndex = i; // 从i后面的所有数中，寻找值最小的数 for (int j = i+1; j < arr.length; j++) { // 判断是否比当前已知的最小的数还要小 if (arr[j]<arr[minIndex]) { // 将最小数的索引保存 minIndex = j; } } // 如果两者不相等，说明存在比它更小的数，需要交换 if (i!=minIndex){ // 将i位置的数与最小值的数交换 int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } }
复制代码依次将元素插入对应位置，不符合的元素后移。
在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
当前元素与它前面所有元素的对比。
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
public void insertSort(int[] arr) { // 第i=0个元素默认已经是有序，因此从i=1开始 // 每个元素都要参与比较，所以arr[n]也要取到 for (int i = 1; i < arr.length; i++) { // 先记录下待插入的元素的值 int key = arr[i]; int j; // 在已排序中，从后往前扫描 // 依次对比大小，大于它的往后移动，直至找到正确位置后停止 // j=i-1：前i-1个元素已经是排完序了的 for (j = i-1; j>=0 && arr[j]>key; j--) { arr[j+1] = arr[j]; } // 将值插入，注意上面的for循环出来前会执行一次j--，所以这里要j+1 arr[j+1] = key; } }
复制代码使用分治法来把一个串（list）分为两个子串（sub-lists）。
左右指针相向移动，先从右指针开始；小的放左边，大的放右边。
挖坑法
- 先从数列中取出一个数作为基准数。i =L; j = R; 将基准数挖出形成第一个坑a。
- j--由后向前找比它小的数，找到后挖出此数填前一个坑a中。
- i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
- 再重复执行2，3二步，直到i==j，将基准数填入a中。
public void quickSort(int[] arr, int left, int right) { // 当left=right时，说明左右指针指向了同一个元素 // 即当前分组只有一个元素，递归结束 if (left>=right) { return; }else { int l = left; int r = right; // 将左边第一个元素作为基准值 // 记录基准值，此时arr[l]这个位置可以放其他值了 int pivot = arr[l]; // 对于当前递归 // 循环比较，直至左右指针相遇，即l=r while (l<r) { // 先将右指针向左移动，直到遇到一个比基准值小的元素 while (l<r && arr[r]>pivot) { r --; } // 如果指向了同一个元素，就不需要交换 // 否则，就需要交换 if (l<r) { // 将右指针指向的元素值赋给左指针指向的元素值 // 此时arr[r]又可以存其他新的内容了 arr[l] = arr[r]; // 左指针已经填值，因此需要l++ l ++; } // 再将左指针向右移动，直到遇到一个比基准值大的元素 while (l<r && arr[l]<pivot) { l ++; } // 同上，下同 if (l<r) { arr[r] = arr[l]; r --; } } // 此时l=r，说明左右指向了同一个位置 // 而这个位置应该放的是基准值，且一趟排序完成 arr[l] = pivot; // 对基准值左边部分再进行递归排序 quickSort(arr, left, l-1); // 对基准值右边部分再进行递归排序 // 由于此时l=r，所以r+1=l+1没影响 quickSort(arr, r+1, right); } }
复制代码先拆分，再合并排序的算法
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
/** * 合并排序部分 * @param arr 原始数组 * @param tempArr 临时数组 * @param left 当前分组的左边位置序号 * @param right 当前分组的右位置边序号 */ public void merge(int[] arr, int[] tempArr, int left, int right) { // 大于1个元素，还可继续划分 if (left < right) { // 中间位置 int mid = (left+right)/2; // 左半部分递归划分 merge(arr, tempArr, left, mid); // 右半部分递归划分 merge(arr, tempArr, mid+1, right); // 到这里，说明已经划分完，开始向上合并 // 指向左边组序列的第一个 int l = left; // 指向右边组序列的第一个 int r = mid+1; // 临时数组的下标，这里的临时数组是存排序后的元素，排完后再复制到原数组中 int tempIndex = left; // 循环比较，直至左边组或右边组没有剩余元素了才停止 while (l<=mid && r<=right) { // 可以想象最简单的情况，倒数第二层，有两个元素，需要对这两个元素排序 // 如果左边组的一个元素 < 右边组的一个元素，就将小的那个先放到临时数组中。放完后，下标+1指向下一个元素 if(arr[l]<arr[r]) { tempArr[tempIndex++] = arr[l++]; }else { tempArr[tempIndex++] = arr[r++]; } } // 可能左边组还有剩余元素，将剩余元素添加到临时数组最后 while (l<=mid) { tempArr[tempIndex++] = arr[l++]; } // 可能右边组还有剩余元素，将剩余元素添加到临时数组最后。这里与上面左边剩余的情况不会同时成立 while (r<=right) { tempArr[tempIndex++] = arr[r++]; } // 最后将排完顺序的临时数组中的元素复制到原数组中 while (left<=right) { arr[left] = tempArr[left]; left++; } } // 否则，说明已经划分到最小单元，即一个元素 else { return; } } public void mergeSort(int[] arr) { // 开辟一个临时数组 int[] tempArr = new int[arr.length]; // 开始归并排序 merge(arr, tempArr, 0, arr.length-1); } public static void main(String[] args) { int[] arr = new int[]{5,9,1,4,54,6,77,54,3,9,5,66,2,6,34}; new Main().mergeSort(arr); System.out.println(Arrays.toString(arr)); }
复制代码平均时间复杂度：O(nlogn) 最佳时间复杂度：O(n) 最差时间复杂度：O(nlogn) 空间复杂度：O(n) 排序方式：In-place 稳定性：稳定
不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。
希尔排序
按组(增量)进行插入排序的算法。
通过对每组使用直接插入排序，使整个数组基本有序.数据有序程度越高，最后使用的插入排序效率越高。
动图是分组执行，实际操作是多个分组交替执行
当gap=4时,意味着将数列分为4个组： {80,20},{30,10},{60,50},{40,70}。 对应数列： {80,30,60,40,20,10,50,70} 对这4个组分别进行排序，排序结果： {20,80},{10,30},{50,60},{40,70}。 对应数列： {20,10,50,40,80,30,60,70}
当gap=2时,意味着将数列分为2个组：{20,50,80,60}, {10,40,30,70}。 对应数列： {20,10,50,40,80,30,60,70} 注意：{20,50,80,60}实际上有两个有序的数列{20,80}和{50,60}组成。 {10,40,30,70}实际上有两个有序的数列{10,30}和{40,70}组成。 对这2个组分别进行排序，排序结果：{20,50,60,80}, {10,30,40,70}。 对应数列： {20,10,50,30,60,40,80,70}
当gap=1时,意味着将数列分为1个组：{20,10,50,30,60,40,80,70} 注意：{20,10,50,30,60,40,80,70}实际上有两个有序的数列{20,50,60,80}和{10,30,40,70}组成。 对这1个组分别进行排序，排序结果：{10,20,30,40,50,60,70,80}
public void shellSort(int[] arr) { // 每次增量除2 for (int inc = arr.length/2; inc > 0; inc/=2) { // 每一趟使用插入排序，从第1组的第2个元素开始，到数组的最后一个元素 // 这里每趟都是对下一组进行排序，即各组交替执行，而不是一个组排序完后再换下一个组 for (int i = inc; i < arr.length; i++) { // 先拿到当前位置的值key int key = arr[i]; int j; // 对当前组的当前位置及前面元素进行插入排序 // j>=inc：保证j-inc非负 // key<arr[j-inc]：将目标值与前一个元素的值比较 // j-=inc：指向当前组的前一个元素 for (j = i; j>=inc&&key<arr[j-inc]; j-=inc) { // 将值后移 arr[j] = arr[j-inc]; } // 将key插入，注意上面的for循环出来前，会执行一次j-=inc arr[j] = key; // 或者 /* for (j = i-inc; j>=0 && arr[j]>key; j-=inc) { arr[j+inc] = arr[j]; } arr[j+inc] = key; */ } }
复制代码堆排序
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
- 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
下标为i的节点的父节点下标: (i-1)/2【整数除法】下标为i的节点的左孩子下标:i*2+1下标为i的节点的右孩子下标:i*2+2
/** * 堆排序 * @param arr 待排序数组 * @param n 总节点数 * @param i 当前节点的下标 */ void heapify(int[] arr, int n, int i) { // 记录最大值的节点的下标 int largest = i; // 第i个节点的左子节点的下标：i*2+1 int lson = i*2+1; // 第i个节点的右子节点的下标：i*2+2 int rson = i*2+2; // 先比较根节点与左子节点的大小 // 如果左子节点的值更大，就记录左子节点的下标 if (lson<n && arr[lson]>arr[largest]) { largest = lson; } // 再比较根节点(或左子节点，如果上面的if成立的话)与右子节点的大小 // 如果右子节点的值更大，就记录右子节点的下标 if (rson<n && arr[rson]>arr[largest]) { largest = rson; } // 若不相等，则说明largest有变动过，即左或右子节点比根节点大了 if (largest != i) { // 交换两者的值，把更大的值放到根节点上 int temp = arr[largest]; arr[largest] = arr[i]; arr[i] = temp; // 递归执行堆维护，因为可能本次调整完后，影响了后面的堆性质，如： // 3 4 // / \ / \ // 4 1 => 3 1 // / \ / \ // 5 2 5 2 // 3跟4换完后，3跟5也需要换 heapify(arr, n, largest); } } /** * 大顶堆，堆排序 * @param arr 待排序的数组 */ public void heapSort(int[] arr) { int n = arr.length; // 1.建堆 // 第i个节点的根节点的下标：(i-1)/2 // 最后一个节点的根节点的下标：((n-1)-1)/2 = n/2-1 // 从最后一个根节点到0号根节点依次循环 for (int i = n/2-1; i >= 0; i--) { // 从下往上维护堆，递归次数少，效率高 heapify(arr, n, i); } // 2.排序 // 将最大放到最后 // 由于大顶堆，所以最大值总是在0号节点上 // 从最后一个节点到0号节点依次循环 for (int i = n-1; i > 0; i--) { // 交换两者的值，把最大值放到后面的节点上 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 交换完成后，对剩余的节点继续执行堆维护 // i: 由于每次都把最大值往后面放，所以这个i可以限制heapify不会影响到后面已排完序的节点 // 0: 从上往下维护堆，之前已经建完堆，这次可能只需要微调 heapify(arr, i, 0); }
复制代码
数组
- 线性数据结构
- 元素存储在连续的内存位置
- 可以使用索引随机访问元素
- 存储同类元素，即相似元素
优点
- 随机访问
- 易于排序和迭代
- 多变量替换
缺点
- 大小固定
- 难以插入和删除
- 如果容量更大而占用更少，则大多数阵列将被浪费
- 需要连续的内存才能分配
应用领域
- 用于以线性方式存储信息
- 频繁查询，对存储空间要求不大，很少增加和删除的情况
堆
- Binary Heap可以可视化为完整的二叉树数组
- arr[0]元素将被视为根
- 通常在我们处理最小和最大元素时使用
- 对于第i个节点
优点
- 可以有2种类型：最小堆和最大堆
- 最小堆的顶部保持最小的元素，最大堆的顶部保持最大的元素+
- O(1)用于处理最小或最大元素
缺点
- 不可能随机访问
- 仅最小或最大元素可访问
应用领域
- 适用于优先处理的应用
- 调度算法
- 缓存
- 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
堆排序
栈
- 仅顶部元素可访问
- 插入和删除从顶部开始，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
- LIFO先进后出
- 所有操作均在恒定时间内进行，即O(1)
优点
- 以LIFO方式维护数据
- 最后一个元素随时可用
- 所有操作的复杂度均为O(1)
缺点
- 操作仅限于栈的顶部
- 不太灵活
应用领域
- 常应用于实现递归功能方面的场景
- 解析功能方面的场景
队列
- 线性数据结构
- 遵循FIFO：先进先出，从一端放入元素的操作称为入队，取出元素为出队
- 可以从后端插入。
- 可以从前端进行删除。
优点
- 以FIFO方式维护数据
- 从开始插入和从结束删除需要O(1)时间
应用领域
- 在多线程阻塞队列管理中非常适用
- 中断处理
链表
Python链表详细笔记
- 线性数据结构
- 可以根据内存可用性存储元素
- 只能以线性方式访问元素
- 存储同类元素，即相似元素
- 动态尺寸
- 易于插入和删除
- 起始元素或节点是键，通常称为head。
优点
- 动态尺寸，不需要初始化容量，可以任意加减元素
- 由于容量和尺寸始终相等，因此不会浪费
- 易于插入和删除，因为需要1个链接操作
- 高效的内存分配，添加、删除很快
缺点
- 如果头节点丢失，则链接列表也丢失
- 不能随机访问
应用领域
- 适用于内存有限的地方，数据量较小
- 适用于需要频繁插入和删除的应用
public class Node { // 为了方便，变量都使用public，而不用private就不需要编写get、set方法了 public Node prev; public Node next; public int val; // 无参构造方法 public Node() {} // 构造方法，在构造时就能够给val赋值 public Node(int val) { this.val = val; } } public class LinkedList { // 头结点 private Node head = new Node(); private int size = 0; /** * 打印链表 */ public void print() { Node temp = head; while (temp.next != null) { temp = temp.next; System.out.print(temp.val+"->"); } System.out.println(); } /** * 返回链表大小 * @return 链表的大小 */ public int getSize() { return size; } /** * 在链表最后添加节点 * @param val 待添加的值 */ public void add(int val) { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = new Node(val); size ++; } /** * 在指定位置的插入节点，旧节点后移 * @param index 待添加的位置，第一个为0 * @param val 待添加的值 */ public void insert(int index, int val) { Node temp = head; if (index<=size) { // 遍历到待删除节点的前一个节点即可 for (int i = 0; i < index; i++) { temp = temp.next; } Node node = new Node(val); node.next = temp.next; temp.next = node; size ++; } } /** * 删除一个节点 * @param index 节点所在位置，第一个为0 */ public void remove(int index) { Node temp = head; if (index<=size) { // 遍历到待删除节点的前一个节点即可 for (int i = 0; i < index; i++) { temp = temp.next; } // 重新链接，跳过待删除节点 temp.next = temp.next.next; size --; } } }
复制代码二叉树
Python二叉树详解笔记
- 分层数据结构
- 最顶层的元素被称为树的根
- 每个节点在二叉树中最多可以有2个子节点
- 可以使用索引随机访问元素
- 例如：文件系统层次结构
优点
- 可以表示某种关系的数据
- 插入和搜索非常有效
- 添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案。
缺点
- 排序困难
- 不太灵活
应用领域
- 文件系统层次结构
- 二叉树的多种变体具有广泛的应用
- 在处理大批量的动态数据方面非常有用
// 节点类 public class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } } public Node create() { Node root = new Node(0); root.left = new Node(1); root.right = new Node(2); root.left.left = new Node(3); root.left.right = new Node(4); root.right.left = new Node(5); root.right.left.left = new Node(6); return root; } /** * 先序遍历，先输出根节点，再遍历左子节点，再遍历右子节点 * @param node */ public void preTraversal(Node node) { if (node != null) { System.out.print(node.val+" "); preTraversal(node.left); preTraversal(node.right); } } /** * 中序遍历，先遍历左子节点，再输出跟节点，再 遍历右子节点 * @param node */ public void midTraversal(Node node) { if (node != null) { midTraversal(node.left); System.out.print(node.val+" "); midTraversal(node.right); } } /** * 后序遍历 * @param node */ public void lastTraversal(Node node) { if (node != null) { lastTraversal(node.left); lastTraversal(node.right); System.out.print(node.val+" "); } } /** * 层序遍历 * 通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。 * 而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队， * 出队结点的先后顺序就是层次遍历的最终结果。 * @param root 根节点 */ public void levelTraversal(Node root) { // 先判断根节点非空 if (root!=null) { // 创建一个队列（先入先出FIFO），用于存放节点 Queue<Node> queue = new LinkedList<>(); // 先将根节点放入 queue.offer(root); // 然后取出一个节点 Node node = queue.poll(); // 循环取出、判断节点是否非空 while (node!=null) { // 输出 System.out.print(node.val+" "); // 判断左子节点非空，若非空则加入队列 if (node.left!=null) { queue.offer(node.left); } // 判断右子节点非空，若非空则加入队列 if (node.right!=null) { queue.offer(node.right); } // 从队列取出一个节点 node = queue.poll(); } } } public static void main(String[] args) { Node node = create(); preTraversal(node); System.out.println(); midTraversal(node); System.out.println(); lastTraversal(node); System.out.println(); levelTraversal(node); System.out.println(); }
复制代码二叉搜索树
- 具有附加限制的二叉树
- 限制：左子节点必须始终小于根节点正确的子节点必须始终大于根节点
- 插入，删除，搜索比二叉树有效得多
优点
- 保持元素顺序
- 可以轻松找到树中的最小和最大节点
- 中序遍历给出排序的元素
缺点
- 不可能随机访问
- 增加了复杂性
应用领域
- 适用于排序的分层数据
public void insert(Node root, int value) { // 当前节点不为空，则继续往下寻找 if (root != null) { // 若待插入的值比当前节点的值小，则往左放 if (value < root.val) { // 左子节点不为空，则递归插入 if (root.left != null) { insert(root.left, value); } // 否则说明已到最后，可以插入 else { root.left = new Node(value); } } // 同上 else if (value > root.val) { if (root.right != null) { insert(root.right, value); }else { root.right = new Node(value); } } } // 当前节点为空，则直接赋值 else { root = new Node(value); } }
复制代码图
- 基本上是一组边和顶点
- 图表示G(V, E)；其中V(G)代表一组顶点，E(G)代表一组边
- 该图可以是有向的或无向的
- 该图可以连接或不连接
优点
- 寻找连通性
- 最短路径
- 从1点到其他点的最低成本
- 最小生成树
缺点
- 存储图（邻接表和邻接矩阵）可能会导致复杂性
应用领域
- 适用于电路网络
- 适用于Facebook，LinkedIn等应用
- 医药科学
哈希表
- 使用特殊的哈希函数
- 哈希函数将元素映射到要存储的地址
- 这提供了恒定时间的访问
- 碰撞由碰撞解决技术处理
- 碰撞解决技术链式开放寻址法
优点
- 哈希函数有助于在恒定时间内获取元素
- 存储元素的有效方法
缺点
- 碰撞解决会增加复杂性
应用领域
- 适用于需要恒定时间获取的应用
来源：小锋学长
https://www.toutiao.com/i6906343788252381708/
/3 
