一.归并排序的核心思想是分而治之:1.分解:将一个大的数组拆成多个小数组,直到每个数组中只有一个数2.解决:对小数组进行排序3.合并:将已经排序好的小数组组合成最终结果二.归并排序中的递归将大数组进行拆分,直至每个数组中只有一个元素时,不需要排序,因为一个元素本身就是有序的拆完之后开始合并,递归负责拆分,合并函数负责排序“先进后出,后进先出”----归并排序利用了递归而递归的实现底层依赖栈结构。三.归并排序java代码实现publicstaticvoidmergesort(int[]arr,intleft,intright){if(leftright){//如果不写则在递归过程中会导致栈溢出return;}intmid(leftright)/2;mergesort(arr,left,mid);mergesort(arr,mid1,right);merge(arr,left,mid,right);}1.判断数组中是否只有一个元素2.找到中间位置mid3.先递归左半部分4.左半部分递归完了,再递归右半部分5.合并两个有序区域例如mergeSort(arr,0,3)会继续调用mergeSort(arr,0,1)mergeSort(arr,2,3)然后mergeSort(arr,0,1)继续拆mergeSort(arr,0,0)mergeSort(arr,1,1)因为left right满足left right所以结束递归。递归过程像不断打开盒子大盒子 - 小盒子 - 更小盒子直到无法拆分然后逐层返回。四.合并排序代码部分:publicstaticvoidmerge(int[]arr,intleft,intmid,intright){int[]tempnewint[right-left1];//定义一个新的数组,数组中的数量是right-left1,暂时用来存放排序好的元素intileft;intjmid1;intk0;while(imidjright){if(arr[i]arr[j]){temp[k]arr[i];}else{temp[k]arr[j];}}while(imid){temp[k]arr[i];}while(jright){temp[k]arr[j];}for(intx0;xtemp.length;x){arr[leftx]temp[x];}} ## 时间复杂度**归并排序的时间复杂度拆分的层数 ×每层合并的次数**即**logn×nO(nlogn)**拆分的时候每次都是拆分成两个,所有klogn**归并排序利用递归不断二分数组二分产生 log n 层每一层合并需要遍历 n 个元素因此时间复杂度为O(nlog n)空间复杂度为O(n)。**
