数据结构和算法
1、⼗⼤排序算法及其时间和空间复杂度
（1）冒泡排序算法描述：
⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换它们两个；
对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对，这样在最后的元素应该会是最⼤的数；
针对所有的元素重复以上的步骤，除了最后⼀个；
重复步骤 1~3，直到排序完成。
⽤⼀个例⼦，带你看下冒泡排序的整个过程。我们要对⼀组数据 4，5，6，3，2，1，从⼩到到⼤进⾏排序。第⼀次冒泡操作的详细过程就是这样
可以看出，经过⼀次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进⾏ 6 次这样的冒泡操作就⾏了。
下⾯代码中std::swap函数的源代码如下，可以看到有三个赋值操作:
template<classT>
voidswap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
voidBubbleSort(std::vector<int> &nums, int n) {
if (n <= 1) return;
bool is_swap;
for (int i = 1; i < n; ++i) {
is_swap = false;//设定⼀个标记，若为false，则表示此次循环没有进⾏交换，也就是待排序列已经有序，排序已经完成。
for (int j = 1; j < n - i + 1; ++j) {
if (nums[j] < nums[j-1]) {
std::swap(nums[j], nums[j-1]);is_swap = true;//表示有数据交换
}
}if (!is_swap) break;//没有数据交集，提前退出
}
}
intmain() {
int a[] = {34,66,2,5,95,4,46,27};
BubbleSort(a,sizeof(a)/sizeof(int)); //cout => 2 4 5 27 34 46 66 95
return0;
}（2）插⼊排序算法描述：分为已排序和未排序初始已排序区间只有⼀个元素就是数组第⼀个遍历未排序的每⼀个元素在已排序区间⾥找到合适的位置插⼊并保证数据⼀直有序。
voidInsertSort(std::vector<int> &nums,int n) {
if (n <= 1) return;
for(int i = 0; i < n; ++i) {
for (int j = i; j > 0 && nums[j] < nums [j-1]; --j) {
std::swap(nums[j],nums[j-1]);
}
}
}
intmain() {
std::vector<int> nums = {4,6,5,3,2,1};
InsertSort(nums,6);//cout => 1,2,3,4,5,6
return0;
}（3）选择排序算法描述：分已排序区间和未排序区间。每次会从未排序区间中找到最⼩的元素，将其放到已排序区间的末尾。
voidSelectSort(std::vector<int> &nums, int n) {
if (n <= 1) return;
int mid;
for (int i = 0; i < n - 1; ++i) {
mid = i;
for (int j = i + 1; j < n; ++j) {
if (nums[j] < nums[mid]) {
mid = j;
}
}
std::swap(nums[mid],nums[i]);
}
}
intmain() {
std::vector<int> nums = {4,6,5,3,2,1};
SelectSort(nums,6);//cout => 1,2,3,4,5,6
return0;
}【时间,空间复杂度/是否稳定？】⾸先，选择排序空间复杂度为 O(1)，是⼀种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n )。你可以⾃⼰来分析看看。
那选择排序是稳定的排序算法吗？答案是否定的，选择排序是⼀种不稳定的排序算法。从图中，你可以看出来，选择排序每次都要找剩余未排序元素中的最⼩值，并和前⾯的元素交换位置，这样破坏了稳定性【思考】冒泡排序和插⼊排序的时间复杂度都是 O(n )，都是原地排序算法，为什么插⼊排序要⽐冒泡排序更受欢迎呢？
【思路】冒泡排序不管怎么优化，元素交换的次数是⼀个固定值，是原始数据的逆序度。插⼊排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码实现上来看，冒泡排序的数据交换要⽐插⼊排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，⽽插⼊排序只需要 1 个。把执⾏⼀个赋值语句的时间粗略地计为单位时间，处理相同规模的数，插⼊排序⽐冒泡排序减少三倍的单位时间！
（4）快排算法描述：先找到⼀个枢纽；在原来的元素⾥根据这个枢纽划分⽐这个枢纽⼩的元素排前⾯；⽐这个枢纽⼤的元素排后⾯；两部分数据依次递归排序下去直到最终有序。
⼿撕快排讲解：https://www.bilibili.com/video/BV1mE411M7SH
voidQuickSort(std::vector<int> &nums,int l,int r) {
if (l + 1 >= r) return;
int first = l, last = r - 1 ,key = nums[first];
while (first < last) {while (first < last && nums[last] >= key) last--;//右指针从右向左扫描将⼩于piv的放到左边
nums[first] = nums[last];while (first < last && nums[first] <= key) first++;//左指针从左向右扫描将⼤于piv的放到右边
nums[last] = nums[first];
}nums[first] = key;//更新pivquick_sort(nums, l, first);//递归排序 //以L为中间值，分左右两部分递归调⽤
quick_sort(nums, first + 1, r);
}
intmain() {
int a[] = {0,34,66,2,5,95,4,46,27};
QuickSort(a, 0, sizeof(a)/sizeof(int));
for(int i=0; i<=8; ++i) {
std::cout<<a[i]<<" "; // print => 0 2 4 5 27 34 46 66 95
}
std::cout<<endl;
return0;
}（5）归并排序算法描述：归并排序是⼀个稳定的排序算法，归并排序的时间复杂度任何情况下都是O(nlogn)，归并排序不是原地排序算法⽤两个游标 i 和 j，分别指向 A[p…q] 和 A[q+1…r] 的第⼀个元素。⽐较这两个元素 A[i] 和A[j]，如果 A[i]<=A[j]，我们就把 A[i] 放⼊到临时数组 tmp，并且 i 后移⼀位，否则将 A[j] 放⼊到数组 tmp，j 后移⼀位。
voidmergeCount(int a[],int L,int mid,int R) {
int*tmp = newint[L+mid+R];
int i=L;
int j=mid+1;
int k=0;
while( i<=mid && j<=R ) {
if(a[i] < a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}///判断哪个⼦数组中有剩余的数据
while( i<=mid )
tmp[k++] = a[i++];
while( j<=R)
tmp[k++] = a[j++];/// 将 tmp 中的数组拷⻉回 A[p...r]
for(int p=0; p<k; ++p)
a[L+p] = tmp[p];
delete tmp;
}
voidmergeSort(int a[],int L,int R) {///递归终⽌条件分治递归/// 将 A[L...m] 和 A[m+1...R] 合并为 A[L...R]
if( L>=R ) { return; }
int mid = L + (R - L)/2;
mergeSort(a,L,mid);
mergeSort(a,mid+1,R);
mergeCount(a,L,mid,R);
}
intmain() {
int a[] = {0,34,66,2,5,95,4,46,27};
mergeSort(a, 0, sizeof(a)/sizeof(int));
for(int i=0; i<=8; ++i) {
std::cout<<a[i]<<" "; // print => 0 2 4 5 27 34 46 66 95
}
std::cout<<endl;
return0;
}（6）堆排序算法描述：利⽤堆这种数据结构所设计的⼀种排序算法。堆积是⼀个近似完全⼆叉树的结构，并同时满⾜堆积的性质：即⼦结点的键值或索引总是⼩于（或者⼤于）它的⽗节点。堆排序可以⽤到上⼀次的排序结果，所以不像其他⼀般的排序⽅法⼀样，每次都要进⾏ n-1 次的⽐较，复杂度为O(nlogn)。
算法步骤：
1、利⽤给定数组创建⼀个堆 H[0..n-1]（我们这⾥使⽤最⼩堆），输出堆顶元素
2、以最后⼀个元素代替堆顶，调整成堆，输出堆顶元素
3、把堆的尺⼨缩⼩ 1
4、重复步骤 2，直到堆的尺⼨为 1
建堆：将数组原地建成⼀个堆，不借助额外的空间，采⽤从上往下的堆化（对于完全⼆叉树来说，下标是 n/2+1 到 n 的节点都是叶⼦节点，不需要堆化）。
排序：”删除堆顶元素“：当堆顶元素移除之后，把下标为 n 的元素放到堆顶，然后在通过堆化的⽅法，将剩下的 n - 1 个元素重新构建成堆，堆化完成之后，在取堆顶的元素，放到下标为n-1 的位置，⼀直重复这个过程，直到最后堆中只剩下标 1 的⼀个元素。
/*优点：O(nlogn)，原地排序，最⼤的特点：每个节点的值⼤于等于(或⼩于等于)其⼦树节点缺点：相⽐于快排，堆排序数据访问的⽅式没有快排友好；数据的交换次数要多于快排。
*/
voidHeapSort(int a[], int n) {
for(int i=n/2; i>=1; --i) {
Heapify(a, n, i);
}
int k = n;
while( k > 1) {
swap(a[1],a[k]);
--k;
Heapify(a,k,1);
}
}
voidHeapify(int a[], int n, int i) {
while (1) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) { maxPos = i*2; }
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) { maxPos = i*2+1; }
if (maxPos == i) break;
std::swap(a[i], a[maxPos]);
i = maxPos;
}
}
void（7）桶排序算法描述：将数组分到有限数量的桶⾥。每个桶再个别排序（有可能再使⽤别的排序算法或是以递归⽅式继续使⽤桶排序进⾏排序）。
voidbucketSort(std::vector<int>& nums) {
if (nums.empty()) return ;
int low = *std::min_element(nums.begin(), nums.end());
int high = *std::max_element(nums.begin(), nums.end());
int n = high - low + 1;
std::vector<int> buckets(n);
std::vector<int> res;
for (auto x : nums) ++buckets[x - low];for (int i = 0; i < n; ++i) { //实现了按桶下标从⼩到达输出for (int j = 0; j < buckets[i]; ++j) { //重复的输出
res.push_back(i + low);
}
}
for (int i=0; i<res.size(); ++i) {
std::cout<<res[i]<<" ";
}
}（8）计数排序扩展：如果在⾯试中有⾯试官要求你写⼀个 O(n) 时间复杂度的排序算法，可不要傻乎乎的说这不可能！虽然前⾯基于⽐较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满⾜⼀定的范围的整数，⽽且计数排序需要⽐较多的辅助空间。
算法描述：其基本思想是，⽤待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
假设有 8 个考⽣，分数在 0 到 5 分之间。这 8 个考⽣的成绩我们放在⼀个数组 A[8]中，它们分别是：2，5，3，0，2，3，0，3。
考⽣的成绩从 0 到 5 分，我们使⽤⼤⼩为 6 的数组 C[6]表示桶，其中下标对应分数。不过，C[6]内存储的并不是考⽣，⽽是对应的考⽣个数。像我刚刚举的那个例⼦，我们只需要遍历⼀遍考⽣分数，就可以得到 C[6]的值。
这是我们的数组，从图中可以看出，分数为 3 分的考⽣有 3 个，⼩于 3 分的考⽣有 4 个，所以，成绩为 3 分的考⽣在排序之后的有序数组 R[8]中，会保存下标 4，5，6 的位置。
那我们如何快速计算出，每个分数的考⽣在有序数组中对应的存储位置呢？
我们对 C[6] 数组顺序求和，C[6]存储的数据就变成了下⾯这样⼦。C[k]⾥存储⼩于等于分数 k的考⽣个数。
我们从后到前依次扫描数组 A。⽐如，当扫描到 3 时，我们可以从数组 C 中取出下标为 3 的值 7，也就是说，到⽬前为⽌，包括⾃⼰在内，分数⼩于等于 3 的考⽣有 7 个，也就是说 3是数组 R 中的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放⼊到数组 R 中后，⼩于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3]要减 1，变成 6。
以此类推，当我们扫描到第 2 个分数为 3 的考⽣的时候，就会把它放⼊数组 R 中的第 6 个元素的位置（也就是下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从⼩到⼤有序排列的了。
注意：计数排序只能⽤在数据范围不⼤的场景中，如果数据范围 k ⽐要排序的数据 n ⼤很多，就不适合⽤计数排序了。⽽且，计数排序只能给⾮负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对⼤⼩的情况下，转化为⾮负整数。
voidcountSort(int*a,int n){
int maxV=a[0];
for(int i=1; i<n; ++i){
maxV=max(maxV,a[i]);
}
int c[maxn];
memset(c,0,sizeof(c));
for(int i=0; i<n; ++i){
c[a[i]]++;
}
for(int i=1; i<=maxV; ++i){
c[i]+=c[i-1];
}
int r[maxn];
memset(r,0,sizeof(r));
for(int i=n-1; i>=0; --i){
int index = c[a[i]]-1;
r[index]=a[i];
c[a[i]]--;
}
for(int i=0; i<n; ++i){
a[i]=r[i];
}
}（9）基数排序算法描述：基数排序对要排序的数据是有要求的，需要可以分割出独⽴的“位”来⽐较，⽽且位之间有递进的关系，如果 a 数据的⾼位⽐ b 数据⼤，那剩下的低位就不⽤⽐较了。除此之外，每⼀位的数据范围不能太⼤，要可以⽤线性排序算法来排序，否则，基数排序的时间复杂度就⽆法做到 O(n) 了。
基数排序相当于通过循环进⾏了多次桶排序。
intgetDigit(int x,int d){
int t[]={1,1,10,100};
return (x/t[d])%10;
}
voidRadixSort(int*a,int begin,int end,int d){
constint radix = 10;
int c[maxn];
int bucket[maxn];
for(int k=1; k<=d; ++k){
memset(c,0,sizeof(c));
for(int i=begin; i<=end; ++i){c[getDigit(a[i],k)]++;//计算i号桶⾥要放多少数
}
for(int i=1; i<radix; ++i) c[i]+=c[i-1];// 把数据依次装⼊桶（注意：装⼊时的分配技巧）
for(int i=end; i>=begin; --i){int j=getDigit(a[i],k);//求出关键码的第k位的数值，例如：576的第3位是5bucket[c[j]-1]=a[i];//放⼊对应的桶中(count[j]-1)表示第k位数值为j的桶底索引
--c[j];//当前第k位数值为j的桶底边界索引减⼀
}for(int i=begin,j=0;i<=end;++i,++j){// 从各个桶中收集数据
a[i]=bucket[j];
}
}
}（10）希尔排序算法描述：通过将⽐较的全部元素分为⼏个区域来提升插⼊排序的性能。这样可以让⼀个元素可以⼀次性地朝最终位置前进⼀⼤步。然后算法再取越来越⼩的步⻓进⾏排序，算法的最后⼀步就是普通的插⼊排序，但是到了这步，需排序的数据⼏乎是已排好的了。
// 希尔排序
voidshellSort(vector<int>& nums) {
for (int gap = nums.size() / 2; gap > 0; gap /= 2) {
for (int i = gap; i < nums.size(); ++i) {
for (int j = i; j - gap >= 0 && nums[j - gap] > nums[j]; j -= gap)
{
swap(nums[j - gap], nums[j]);
}
}
}
}2、⼆叉树前中后遍历⼿撕代码（递归和⾮递归）
LeetCode 144. ⼆叉树的前序遍历难度简单609给你⼆叉树的根节点root，返回它节点值的前序遍历。
示例 1：
输⼊：root = [1,null,2,3]输出：[1,2,3]
示例 2：输⼊：root = []输出：[]
示例 3：输⼊：root = [1]输出：[1]
【思路】由于“中左右”的访问顺序正好符合根结点寻找⼦节点的顺序，因此每次循环时弹栈，输出此弹栈结点并将其右结点和左结点按照叙述顺序依次⼊栈。⾄于为什么要右结点先⼊栈，是因为栈后进先出的特性。右结点先⼊栈，就会后输出右结点。
初始化：⼀开始让root结点先⼊栈，满⾜循环条件
步骤：弹栈栈顶元素，同时输出此结点当前结点的右结点⼊栈当前结点的左结点⼊栈重复上述过程结束条件：
每次弹栈根结点后⼊栈⼦结点，栈为空时则说明遍历结束。
【代码】//递归版
/* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x),
left(left), right(right) {}
* };
*/
classSolution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {// 为空则直接返回
if(root == NULL)
return ans;
ans.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return ans;
}
}//⾮递归
classSolution {
public:
std::vector<int>preorderTraversal(TreeNode* root) {
std::vector<int>res;
if (!root) return res;
stack<TreeNode*> st;
TreeNode* node = root;
while (!st.empty() || node) {
while(node) {
st.push(node);
res.push_back(node->val);
node = node->left;
}
node = st.top();
st.pop();
node = node->right;
}
return res;
}
};LeetCode 94. ⼆叉树的中序遍历难度简单1035给定⼀个⼆叉树的根节点root，返回它的中序遍历。
示例 1：
输⼊：root = [1,null,2,3]输出：[1,3,2]
示例 2：输⼊：root = []输出：[]
示例 3：输⼊：root = [1]输出：[1]
示例 4：
输⼊：root = [1,2]输出：[2,1]
示例 5：
输⼊：root = [1,null,2]输出：[1,2]
【思路】中序遍历思路相较于前序遍历有很⼤的改变。前序遍历遇到根结点直接输出即可，但中序遍历“左中右”需先找到此根结点的左结点，因此事实上第⼀个被输出的结点会是整个⼆叉树的最左侧结点。
依据这⼀特性，我们每遇到⼀个结点，⾸先寻找其最左侧的⼦结点，同时⽤栈记录寻找经过的路径结点，这些是输出最左侧结点之后的返回路径。
之后每次向上层⽗结点返回，弹栈输出上层⽗结点的同时判断此结点是否含有右⼦结点，如果存在则此右结点⼊栈并到达新的⼀轮循环，对此右结点也进⾏上述操作。
初始化：
curr定义为将要⼊栈的结点，初始化为roottop定义为栈顶的弹栈结点步骤：
寻找当前结点的最左侧结点直到curr为空（此时栈顶结点即为最左侧结点）弹栈栈顶结点top并输出判断top是否具有右结点，如果存在则令curr指向右结点，并在下⼀轮循环⼊栈重复上述过程结束条件：这⾥可以看到结束条件有两个：栈为空，curr为空。这是因为中序遍历优中后右的特性，会有⼀个时刻栈为空但右结点并未被遍历，因此只有在curr也为空证明右结点不存在的情况下，才能结束遍历。
【代码】
/*** Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x),
left(left), right(right) {}
* };
*///递归法
// class Solution {
// public:
// std::vector<int> ret;
// vector<int> inorderTraversal(TreeNode* root) {
// postOrder(root);
// return ret;
// }
// void postOrder(TreeNode* root) {
// if (root == nullptr) return;
// inorderTraversal(root->left);
// ret.push_back(root->val);
// inorderTraversal(root->right);
// }
// };//迭代法
classSolution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
TreeNode* curr = root;
while(!stk.empty() || curr != NULL) {// 找到节点的最左侧节点，同时记录路径⼊栈
while(curr != NULL) {
stk.push(curr);
curr = curr->left;
}// top 定义是此刻的弹栈元素
TreeNode* top = stk.top();
ans.push_back(top->val);
stk.pop();// 处理过最左侧结点后，判断其是否存在右⼦树
if(top->right != NULL)
curr = top->right;
}
return ans;
}
};LeetCode 145. ⼆叉树的后序遍历难度简单630给定⼀个⼆叉树，返回它的后序遍历。
示例:输⼊: [1,null,2,3]
1
\
2
/
3输出: [3,2,1]
进阶:递归算法很简单，你可以通过迭代算法完成吗？
【思路】1、前序遍历的过程是中左右。
2、将其转化成中右左。也就是压栈的过程中优先压⼊左⼦树，再压⼊右⼦树。
3、在弹栈的同时将此弹栈结点压⼊另⼀个栈，完成逆序。
4、对新栈中的元素直接顺序弹栈并输出。
【代码】
/*** Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x),
left(left), right(right) {}
* };
*/
/*//递归版
class Solution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {// 为空则直接返回
if(root == NULL)
return ans;
preorderTraversal(root->left);
preorderTraversal(root->right);
ans.push_back(root->val);
return ans;
}
};
*///⾮递归版
classSolution {
public:
std::vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
if (!root) return res;
std::stack<TreeNode*> st1;
std::stack<TreeNode*> st2;
st1.push(root);// 栈⼀顺序存储
while (!st1.empty()){
TreeNode* node = st1.top();
st1.pop();
st2.push(node);
if (node->left) st1.push(node->left);
if (node->right) st1.push(node->right);
}// 栈⼆直接输出
while (!st2.empty()) {
res.push_back(st2.top()->val);
st2.pop();
}
return res;
}
};