企业官网建设流程全解析

#例1《快速排序》#

#include<iostream> using namespace std; void swap(int &a,int &b){//交换函数 int t=a; a=b; b=t; return;//void可直接返回 } void quickSort(int a[],int left,int right){//传入数组，左右边界，可拓展为vector容器 if(left>=right)return;//处理边界问题 int i=left,j=right,pivot=a[left];//取left为基准值可以减小极端情况的影响 while(i<j){//i>=j时弹出，否则交换受影响 while(i<j && a[i]<=pivot)i++; while(i<j && a[j]>=pivot)j--; if(i<j)swap(a[i],a[j]); } swap(a[left],a[i]);//把基准值放在排序好的位置上 quickSort(a,left,i-1); quickSort(a,i+1,right); return;//直接返回 }

#快排优化版本#

相当于是每次把val=vec[i]放在排序好的位置上。

int partation(vector<int> &vec,int i ,int j){//基准值与排序步骤 int val=vec[i],l=i,r=j; if（j-i<=50）InsertSort(vec,i,j);#快排在最差情况下会退化到O（n**2）时间复杂度 #插入排序的效率在数组有序的时候效率最高 while(l<r){ while(l<r && vec[r]>=val)r--;//要小于等于，否则容易卡死 if(l<r)vec[l++]=vec[r];//也可以写成vec[l]=vec[r];r--; while(l<r && vec[l]<=val)l++; if(l<r)vec[r--]=vec[l]; } vec[l]=val;//把基准值放在排序好的位置 return l;//返回基准位置，便于下一步操作 }

void quickSort(vector<int> &vec,int i, int j){ if(i>=j)return; int pos=partation(vec,i,j); quickSort(vec,i,pos-1); quickSort(vec,pos+1,j); return; }

#例2求TOPk（分治做法）#

int di_TOPk_big(vector<int> &vec, int i,int j,int k){ int pos=partation(vec,i,j); if(pos==vec.size()-k)return pos; else if(pos<vec.size()-k)return di_TOPk_big(vec,pos+1,j,k); else if(pos>vec.size()-k)return di_TOPk_big(vec,i,pos-1,k); }

#归并排序（分-治-合）#

1. 时间复杂度：O(n log n)。无论输入数据是否有序，时间复杂度都稳定（拆分过程是log n层，每层合并操作是O(n)）。
2. 空间复杂度：O(n)。需要临时数组tmp存储合并结果。
3. 稳定性：稳定排序。当两个元素相等时（a[i] <= a[j]），优先保留左子数组的元素，不会改变相等元素的相对顺序。
4. 适用场景：适合大规模数据排序（尤其是外部排序，如磁盘文件排序），但因需要额外空间，小规模数据可能不如插入排序高效。

#include<iostream> using namespace std; int a[1001], tmp[1001]; void mergesort(int l, int r) { if (l >= r)return; int mid = (l + r) / 2; mergesort(l, mid); mergesort(mid + 1, r); merge(l, mid, r); }

归并排序伪代码实现：

传入参数：l（左边界）、r（右边界）

设置退出条件：（l>=r）退出

设置中间的划分坐标：mid=(l+r)/2

划分区间左边是l-mid；

右边则是mid+1-r；

设置合并区间：实际上利用了tmp数组来存放排序好的数组，所以需要同等空间大小的数组

递归的逻辑：每次调用函数都会开辟一个栈空间，不断调用函数到最小，也就是可以解决问题的时候就开始回溯，后一个问题解决完了就解决前一个问题。所以就是从大划分到小，再从小到大解决，等都解决好才会释放空间。

流程就是：先不断划分成小区间，划分到最小区间的时候（不执行mergesort函数）就开始合并，合并好的部分存放在tmp数组中，tmp的坐标区间和原数组是一样的。小的部分排序好了就会一步步解决更大的待排序函数。

void merge(int l, int mid, int r) { int i = l, j = mid + 1, k = l; 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++]; for (int i = l; i <= r; i++)a[i] = tmp[i]; }

拟合并数组(a)：

0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9

[ l mid ][ mid+1 r ]

i j

tmp: k=l;

如果（nums[i]<=nums[j]）{把nums[i]放在tmp[k]的位置，随后i++，k++}

否则{把nums[j]放在tmp[k]的位置，随后j++，k++}

上面两个区间有一方分配完就退出循环，把另一方的剩余元素直接补在k的末尾，

然后就排序好tmp数组【l到r】区间的元素了，这时候在再把tmp数组【l到r区间】传给a数组

由此就排序好一个区间了。

非递归归并排序

原理：把原来的数组已经看作是分到了最小的区间，每个区间只有一个元素，开始合并。

合并的时候从步长为1开始处理整个数组，处理边界问题：如果右边界超过了数组长度，就把右边界定位最大数组长度，如果左数组超过了数组长度，那么本次无需合并，它原本就是已经排序好的。不断循环，每次步长是原来的两倍，并且不超过数组最大下标，最大步长不超过数组长度，在大于数组长度一半的时候就已经是合二为一的最后一次合并了。

void mergeSort(int n) { for (int step = 1; step < n; step *= 2) { // 步长从1开始，每次翻倍 for (int i = 1; i <= n; i += 2 * step) { // 每次处理两个step长度的子数组 int l = i; int mid = i + step - 1; int r = i + 2 * step - 1; if (r > n) r = n; // 右边界不超过数组长度 if (mid > n) continue; // 左子数组越界，无需合并 merge(l, mid, r); } } }

力扣题目：

寻找两个正序数组的中位数

#include <vector> #include <climits> // 包含 INT_MIN 和 INT_MAX using namespace std; class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { // 确保 nums1 是较短的数组，优化二分查找效率 if (nums1.size() > nums2.size()) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.size(); int n = nums2.size(); int left = 0, right = m; // 二分查找 nums1 的分割点范围 while (left <= right) { // i 是 nums1 左侧的元素个数（分割点） int i = (left + right) / 2; // j 是 nums2 左侧的元素个数（总左侧元素为 (m+n+1)/2，确保左侧比右侧多1个当总数为奇数时） int j = (m + n + 1) / 2 - i; // 处理边界情况：左侧无元素时用 INT_MIN 表示 int left1 = (i == 0) ? INT_MIN : nums1[i - 1]; int left2 = (j == 0) ? INT_MIN : nums2[j - 1]; // 处理边界情况：右侧无元素时用 INT_MAX 表示 int right1 = (i == m) ? INT_MAX : nums1[i]; int right2 = (j == n) ? INT_MAX : nums2[j]; // 找到有效分割点：左侧所有元素 <= 右侧所有元素 if (left1 <= right2 && left2 <= right1) { // 总长度为奇数时，中位数是左侧最大值 if ((m + n) % 2 == 1) return max(left1, left2); // 总长度为偶数时，中位数是左侧最大值和右侧最小值的平均 else return (max(left1, left2) + min(right1, right2)) / 2.0; } // 左侧过大，需要减少 nums1 的左侧元素 else if (left1 > right2) right = i - 1; // 左侧过小，需要增加 nums1 的左侧元素 else left = i + 1; } return 0.0; } };