复杂度分析
为什么需要时间复杂度？
通过统计、监控获得代码的运行时长和占用内存有一定的局限性。
- 测试结果非常依赖测试环境。 如在不同的处理器下获得的运行结果不同。
- 测试结果受限于数据的规模。 如在数据量少的情况下，插入排序会快于快速排序。 因此需要一个粗略的估计方法。
常见的时间复杂度量级
O(1)
int a = 8;
int b = 2;
int sum = a + b
O(n)
int sum = 0;
for(int i = 0;i < n;i++) {
sum += i;
}
O(logn)、O(nlogn)
int i = 1;
while(i <= n) {
i *= 2;
}
O(n2)**、**O(n3)...
for(...){
for(...) {
...
}
}
O(m + n)、O(m * n)
for(int i = 0;i < n;i++){...}
for(int i = 0;i < m;i++){...}
O(n!)
O(2^n)
思考：
有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？
答：代码的时间复杂度和空间复杂度分析是程序员的基本功，这并不会消耗过多的时间，同时正是因为有这一概念，使得我们在写代码时，有一个优化的目标。
最好时间复杂度、最坏时间复杂度
// n表示数组array的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
当运气最好时，即第一个就为所要查的值，此时时间复杂度为O(1)，当运气最差时，即该数组中没有这个值，此时时间复杂度为O(n)
平均时间复杂度
无论最好时间复杂度还是最差时间复杂度，都只在极端的情况下才会发生，发生的概率不大。因此为了更好地表示平均情况下的复杂度， 我们需要引入另一个概念：平均情况时间复杂度。
算平均时间复杂度的方法，加权平均值。同样以上面那个代码为例，要查找的变量x在数组中的位置，有n+1种情况：在数组的0～n-1位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以n+1， 就可以得到需要遍历的元素个数的平均值，即：
我们知道，要查找的变量x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便你理解，我们假设在数组中与不在数组中的概 率都为1/2。另外，要查找的数据出现在0～n-1这n个位置的概率也是一样的，为1/n。所以，根据概率乘法法则，要查找的数据出现在0～n-1中任意位置的概率就 是1/(2n)。
大部分情况下使用一种复杂度即可，只有在量级变动大的时候，才使用最好、最坏、平均时间复杂度进行分析。
均摊时间复杂度
// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
与上一个代码例子不同的是，find函数只在极端情况下的时间复杂度为O(1),而insert函数在大部分情况下的时间复杂度为O(1)，同时insert函数每隔n-1次O(1)的操作后，迎来一次O(n)的时间复杂度操作，具有规律性。
摊还分析法：每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的 操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。
思考:
分析一下下列代码的时间复杂度：
// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个2倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来array数组中的数据依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array复制给array，array现在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 将element放到下标为i的位置，下标i加一
array[i] = element;
++i;
}
答：仔细看，发现符合摊还分析法。大部分情况为O(1)时间复杂度的操作，只有当下标超过数组空间时，才会申请一个更大的空间，进行数据的迁移，此时的时间复杂度为O(n).故平均复杂度为O(1).
数组
概念
数组的概念：数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
1、线性表：指数据只有前后两个方向的结构。常见的如栈、队列、链表等。而树、图、堆为非线性的。
2、连续的内存空间和相同类型的数据。 有利且有弊，利在于数组支持随机访问（一般不说查询的时间复杂度为O(1)，顺序的二叉查找时间复杂度都为O(logn)）,弊在于在插入和删除操作时，为保证顺序性需要迁移数据。
数组是如何实现随机访问的？
我们拿一个长度为10的int类型的数组int[] a = new int[10]来举例。 在图中，计算机给数组a[10]，分配了一块连续内存空间1000～1039，其中，内存块的首地址为base_address = 1000
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size
其中data_type_size表示数组中每个元素的大小。我们举的这个例子里，数组中存储的是int类型数据，所以data_type_size就为4个字节。
数组插入删除效率的提高
如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是O(n)。 因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为(1+2+…n)/n=O(n)。
为避免大规模的迁移数据，可以在将数据插入到第k位后，将原先第k位的数字插入到数组尾部
这样可以提高插入的时间复杂度，但无法保证原先数组的顺序性。快排中引入了这个思想。
删除操作同插入操作的时间复杂度一致。对于删除操作可以先标记要删除的元素，在数组满的时候，再统一删除，这样可以大大减少删除导致的数据迁移。如jvm的标记清理。
容器ArrayList与数组如何抉择？
ArrayList相对于数组的优势是，将很多数组操作的细节封装了，使得程序员不用关心底层的逻辑，如添加，删除，扩容等。
而数组相对于ArrayList的优点是，ArrayList无法存储基本数据类型，他只能存储基本数据类型的封装类以及其他类，而装箱与拆箱有一定的性能消耗。
通常在写业务代码时使用的是ArrayList，因为这点性能影响不了整体系统的性能，而在做底层开发时，会选择使用数组，为了达到极致的性能。
数组为什么从0开始编号？
数组a[n],a代表数组首地址，n表示偏移，a[k]表示偏移k*type_size的位置。故其随机访问公式为:
a[k]_address = base_address + k * type_size
如果从1开始的话，那么公式就为
a[k]_address = base_address + (k - 1) * type_size
每次随机访问都多一次减的操作。
从历史上讲，java,js等设计者为了减少c语言程序员的学习成本，沿袭了c语言中0作为数组起始编号的设计
思考
二维数组的随机访问公式应该是怎样的？
答：a[i][j] = base_address + (i * n + j) * type_size.
链表
链表是线性表，与数组不同的是，他并不占据连续的内存空间，链表包括单链表，双链表，循环链表，循环双链表。
由于链表是通过指针将离散的内存空间串起来，因此他并不具备随机访问特性。
其好处是数组需要合理设置大小，过小会导致频繁扩容，过大会由于内存不足而导致创建失败。链表不必担心内存中没有连续的内存空间，同时其插入删除操作的时间复杂度为O(1),不需要进行数据的迁移操作。链表由于没有大小的限制，天然支持扩容。
其弊端在于，cpu读取内存时，会先将一个数据块读入cpu缓存中。下次访问内存数据，会先从cpu缓存中读取，cpu缓存没有时，才会读取内存，该机制是为了弥补内存访问慢与cpu处理速度快的差异。利用该缓存机制，cpu读取数组的效率会快于链表，因为数组的内存空间是连续的，而链表是非连续的。同时链表会有大量的插入删除操作，这在java语言中，可能导致频繁的gc。链表每个节点需要额外的存储空间去存储指向下一个节点的指针，这也使得链表的内存消耗会翻倍。
单链表
利用头节点和尾节点，可以完整遍历链表。
循环链表
循环链表是特殊的单链表，其尾节点指向头节点，适合解决约瑟夫问题。 约瑟夫问题：
剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int lastRemaining(int n, int m) {
if(m == 1) {
return n - 1;
}
Node head = new Node(0);
Node cur = head;
for(int i = 1;i < n;i++) {
cur.next = new Node(i);
cur = cur.next;
}
cur.next = head;
cur = head;
int count = 0;
while(cur.next != cur) {
if(count == m - 2) {
cur.next = cur.next.next;
count = 0;
cur = cur.next;
continue;
}
cur = cur.next;
count++;
}
return cur.val;
}
}
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
public Node(){}
}
仅作示例，该解法会超时。
双链表
相对于单链表而言，需要额外的存储空间，但他使得插入删除相对于单链表而言更加高效。
以删除为例，单链表的删除有两个情境：
- 删除链表中指定的值
- 删除链表中已知结点。 情境1下，无论单链表还是双链表，其删除的时间复杂度是一致的，都需要进行一次O(n)的遍历，而情境二下，单链表需要重新进行一次遍历，找到删除结点的前驱节点，而双链表只需要通过前驱指针即可，该情况下双链表的删除只需要O(1).这体现了空间换时间的思想。LinkedHashMap即采用双向链表。
思考：
单链表如何判断字符串为回文串？
public class Main {
public static void main(String[] args) {
String s = "abc";
Node root = new Node(s.charAt(0));
Node cur = root;
for (int i = 1; i < s.length(); i++) {
cur.next = new Node(s.charAt(i));
cur = cur.next;
}
boolean flag = isPalindrome(root);
System.out.println(flag);
}
public static boolean isPalindrome(Node root) {
Node slow = root;
Node fast = root;
Node pre = null;
while (fast != null && fast.next != null) {
fast = fast.next.next;
Node tmp = slow.next;
slow.next = pre;
pre = slow;
slow = tmp;
}
if (fast != null) {
slow = slow.next;
}
while (slow != null) {
if (slow.val != pre.val) return false;
slow = slow.next;
pre = pre.next;
}
return true;
}
}
class Node {
char val;
Node next;
public Node() {
}
public Node(char val) {
this.val = val;
}
}
链表练习题
剑指 Offer II 024. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
面试题 02.08. 环路检测 题解 - 力扣（LeetCode） (leetcode-cn.com)
21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)
剑指 Offer II 021. 删除链表的倒数第 n 个结点 - 力扣（LeetCode） (leetcode-cn.com)
栈
如何理解栈？
栈是操作受限的线性表，之所以需要这样的数据结构，是因为数组、链表相对于一些功能而言暴露了太多没必要的接口，栈适合于一些先进后出的场景。
实现一个栈
基于数组
class Stack{
private String[] arr;
private int capacity;
private int cur;
public Stack(int capacity) {
this.capacity = capacity;
arr = new String[capacity];
cur = 0;
}
public boolean put(String s) {
if (cur == capacity) return false;
arr[cur] = s;
cur++;
return true;
}
public String remove(){
if (cur == 0) return null;
String res = arr[cur - 1];
cur--;
return res;
}
}
基于链表
class Stack{
private int capacity;
private int cur;
private Node node;
public Stack(int capacity) {
this.capacity = capacity;
cur = 0;
node = null;
}
public boolean put(String s) {
if (cur == capacity) {
return false;
}
if (node == null) {
node = new Node(s);
cur++;
return true;
}
Node t = new Node(s);
node.next = t;
t.pre = node;
node = node.next;
cur++;
return true;
}
public String remove(){
if (cur == 0) {
return null;
}
String res = node.val;
node = node.pre;
cur--;
if (node == null) return res;
node.next = null;
return res;
}
}
class Node{
public String val;
public Node next;
public Node pre;
public Node(String val) {
this.val = val;
}
public Node(){}
}
栈在函数调用的应用
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
栈在表达式求值的应用
栈可用作加减乘除的四则运算。编译器通过两个栈来实现加减乘除的四则运算，其中一个栈保存操作数，另一个栈保存运算符。们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
/**
* @author EnochStar
* @title: Calculator
* @projectName basic_use
* @description: TODO
* @date 2021/10/17 14:26
*/
public class Calculator {
private static Map<Character,Integer> map = new HashMap<>();
static {
map.put('+',1);
map.put('-',1);
map.put('*',2);
map.put('/',2);
}
public int solve (String s) {
char[] cs = s.toCharArray();
Deque<Integer> nums = new ArrayDeque();
Deque<Character> symbol = new ArrayDeque();
int len = cs.length;
for(int i = 0;i < len;i++) {
if(cs[i] == ' ') continue;
if(Character.isDigit(cs[i])){
int num = cs[i] - '0';
while(i + 1 < len && Character.isDigit(cs[i + 1])) {
num = num * 10 + cs[++i] - '0';
}
nums.addLast(num);
}else if(cs[i] == '(') {
symbol.addLast(cs[i]);
}else if(cs[i] == ')') {
while(!symbol.isEmpty()) {
if(symbol.peekLast() != '(') {
cal(nums,symbol);
}else{
symbol.pollLast();
break;
}
}
}else{
while(!symbol.isEmpty() && symbol.peekLast() != '(') {
char pre = symbol.peekLast();
if(map.get(pre) >= map.get(cs[i])) {
cal(nums,symbol);
}else{
break;
}
}
symbol.addLast(cs[i]);
}
}
while(!symbol.isEmpty() && symbol.peekLast() != '(') {
cal(nums,symbol);
}
int ans = nums.pollLast();
return ans;
}
public void cal(Deque<Integer> nums,Deque<Character> symbol) {
if(nums.isEmpty()) return;
int fis = nums.pollLast();
int sec = nums.pollLast();
char c = symbol.pollLast();
int num;
if(c == '+') {
num = fis + sec;
}else if(c == '-'){
num = sec - fis;
}else if(c == '*') {
num = fis * sec;
}else {
num = sec / fis;
}
nums.addLast(num);
}
}
除此之外，栈还可用作括号匹配，在此不再赘述。
如何实现浏览器的前进与后退？
浏览器的前进与后退也可以用栈来实现，即一个栈用于存储浏览的历史，当执行后退时，就将第一个栈的一个内容推出到第二个栈中，当执行前进时，就将第二个栈的内容返还给第一个栈，当打开新的页面时，就清空第二个栈的内容。如图：
顺序查看了a，b，c三个页面，我们就依次把a，b，c压入栈
当你通过浏览器的后退按钮，从页面c后退到页面a之后，我们就依次把c和b从栈X中弹出，并且依次放入到栈Y。
这个时候你又想看页面b，于是你又点击前进按钮回到b页面，我们就把b再从栈Y中出栈，放入栈X中。
这个时候，你通过页面b又跳转到新的页面d了，页面c就无法再通过前进、后退按钮重复查看了，所以需要清空栈Y。
思考
1、在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
2、我们都知道，JVM内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储Java中的对象。那JVM里面的“栈”跟我们这里说 的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？
解答： 1、并不一定要用栈保存临时变量，只是函数调用时，刚好符合后进先出这个特性，因此用栈来保存临时变量是很方便的。
2、不是一回事，内存中的堆栈是真实存在的物理区，而这里的栈只是一个抽象的数据结构。只是jvm中的栈符合数据结构中栈的特性。
队列
如何理解队列？
队列和栈类似，也是操作受限的数据结构，其特性是先进先出，可理解为日常生活中的排队。
如何实现队列？
方法1、
/**
* @author EnochStar
* @title: Queue
* @projectName basic_use
* @description: TODO
* @date 2021/10/17 16:46
*/
public class Queue {
private String[] queue;
private int capacity;
private int head;
private int tail;
public Queue(int capacity) {
this.capacity = capacity;
queue = new String[capacity];
head = 0;
tail = 0;
}
public boolean enqueue(String s){
if (tail == capacity) return false;
queue[tail++] = s;
return true;
}
public String dequeue() {
if (head == tail) return null;
String res = queue[head++];
return res;
}
}
这种方法有个明显的缺点，即进行对此的入队出队操作后，就无法继续添加数据。因此可以对入队操作进行优化。
方法2、
/**
* @author EnochStar
* @title: Queue
* @projectName basic_use
* @description: TODO
* @date 2021/10/17 16:46
*/
public class Queue {
private String[] queue;
private int capacity;
private int head;
private int tail;
public Queue(int capacity) {
this.capacity = capacity;
queue = new String[capacity];
head = 0;
tail = 0;
}
public boolean enqueue(String s){
if (tail == capacity && head == 0) return false;
else if (tail == capacity) {
for (int i = head;i < tail;i++) {
queue[i - head] = queue[i];
}
tail -= head;
head = 0;
}
queue[tail++] = s;
return true;
}
public String dequeue() {
if (head == tail) return null;
String res = queue[head++];
return res;
}
}
由摊还分析法可知，该平均时间复杂度为O（1），但最坏时间复杂度为O(1)
方法3、
采取循环队列的思路。
/**
* @author EnochStar
* @title: Queue
* @projectName basic_use
* @description: TODO
* @date 2021/10/17 16:46
*/
public class Queue {
private String[] queue;
private int capacity;
private int head;
private int tail;
private int size;
public Queue(int capacity) {
this.capacity = capacity;
queue = new String[capacity];
head = 0;
tail = 0;
size = 0;
}
public boolean enqueue(String s){
if (size == capacity) {
return false;
}
queue[tail] = s;
tail = (tail + 1) % capacity;
size++;
return true;
}
public String dequeue() {
if (head == tail) return null;
String res = queue[head];
head = (head + 1) % capacity;
size--;
return res;
}
}
(图片有些许出入)
方法4、
基于链表实现队列
public class Queue {
private int capacity;
private int size;
private Node tail;
private Node head;
public Queue(int capacity) {
this.capacity = capacity;
size = 0;
}
public boolean enqueue(String s) {
if (size == capacity) return false;
if (head == null) {
head = new Node(s);
tail = head;
size++;
return true;
}
tail.next = new Node(s);
tail = tail.next;
size++;
return true;
}
public String dequeue() {
if (size == 0) return null;
String res = head.val;
head = head.next;
size--;
return res;
}
}
class Node {
public String val;
public Node next;
public Node(String val) {
this.val = val;
}
}
队列一般可用作线程池的阻塞队列，或是并发队列。因此如果采用数组去实现队列的话，需要选择合适的大小，以充分的利用系统资源。当队列容量过大时，会有过多的请求等待，而当队列容量过小时，会导致无法充分利用系统资源，最大化系统性能。
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
递归
实现递归的三大条件
- 一个问题的解可分为几个子问题的解
- 该问题和子问题，除了数据的规模不同外，解题思路完全相同
- 存在递归终止
递归需要注意的问题
1、警惕堆栈溢出。由于函数调用是依靠栈来存储临时变量的，当函数调用过深，数据规模过大时，就会有堆栈溢出的问题。
2、警惕重复计算。通常采用备忘录来解决这个问题。
3、递归代码中有很多函数调用，当函数调用数量较大时，也会有很大的时间成本。同时递归调用的本质是不断压栈和出栈的过程，故其空间复杂度也不低。关于时间复杂度的计算方法是：函数调用的次数 * 每次函数调用的操作次数。 可看博客：带你逐步分析递归算法的时间复杂度 - 知乎 (zhihu.com)
能否将递归代码改写为非递归？
递归调用本质是依靠栈来进行不断的入栈和出栈的操作，因此，笼统来讲是可以改写的。但没必要，因为大多数情况下，将递归改为非递归，对其时间复杂度的影响并不大，只是徒增了实现的复杂度。
实际项目中的递归是如何的
实际项目中不好用递归，因为不好解决递归栈的问题。
思考
对于递归深度很深，递归规模大的代码，有什么好的调试方法？
1、打印日志，发现递归值
2、结合条件断点进行调试。
插入、冒泡、选择
如何分析一个“排序算法”？
排序算法的执行效率
- 最好、最坏、平均时间复杂度。用于分析在有序度不同情况下，不同算法的性能比较。
- 时间复杂度的系数、常数、低阶。时间复杂度表示的是在数据规模n很大的时候增长趋势，因此会忽略系数、常数、低阶。但在数据规模小的时候，同一阶时间复杂度比较时，需要考虑这些因素。
- 比较和交换的次数。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如 果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。
排序算法的内存消耗
算法的内存消耗可用空间复杂度来度量。对于一些原地排序的排序算法，其时间复杂度为O(1)
排序算法的稳定性
即经过排序后，相同元素之间的顺序是不变的。为什么需要稳定性呢？可以考虑一种场景，当对一个订单进行排序，排序的要求为先根据金额进行排序，金额相同时再根据下单时间进行排序。
利用排序算法的稳定性，就可以先将数据根据下单时间排序，然后再根据金额排序。通过两次排序就可以达到这个要求。
冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一 个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
public void bubbleSort(int[] nums) {
for (int i = 0;i < nums.length;i++) {
boolean flag = false;
for (int j = i + 1;j < nums.length;j++) {
if (nums[j] < nums[i]) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
flag = true;
}
}
if (!flag) break;
}
}
由代码可知，冒泡排序只需要O(1)的空间复杂度，故是原地排序。每次都对相邻的数据进行比较，进而决定要不要交换位置，由此可知，冒泡排序是稳定的。现在分析冒泡排序的时间复杂度，当数据本身有序时，只需要进行一次冒泡排序即可，此时时间复杂度为O（1）。最差情况是需要进行n次的冒泡排序，此时时间复杂度为O(n^2)。
平均时间复杂度可通过有序度和逆序度来分析。有序度是数组中具有有序关系的元素对的个数。
对于一个倒序排列的数组，比如6，5，4，3，2，1，有序度是0；对于一个完全有序的数组，比如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15。我们把这种完全有序的数组的有序度叫作满有序度。
逆序度=满有序度-有序度，要排序的数组的初始状态是4，5，6，3，2，1 ，其中，有序元素对有(4，5) (4，6)(5，6)，所以有序度是3。n=6， 所以排序完成之后终态的满有序度为n*(n-1)/2=15。其逆序度为12，因此需要交换12次。
对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是0，所以要进行n(n-1)/2次交换。最好情况下，初始状态的有序度是n(n-1)/2，就不需要进行交换。我们可以取个中间值n(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。 换句话说，平均情况下，需要n(n-1)/4次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是O(n2)，所以平均情况下的时间复杂度就是O(n^2）。
插入排序
插入排序，即将数据插入已排序的顺序子数组中，是一个动态排序的过程。
插入排序也包括比较和移动两个操作，插入排序初始数据的移动操作是固定的，等于逆序度。
public void insertSort(int[] nums) {
for (int i = 1;i < nums.length;i++) {
int value = nums[i];
int j = i - 1;
for (;j >= 0;j--) {
if (nums[j] > value) {
nums[j+1] = nums[j];
}else{
break;
}
}
nums[j + 1] = value;
}
}
显然插入排序是原地排序，且是稳定的排序，对于有序的数组，每次只需要比较一次即可，时间复杂度为O（n），如果该数组是倒叙的话，那么每次需要迁移n次，时间复杂度为o(n2)，还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n2)。
选择排序
是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
public void selectSort(int[] nums) {
for (int i = 0;i < nums.length;i++) {
int minIndex = i;
int min = nums[i];
for (int j = i + 1;j < nums.length;j++) {
if (nums[j] < min) {
min = nums[j];
minIndex = j;
}
}
int tmp = nums[i];
nums[i] = min;
nums[minIndex] = tmp;
}
}
简单分析可知，其为原地排序，无论数组是否有序，其时间复杂度都为O(n^2)。它并非稳定排序，以数组[5,4,5,2,7]可知，在第一次查找最小值时，会将第1个5的位置放在第二个5的后面。
为什么插入排序会比冒泡排序更受欢迎？
根据代码实现来看
冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) {
// 交换 int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j];
// 数据移动
} else {
break;
}
可见，把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是K的数组进行排序。用冒泡排序，需要K次交换操作，每次需要3个赋值语句，所以交换操作总耗时就是3*K单位时间。而插入排序中数据移动操作只需要K个单位时间。
总结，思考
这三种排序算法，实现代码都非常简单，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，所以我们更倾向于时间复杂度为O(nlogn)的排序算法。
这几种排序算法，都是基于数组实现的。如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？
解答：前提，是否允许修改链表的节点value值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会 变大，插入排序系数会减小，选择排序无明显变化。
快速排序、归并排序
归并排序和快速排序都运用了分治的思想。分治即分而治之，将大问题分解成小问题，小问题解决了，大问题就解决了，是一种编程思想，通常使用递归实现，递归是一种编程技巧。
归并排序
归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
public void mergeSort(int[] nums,int left,int right){
if (left >= right) return;
int mid = ((right - left) >> 1) + left;
mergeSort(nums,left,mid);
mergeSort(nums,mid + 1,right);
mergeSort(nums,left,mid,right);
}
public void mergeSort(int[] nums,int left,int mid,int right) {
int[] tmp = new int[right - left + 1];
int l1 = left;
int l2 = mid + 1;
int index = 0;
while (l1 <= mid && l2 <= right) {
if (nums[l1] <= nums[l2]) {
tmp[index++] = nums[l1++];
}else{
tmp[index++] = nums[l2++];
}
}
while (l1 <= mid) {
tmp[index++] = nums[l1++];
}
while (l2 <= right) {
tmp[index++] = nums[l2++];
}
for (int i = 0;i < tmp.length;i++) {
nums[i + left] = tmp[i];
}
}
归并排序性能分析
1、归并排序是稳定的。其稳定的关键在于mergeSort(int[] nums,int left,int mid,int right)中，l1和l2的比较。
2、归并排序非原地排序。根据代码很容易得知，每次合并操作时需要申请额外的空间，合并完成后，该空间就会释放，他最多需要申请O（n）的空间，故空间复杂度为O（n）
3、归并排序的时间复杂度分析。已知对n个元素进行归并排序，需要分解的时间为O(n)，分解两个子数组排序的时间复杂度为O（n/2）,每次执行mergeSort(int[] nums,int left,int mid,int right)需要的时间复杂度为O(n).推导公式为：
T(n) = 2*T(n/2) + n = 2*(2*T(n/4) + n/2) + n
= 4*T(n/4) + 2*n = 4*(2*T(n/8) + n/4) + 2*n
= 8*T(n/8) + 3*n = 8*(2*T(n/16) + n/8) + 3*n
= 16*T(n/16) + 4*n ...... = 2^k * T(n/2^k) + k * n
当T(n/2^k) = 1时,k = log2n,代入T(n) = nlog2n.归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。
快速排序
快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。 我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。
public void quickSort(int[] arr,int begin,int end) {
if(end <= start) {
return;
}
int pivot = partition(arr,begin,end);
quickSort(arr,begin,pivot - 1);
quickSort(arr,pivot,end);
}
public int partition(int[] arr,int begin,int end) {
int pivot = end,counter = begin;
for(int i = begin;i < end;i++) {
if(arr[i] < arr[pivot]) {
int temp = arr[counter];
arr[counter] = arr[i];
arr[i] = temp;
counter++;
}
}
int temp = arr[pivot];
arr[pivot] = arr[counter];
arr[counter] = temp;
return counter;
}
快排与归并排序的区别：归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为O(nlogn)的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
快排性能分析
快排是原地排序，但非稳定，当数组分区平衡情况下，快排的时间复杂度为O（nlogn），当分区极不平衡情况下，快排的时间复杂度为O(n^2),平均时间复杂度为O(nlogn).
如何利用快排找到数组中第k大的数字
我们选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot，对数组A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。
如果p+1=K，那A[p]就是要求解的元素；如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间，我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理，如果K<p+1,就在A[0...p-1]区间查找。
第一次分区查找，我们需要对大小为n的数组执行分区操作，需要遍历n个元素。第二次分区查找，我们只需要对大小为n/2的数组执行分区操作，需要遍历n/2个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为1。
如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于2n-1。所以，上述解决思路的时间复杂度就为O(n)。
你可能会说，我有个很笨的办法，每次取数组中的最小值，将其移动到数组的最前面，然后在剩下的数组中继续找最小值，以此类推，执行K次，找到的数据不就是第K大元素了吗？
不过，时间复杂度就并不是O(n)了，而是O(K * n)。你可能会说，时间复杂度前面的系数不是可以忽略吗？O(K * n)不就等于O(n)吗？ 这个可不能这么简单地划等号。当K是比较小的常量时，比如1、2，那最好时间复杂度确实是O(n)；但当K等于n/2或者n时，这种最坏情况下的时间复杂度就是O(n2)了。
具体代码
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSort(nums,0,nums.length - 1,k);
}
public int quickSort(int[] nums,int start,int end,int k) {
int pivot = partition(nums,start,end);
if(pivot + 1 == k) {
return nums[pivot];
}else if(pivot + 1 < k) {
return quickSort(nums,pivot + 1,end,k);
}else{
return quickSort(nums,start,pivot - 1,k);
}
}
public int partition(int[] arr,int begin,int end) {
int pivot = end,counter = begin;
for(int i = begin;i < end;i++) {
if(arr[i] > arr[pivot]) {
int tmp = arr[counter];
arr[counter] = arr[i];
arr[i] = tmp;
counter++;
}
}
int tmp = arr[pivot];
arr[pivot] = arr[counter];
arr[counter] = tmp;
return counter;
}
}
思考
现在你有10个接口访问日志文件，每个日志文件大小约300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为1个 日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB，你有什么好的解决思路，能“快速”地将这10个日志文件合并吗？
解答：先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然 后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合 并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存。
线性排序
时间复杂度均为O(n),是非基于比较的排序
桶排序
将有序的数据放在有序的桶中，然后桶内进行排序。排序完后依次取出，即是有序的数据。
时间复杂度分析。假设有n个数据，将他们均匀的划分到m个桶中，然后桶内进行快速排序，那么桶内的数据为k = n/m，则桶内的时间复杂度为O(klogk),那么m个桶排序时的时间复杂度为O(m * klogk),当m的个数与n近似时，时间复杂度接近O(n)。
桶排序虽然时间复杂度比较好，但只适用于特定的场景。
- 能容易的划分为m个桶，且桶与桶间存在天然的大小顺序
- 数据在各个桶的分配比较均匀，如果分布不均匀的话，那么在极端情况下，数据都放入一个桶内，时间复杂度为O(nlogn)
- 桶排序适合外部排序，即数据存储在外部磁盘中，数据量比较大，且内存有限，无法将所有数据载入内存
桶排序的实现
package algorithm;
/**
* @author EnochStar
* @title: BucketSort
* @projectName basic_use
* @description: 桶排序
* @date 2021/10/28 16:15
*/
public class BucketSort {
public static void main(String[] args) {
int[] nums = new int[] {1,0,2,3,6,5,4};
BucketSort bucketSort = new BucketSort();
bucketSort.bucketSort(nums,3);
for (int i : nums) {
System.out.println(i);
}
}
/**
* @param arr 待排序数组
* @param bucketSize 每个桶中的数量
*/
public void bucketSort(int[] arr,int bucketSize){
if (arr.length < 2) return;
int maxNum = arr[0];
int minNum = arr[0];
// 找到最大最小值
for (int i = 1;i < arr.length;i++) {
if (arr[i] > maxNum) maxNum = arr[i];
if (arr[i] < minNum) minNum = arr[i];
}
int bucketNum = (maxNum - minNum) / bucketSize + 1;
int[][] bucket = new int[bucketNum][bucketSize];
// 每个桶下对应的下标
int[] indexArr = new int[bucketNum];
// 将值填充入桶中
for (int i : arr) {
int bucketIndex = (i - minNum) / bucketSize;
if (indexArr[bucketIndex] == bucket[bucketIndex].length) {
ensureCapacity(bucket,bucketIndex);
}
bucket[bucketIndex][indexArr[bucketIndex]++] = i;
}
int k = 0;
// 对桶内数据进行排序
for (int i = 0;i < bucketNum;i++) {
quickSort(bucket[i],0,indexArr[i] - 1);
for (int j = 0;j < indexArr[i];j++) {
arr[k++] = bucket[i][j];
}
}
}
// 数组扩容
public void ensureCapacity(int[][] bucket,int bucketIndex) {
int[] newArr = new int[bucket[bucketIndex].length * 2];
for (int i = 0;i < bucket[bucketIndex].length;i++) {
newArr[i] = bucket[bucketIndex][i];
}
bucket[bucketIndex] = newArr;
}
public void quickSort(int[] arr,int begin,int end) {
if (end <= begin) return;
int pivot = partition(arr,begin,end);
quickSort(arr,begin,pivot - 1);
quickSort(arr,pivot,end);
}
public int partition(int[] arr,int begin,int end) {
int count = begin;
int pivot = end;
for (int i = begin;i < end;i++) {
if (arr[i] < arr[pivot]) {
int tmp = arr[i];
arr[i] = arr[count];
arr[count++] = tmp;
}
}
int tmp = arr[pivot];
arr[pivot] = arr[count];
arr[count] = tmp;
return count;
}
}
计数排序
计数排序是一种特殊的桶排序，适用于数据量不大的情况下，省去了排序的时间，比如高考成绩排名，多个人会处于同一个分数。
实现
package algorithm;
/**
* @author EnochStar
* @title: CountSort
* @projectName basic_use
* @description: 计数排序
* @date 2021/10/28 15:12
*/
public class CountSort {
public static void main(String[] args) {
int[] score = new int[] {1,0,2,3,4,5,1,0};
int[] sort = countSort(score);
for (int i : sort) {
System.out.println(i);
}
}
public static int[] countSort(int[] nums) {
int maxNum = 0;
for (int i = 0;i < nums.length;i++) {
if (nums[i] > maxNum)
maxNum = nums[i];
}
int[] tmp = new int[maxNum + 1];
for (int num : nums) {
tmp[num]++;
}
for (int i = 1;i < maxNum + 1;i++) {
tmp[i] += tmp[i - 1];
}
int[] sort = new int[nums.length];
for (int i = nums.length - 1;i >= 0;i--) {
int index = tmp[nums[i]] - 1;
sort[index] = nums[i];
tmp[nums[i]]--;
}
return sort;
}
}
基数排序
假设有100000个手机号码，希望对该手机号码进行排序，显然以上两种排序方法都不适用，而快排的时间复杂度为O(nlogn),那么能否有更有效的排序方法？可以利用排序的稳定性来解决这个问题，依次对每个手机号的某一位进行排序，利用了计数排序。假设手机号码的长度为k，计数排序的时间复杂度为O(n)，则总的时间复杂度为O(K*N)。
package algorithm;
/**
* @author EnochStar
* @title: RadixSort
* @projectName basic_use
* @description: 基数排序
* @date 2021/10/28 16:56
*/
public class RadixSort {
public static void main(String[] args) {
int[] nums = new int[] {201101,201102,101105,201103,201104};
radixSort(nums);
for (int i : nums) {
System.out.println(i);
}
}
public static void radixSort(int[] nums) {
int maxNum = nums[0];
for (int i : nums) {
if (i > maxNum) {
maxNum = i;
}
}
for (int exp = 1;maxNum / exp > 0;exp *= 10) {
countingSort(nums,exp);
}
}
public static void countingSort(int[] nums,int exp) {
int[] count = new int[10];
for (int i = 0;i < nums.length;i++) {
count[(nums[i] / exp) % 10]++;
}
for (int i = 1;i < count.length;i++) {
count[i] += count[i - 1];
}
int[] r = new int[nums.length];
for (int i = nums.length - 1;i >= 0;i--) {
int index = count[(nums[i] / exp) % 10] - 1;
r[index] = nums[i];
count[(nums[i] / exp) % 10]--;
}
for (int i = 0;i < nums.length;i++) {
nums[i] = r[i];
}
}
}
思考
假设我们现在需要对D，a，F，B，c，A，z这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么解决呢？
答：可以利用桶排序，设置三个桶分别处理小写字母，数字，大写字母，各个桶根据自己的排序规则进行排序，再遍历读取。
二分查找(基础)
时间复杂度O(logn)
二分查找每次查找后数据的范围就会变成原来的一半n,n/2,n/4...n/2^k,当n/2^k == 1时，k=logn，时间复杂度为O(k)
二分查找的实现（递归与非递归）
非递归
public int binarySearch(int[] nums,int key) {
int left = 0;
int right = nums.length-1;
while (left <= right) {
int mid = ((right - left) >>> 1) + left;
if (nums[mid] == key) return mid;
else if (nums[mid] > key)
right = mid - 1;
else {
left = mid + 1;
}
}
return -1;
}
递归
public int binarySearchReverse(int[] nums,int key) {
int left = 0;
int right = nums.length - 1;
return binarySearchReverse(nums,key,left,right);
}
public int binarySearchReverse(int[] nums,int key,int left,int right) {
if (left > right) return - 1;
int mid = ((right - left) >>> 1) + left;
if (nums[mid] == key) return mid;
else if (nums[mid] > key) return binarySearchReverse(nums,key,left,mid - 1);
else {
return binarySearchReverse(nums,key,mid + 1,right);
}
}
二叉查找应用场景
- 依赖于数组这一数据结构，因为数组支持随机访问，如果底层数据结构是链表的话，那么时间复杂度还是很高
- 二叉查找针对的是有序数据
- 数据量过少不适合二叉查找
- 数据量过大也不适合用二叉查找，因为二叉查找底层数据结构是数组，数组要求有连续的内存空间
思考
1、不用API，如何求一个数的平方根（可舍弃小数点） 2、如果二叉查找应用到有序链表上，那么它的时间复杂度是多少？
解答：
1、剑指 Offer II 072. 求平方根 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int mySqrt(int x) {
long left = 0;
long right = x;
while(left <= right) {
long mid = left + ((right - left) >>> 1);
long num = mid * mid ;
if(num == x) {
return (int)mid;
}else if(num > x) {
right = mid - 1;
}else{
left = mid + 1;
}
}
return (int)right;
}
}
2、当底层是双向链表时，则每次迁移数据的二分之一，n/2 + n / 4 + n / 8 + ... + 1 = n - 1 时间复杂度为O(n)
二分查找（进阶）
查找第一个值等于给定值的元素
public int bsearch(int[] nums,int key) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = ((r - l) >>> 1) + l;
if (nums[mid] > key) {
r = mid - 1;
}else if (nums[mid] < key) {
l = mid + 1;
}else{
if (nums[mid - 1] != key) {
return mid;
}
r = mid - 1;
}
}
return -1;
}
查找最后一个值大于等于给定值的元素
public int bsearchII(int[] nums,int key) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = ((r - l) >>> 1) + l;
if (nums[mid] >= key) {
if (nums[mid - 1] < key) return mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
return -1;
}
大部分情况下，凡是二分查找能解决的都会采用散列表或者二叉查找树来解决，因为内存紧缺的情况并不多，二分查找通常用于以上的变体问题。
思考
如果有序数组是一个循环有序数组，比如4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢?
解：33. 搜索旋转排序数组 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while(l <= r) {
int mid = ((r - l) >>> 1) + l;
if(nums[mid] == target) return mid;
if(nums[mid] >= nums[l]) {
if(target < nums[mid] && target >= nums[l]) {
r = mid - 1;
}else{
l = mid + 1;
}
}else{
if(target > nums[mid] && target <= nums[r]) {
l = mid + 1;
}else{
r = mid - 1;
}
}
}
return -1;
}
}