力扣912题 排序数组 详细教程（归并排序实现）.docx

力扣912题排序数组详细教程（归并排序实现）

题目分析与解读

给定一个整数数组nums，将该数组升序排列后返回。要求时间复杂度为O(nlogn)，空间复杂度尽可能低。

关键点解析：

1.必须实现真正的排序算法，不能直接调用库函数

2.时间复杂度要求O(nlogn)，排除了O(n2)的简单排序算法

3.需要原地排序或使用有限额外空间

4.归并排序、快速排序、堆排序都符合要求

现实生活场景类比

想象你在整理一副扑克牌：

1.把牌分成两半，分别排序（递归过程）

2.然后像洗牌一样，从两叠已排序的牌中轮流取较小的牌

3.最终合并成一叠完全有序的牌

4.这个过程就是归并排序的直观体现

解题步骤详解（归并排序）

1.递归终止条件?：当子数组长度为1时直接返回

2.分割数组?：找到中间点mid，将数组分为左右两部分

3.递归排序?：对左右子数组分别递归调用排序

4.合并过程?：

使用三个指针：index(临时数组)、lnow(左数组)、rnow(右数组)

比较左右数组元素，取较小者放入临时数组

处理剩余元素

复制回原数组?：将临时数组结果复制回原数组对应位置

注意事项

1.临时数组大小要足够（本题设为50000）

2.递归深度可能导致栈溢出（对极大数组）

3.合并时的边界条件要仔细处理

4.可以使用全局变量减少参数传递

5.注意mid计算避免整数溢出（本题使用(l+r)/2）

代码实现与注释

classSolution{

public:

inttmp[50000];//全局临时数组，用于归并过程

voidmysort(vectorintnums,intl,intr){

if(l==r){//递归终止条件：子数组长度为1

return;

}

intmid=(l+r)/2;//计算中间点

//递归排序左右子数组

mysort(nums,l,mid);

mysort(nums,mid+1,r);

intindex=l;//临时数组指针

intlnow=l;//左子数组指针

intrnow=mid+1;//右子数组指针

//合并两个有序子数组

while(lnow=mid||rnow=r){

if(rnowr){//右子数组已全部处理

tmp[index]=nums[lnow];

lnow++;

index++;

}

elseif(lnowmid){//左子数组已全部处理

tmp[index]=nums[rnow];

rnow++;

index++;

}

else{//比较左右子数组当前元素

tmp[index]=min(nums[lnow],nums[rnow]);

if(nums[lnow]nums[rnow]){

lnow++;

}

else{

rnow++;

}

index++;

}

}

//将临时数组复制回原数组

for(inti=l;i=r;i++){

nums[i]=tmp[i];

}

}

vectorintsortArray(vectorintnums){

mysort(nums,0,nums.size()-1);//调用归并排序

returnnums;

}

};

问题与代码分析

问题特点：?

1.标准排序问题，但限制算法复杂度

2.测试用例包含各种边界情