文章目录
前置知识
插入排序
- 插入排序 步骤：
1.从第一个元素开始，该元素可以认为已经被排序
2.取下一个元素tem，从已排序的元素序列从后往前扫描
3.如果该元素大于tem，则将该元素移到下一位
4.重复步骤3，直到找到已排序元素中小于等于tem的元素
5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
6.重复步骤2~5
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的
归并排序的核心：分治
归并排序与插入排序对比
基础的二路归并(c++)
//基础的二路归并
//核心思想：划分为两个子问题
//左边处理一下，得到左边的信息
//右边处理一下，得到右边的信息
//最后再处理一下，横跨左右两边的信息
void merge_sort(int *arr, int l, int r){
if(l >= r) return;
int mid = (l + r) / 2;
cout << endl;
cout << "sort : " << l << "<--->" << r << " : " << endl;
for(int i = l; i <= r; i++){
cout << arr[i] << " ";
}
cout << endl; //换行
//上面几行用来打印 方便观察
merge_sort(arr, l, mid);
merge_sort(mid + 1, r);
vector<int> temp(r - l + 1);
int k = 0, p1 = l, p2 = mid + 1;
//当左右两个区间还有元素的时候
while(p1 <= mid || p2 <= r){
//1. 右区间为空
//2. 左区间没空，并且，左区间的元素比较小
if((p2 > r) || (p1 <= mid && arr[p1] <= arr[p2])){
temp[k] = arr[p1];//最开始是把p1指向元素放进temp 0下标中
k++, p1++;
}else{//左区间空了，把右区间元素放进去
temp[k] = arr[p2];
k++, p2++;
}
}//右区间还有元素的话，继续把右区间的元素放进去
for(int i = l; i <= r; i++){
arr[i] = temp[i - l];
}//上面那两行相当于覆盖操作
//打印
for(int i = l; i <= r; i++){
cout << arr[i] << " ";
}
cout << arr[i] << " ";
return ;
}
int main(){
int a[10] = {1, 9, 0, 2, 5, 6, 2, 7, 1, 9};
merge_sort(a, 0, 9);
for(int i = 0; i < 10; i++){
cout << a[i] << " ";
}
return 0;
}
//归并排序稳定 时间复杂度：O(nlogn)
//空间复杂度：那个临时数组是在函数内部开辟的空间，属于栈上开辟的变量，先开辟n/2后再释放n/2，再开辟n/2，再释放... 最大的情况是开辟n的，所以空间复杂度为 O(n)
问题：电脑内存大小2GB，如何对一个40GB的文件进行排序？
- 分成20个数组，每个处理2GB的文件，最终得到20个有序数组
- 对文件的写入支持追加写，所以不需要临时变量来存
- 我们可以借助小顶堆加速，比如对20行文件以流的方式只读第一行文件
- 得到最小的文件后在后面继续追加，一直重复这个过程
- 时间复杂度：O(nlogn) * 20 + O(1) + O(n) O(1)因为堆是常量空间 O(n) 是扫一行 然后O(1)可以忽略掉，所以最后时间复杂度为：O(nlogn + n)
//插入排序：/*
* 插入排序算法：
* 1、以数组的某一位作为分隔位，比如index=1，假设左面的都是有序的.
*
* 2、将index位的数据拿出来，放到临时变量里，这时index位置就空出来了.
*
* 3、从leftindex=index-1开始将左面的数据与当前index位的数据（即temp）进行比较，如果array[leftindex]>temp,
* 则将array[leftindex]后移一位，即array[leftindex+1]=array[leftindex],此时leftindex就空出来了.
*
* 4、再用index-2(即leftindex=leftindex-1)位的数据和temp比，重复步骤3，
* 直到找到<=temp的数据或者比到了最左面（说明temp最小），停止比较，将temp放在当前空的位置上.
*
* 5、index向后挪1，即index=index+1，temp=array[index],重复步骤2-4，直到index=array.length,排序结束，
* 此时数组中的数据即为从小到大的顺序.
*
*/publicclassInsertSort{privateint[] array;privateint length;publicInsertSort(int[] array){this.array = array;this.length = array.length;}publicvoiddisplay(){for(int a: array){System.out.print(a+" ");}System.out.println();}/*
* 插入排序方法
*/publicvoiddoInsertSort(){for(int index =1; index<length; index++){//外层向右的index，即作为比较对象的数据的indexint temp = array[index];//用作比较的数据int leftindex = index-1;while(leftindex>=0&& array[leftindex]>temp){//当比到最左边或者遇到比temp小的数据时，结束循环
array[leftindex+1]= array[leftindex];
leftindex--;}
array[leftindex+1]= temp;//把temp放到空位上}}publicstaticvoidmain(String[] args){int[] array ={38,65,97,76,13,27,49};InsertSort is =newInsertSort(array);System.out.println("排序前的数据为：");
is.display();
is.doInsertSort();System.out.println("排序后的数据为：");
is.display();}}//归并排序：publicclassMergeSort{//两路归并算法，两个排好序的子序列合并为一个子序列publicvoidmerge(int[] a,int left,int mid,int right){int[] tmp=newint[a.length];//辅助数组int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针while(p1<=mid && p2<=right){if(a[p1]<=a[p2])
tmp[k++]=a[p1++];else
tmp[k++]=a[p2++];}while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中while(p2<=right) tmp[k++]=a[p2++];//同上//复制回原数组for(int i = left; i <=right; i++)
a[i]=tmp[i];}publicvoidmergeSort(int[] a,int start,int end){if(start<end){//当子序列中只有一个元素时结束递归int mid=(start+end)/2;//划分子序列mergeSort(a, start, mid);//对左侧子序列进行递归排序mergeSort(a, mid+1, end);//对右侧子序列进行递归排序merge(a, start, mid, end);//合并}}@Testpublicvoidtest(){int[] a ={49,38,65,97,76,13,27,50};mergeSort(a,0, a.length-1);System.out.println("排好序的数组：");for(int e : a)System.out.print(e+" ");}}
经典题目
开胃菜
//力扣题：21 88 56//21/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/classSolution{publicListNodemergeTwoLists(ListNode list1,ListNode list2){if(list1 ==null){return list2;}elseif(list2 ==null){return list1;}elseif(list1.val < list2.val){
list1.next =mergeTwoLists(list1.next, list2);return list1;}else{
list2.next =mergeTwoLists(list1, list2.next);return list2;}}//虚拟头节点+迭代方法publicListNodemergeTwoLists(ListNode list1,ListNode list2){ListNode hair =newListNode(-1);ListNode pre = hair;while(list1 !=null&& list2 !=null){if(list1.val <= list2.val){
pre.next = list1;
list1 = list1.next;}else{
pre.next = list2;
list2 = list2.next;}//继续往后迭代
pre = pre.next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
pre.next = list1 ==null? list2 : list1;return hair.next;}}/*复杂度分析
时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。
空间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)
*//*Java中arraycopy方法
System.arraycopy(src, srcPos, dest, destPos, length);
src表示源数组
srcPos表示源数组中拷贝元素的起始位置。
dest表示目标数组
destPos表示拷贝到目标数组的起始位置
length表示拷贝元素的个数*///需要注意的是在进行数组拷贝时，目标数组必须有足够的空间来存放拷贝的元素，否则就会发生角标越界异常。// ！！！！另外还需要注意的是目标数组相对应位置上的元素会被覆盖掉//88 合并两个有序数组classSolution{publicvoidmerge(int[] nums1,int m,int[] nums2,int n){int p1 = m-1;int p2 = n-1;int p = m+n-1;while((p1>=0)&&(p2>=0))
nums1[p--]=(nums1[p1]<nums2[p2])? nums2[p2--]: nums1[p1--];System.arraycopy(nums2,0,nums1,0,p2+1);}}//时间复杂度：O(m+n)。//指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)//空间复杂度：O(1)//直接对数组nums1原地修改，不需要额外空间//56 合并区间//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 classSolution{//思路:区间只有三种情况：包含、相交、独立 我们合并前两种//对区间起始位置从小到大排序 A[] B[] A[尾] >= B[头] 就合并publicint[][]merge(int[][] intervals){Arrays.sort(intervals,newComparator<int[]>(){//排序@Overridepublicintcompare(int[] o1,int[] o2){return o1[0]- o2[0];}});int[][] res =newint[intervals.length][2];//结果集数组int ind =-1;//索引 告诉我们合并的集合应该放在结果集的哪个位置for(int[] interval : intervals){//说明是我们第一个拿到的区间 或者 当前数组头部大于上次拿到数组的尾部if(ind ==-1|| interval[0]> res[ind][1]){
res[++ind]= interval;}else{//此时相交或者包含 确定边界
res[ind][1]=Math.max(res[ind][1], interval[1]);}}//走到这里后面要切割无用部分returnArrays.copyOf(res, ind +1);}}
剑指offer51.数组中的逆序对(hard)
/**
* 剑指offer51.数组中的逆序对(困难)
* @author: William
* @time:2022-05-09
*/publicclassNum51{publicintreversePairs(int[] nums){if(nums.length <2)return0;returnmerge_sort(nums,0, nums.length -1);}privateintmerge_sort(int[] nums,intL,intR){if(L>=R)return0;int mid =L+((R-L)>>1), ans =0;//分治 两个数组都是递增的，p1都比p2大，那p1后面的数更加比p2大
ans =merge_sort(nums,L, mid)+merge_sort(nums, mid +1,R);//归并int[] tmp =newint[R-L+1];int k =0, p1 =L, p2 = mid +1;while(p1 <= mid || p2 <=R){if((p2 >R)||(p1 <= mid && nums[p1]<= nums[p2])){
tmp[k++]= nums[p1++];}else{//只有p1 > p2 的情况下才走到这 是逆序对
tmp[k++]= nums[p2++];
ans +=(mid - p1 +1);}}//将数组元素放到原数组中for(int i =0; i < tmp.length; i++) nums[i +L]= tmp[i];return ans;}//k神版本int[] nums, temp;publicintreversePairs1(int[] nums){this.nums = nums;
temp =newint[nums.length];returnmergeSort(0, nums.length -1);}privateintmergeSort(intL,intR){//终止条件if(L>=R)return0;//递归划分int m =(L+R)>>1;int res =mergeSort(L, m)+mergeSort(m +L,R);//合并阶段int i =L, j = m +1;for(int k =L; k <=R; k++){
temp[k]= nums[k];}for(int k =L; k <=R; k++){if(i == m +1)
nums[k]= temp[j++];elseif(j ==R+1|| temp[i]<= temp[j])
nums[k]= temp[i++];else{
nums[k]= temp[j++];
res += m - i +1;//统计逆序对}}return res;}}
合并K个升序链表(hard)
/**
* 合并K个升序链表(困难)
* @author: William
* @time:2022-05-09
*/classListNode{int val;ListNode next;ListNode(){}ListNode(int val){this.val = val;}ListNode(int val,ListNode next){this.val = val;this.next = next;}}publicclassNum23{//小顶堆publicListNodemergeKLists(ListNode[] lists){if(lists ==null|| lists.length ==0)returnnull;PriorityQueue<ListNode> q =newPriorityQueue<ListNode>(newComparator<ListNode>(){@Overridepublicintcompare(ListNode o1,ListNode o2){return o1.val - o2.val;}});//把链表中的数据塞到小顶堆中for(ListNode list : lists)if(list !=null) q.offer(list);//新的链表来存储合并后的结果集 并且从虚拟头节点开始ListNode ret =newListNode(-1), p = ret;while(!q.isEmpty()){ListNode cur = q.poll();
p.next = cur;//继续往后迭代
p = cur;if(cur.next !=null) q.offer(cur.next);}return ret.next;}}
排序链表
/**
* 排序链表
* @author: William
* @time:2022-05-09
*/publicclassNum148{publicListNodesortList(ListNode head){int n =0;ListNode p = head;while(p !=null){
p = p.next;
n++;}//得到链表的长度returnmerge_sort(head, n);}privateListNodemerge_sort(ListNode head,int n){if(n <=1)return head;int l_cnt = n >>1, r_cnt = n - l_cnt;ListNode ret =newListNode(-1),L= head,R=L, p =L;for(int i =0; i < l_cnt -1; i++) p = p.next;//p此时走到左边链表的尾部R= p.next;
p.next =null;//此时完成左右链表的拆分//开始合并L=merge_sort(L, l_cnt);R=merge_sort(R, r_cnt);
p = ret;while(L!=null||R!=null){if((R==null)||(L!=null&&L.val <=R.val)){
p.next =L;
p =L;L=L.next;}else{
p.next =R;
p =R;R=R.next;}}return ret.next;}}
两根搜索树中的所有元素
/**
* 两根搜索树中的所有元素
* @author: William
* @time:2022-05-10
*/classTreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}TreeNode(int val,TreeNode left,TreeNode right){this.val = val;this.left = left;this.right = right;}}publicclassNum1305{//二叉搜索树在进行中序遍历的时候是递增的publicList<Integer>getAllElements(TreeNode root1,TreeNode root2){List<Integer> list1 =newArrayList<>();List<Integer> list2 =newArrayList<>();List<Integer> res =newArrayList<>();//得到两个递增集合inorder(root1, list1);inorder(root2, list2);intL=0,R=0;while(L< list1.size()||R< list2.size()){if((R>= list2.size())||(L< list1.size()&& list1.get(L)<= list2.get(R))){
res.add(list1.get(L++));}else{
res.add(list2.get(R++));}}return res;}publicvoidinorder(TreeNode root,List<Integer> list){if(root ==null)return;inorder(root.left, list);
list.add(root.val);inorder(root.right, list);}//直接调用集合工具类哈哈哈List<Integer> ans;publicList<Integer>getAllElements1(TreeNode root1,TreeNode root2){
ans =newArrayList<>();dfs(root1);dfs(root2);Collections.sort(ans);return ans;}voiddfs(TreeNode root){if(root ==null)return;dfs(root.left);
ans.add(root.val);dfs(root.right);}}
区间和的个数(hard)
/**
* 区间和的个数(困难)
* @author: William
* @time:2022-05-11
*/publicclassNum327{//通过前缀和求区间和//low <= sum[j] - sum[i] <= upperint lower, upper;publicintcountRangeSum(int[] nums,int lower,int upper){//初始化this.lower = lower;this.upper = upper;long[] sum =newlong[nums.length +1];
sum[0]=0;//求前缀和for(int i =0; i < nums.length; i++) sum[i +1]= sum[i]+ nums[i];returnmerge_sort(sum,0, sum.length -1);}privateintmerge_sort(long[] nums,intL,intR){if(L>=R)return0;int mid =L+((R-L)>>1);int ans =0;
ans +=merge_sort(nums,L, mid);
ans +=merge_sort(nums, mid +1,R);
ans +=countTwoPart(nums,L, mid, mid +1,R, lower, upper);int k =0, p1 =L, p2 = mid +1;long[] tmp =newlong[R-L+1];while(p1 <= mid || p2 <=R){if((p2 >R)||(p1 <= mid && nums[p1]<= nums[p2])){
tmp[k++]= nums[p1++];}else{
tmp[k++]= nums[p2++];}}for(int i =0; i < tmp.length; i++) nums[i +L]= tmp[i];return ans;}//在并的过程中看有多少个元素符合条件privateintcountTwoPart(long[] nums,int l1,int r1,int l2,int r2,int lower,int upper){int ans =0;//记录多少个区间符合状态//j是右侧区间固定数 左侧查找范围for(int j = l2, k1 = l1, k2 = l1; j <= r2; j++){//lower <= j-i <= upper -> j - lower i >= i >= j - upperlong a = nums[j]- upper;long b = nums[j]- lower;//确定两个边界while(k1 <= r1 && nums[k1]< a) k1++;//找到第一个边界就停//k2找比较大的边界 大于等于b的话说明站在最后一个的后面 等于也不要停 往后站一位while(k2 <= r1 && nums[k2]<= b) k2++;
ans += k2 - k1;}return ans;}}
计算右侧小于当前元素的个数(hard)
/**
* 计算右侧小于当前元素的个数(困难)
* @author: William
* @time:2022-05-11
*/publicclassNum315{classData{//每一个data的cnt记录右侧有多少元素小于当前元素int ind, val, cnt;publicData(int ind,int val){this.ind = ind;this.val = val;this.cnt =0;}}publicList<Integer>countSmaller(int[] nums){Data[] data =newData[nums.length];for(int i =0; i < nums.length; i ++){
data[i]=newData(i, nums[i]);//把集合数据塞进去}merge_sort(data,0, data.length -1);Arrays.sort(data,newComparator<Data>(){//下标从小到大排序@Overridepublicintcompare(Data o1,Data o2){return o1.ind - o2.ind;}});List<Integer> res =newArrayList<>();for(Data datum : data){
res.add(datum.cnt);//加入到结果集中}return res;}privatevoidmerge_sort(Data[] data,intL,intR){if(L>=R)return;int mid =(L+R)>>1;merge_sort(data,L, mid);merge_sort(data, mid +1,R);//合并过程int k =0, p1 =L, p2 = mid +1;Data[] tmp =newData[R-L+1];while(p1 <= mid || p2 <=R){//两边任意一个有值就可以if((p2 >R)||(p1 <= mid && data[p1].val > data[p2].val)){//在前面找到一个比后面大的元素 开始计数
data[p1].cnt +=(R- p2 +1);
tmp[k++]= data[p1++];}else{//右侧小于左侧的情况
tmp[k++]= data[p2++];}}for(int i =0; i < tmp.length; i++){
data[i +L]= tmp[i];//将tmp数组中数据覆盖到data中}}}
首个共同祖先
/**
* 首个共同祖先
* @author: William
* @time:2022-05-11
*/publicclassNum0408{publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if(root ==null)returnnull;if(root == p || root == q)return root;//至少找到一个TreeNodeL=lowestCommonAncestor(root.left, p, q);TreeNodeR=lowestCommonAncestor(root.right, p, q);if(L!=null&&R!=null)return root;//p q都找到if(L!=null&&R==null)returnL;//左边是找到的returnR;}}
层数最深叶子节点的和
/**
* 层数最深叶子节点的和
* @author: William
* @time:2022-05-11
*/publicclassNum1302{int ans, max_k;publicintdeepestLeavesSum(TreeNode root){
ans =0;
max_k =0;getAns(root,0);return ans;}privatevoidgetAns(TreeNode root,int k){if(root ==null)return;if(k == max_k) ans += root.val;//当前叶子节点到了最深层 elseif(k > max_k){//达到新的最深层，前面的作废
max_k = k;
ans = root.val;}//继续向下递归getAns(root.left, k +1);getAns(root.right, k +1);}}
本文转载自: https://blog.csdn.net/qq_57469718/article/details/126328914
版权归原作者 慢慢敲吧 所有， 如有侵权，请联系我们删除。
版权归原作者 慢慢敲吧 所有， 如有侵权，请联系我们删除。