本文介绍: 归并排序是一种常见的排序算法,也是一种分治策略的典型应用。该算法的基本思想是将待排序的序列分成若干个子序列,然后递归地对这些子序列进行排序,最终将排好序的子序列合并成一个有序序列。具体来说,归并排序的过程可以分为两个阶段。第一个阶段是分解,即将原序列分成若干个长度相等的子序列,每个子序列再分成若干个长度相等的子序列,直到无法分解为止。第二个阶段是合并,即将已排好序的子序列合并成一个有序序列。
一、什么是归并排序
归并排序是一种常见的排序算法,也是一种分治策略的典型应用。该算法的基本思想是将待排序的序列分成若干个子序列,然后递归地对这些子序列进行排序,最终将排好序的子序列合并成一个有序序列。
二、代码实现
递归:
public static void mergeSort(int[] nums,int left,int right){
if(left >= right){
return ;
}
int mid = (left+right)/2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
merge(nums,left,mid,right);
}
public static void merge(int[] nums,int left,int mid,int right){
// 左子数组区间 [left, mid], 右子数组区间 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int s2 = mid+1;
// 当左右子数组都还有元素时,比较并将较小的元素复制到临时数组中
while(s1 <= mid && s2 <= right){
if(nums[s1] <= nums[s2]){
tmp[k++] = nums[s1++];
}else{
tmp[k++] = nums[s2++];
}
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (s1 <= mid){
tmp[k++] = nums[s1++];
}
while (s2 <= right){
tmp[k++] = nums[s2++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (int i = 0; i < tmp.length; i++) {
nums[i+left] = tmp[i];
}
}
非递归:
public static void mergeSort(int[] nums){
//模拟递归的效果
int gap = 1;
while(gap < nums.length){
for (int i = 0; i < nums.length; i += gap * 2) {
int left = i;
int mid = left + gap -1;
if(mid >= nums.length){
mid = nums.length -1;
}
int right = mid + gap;
if(right >= nums.length){
right = nums.length -1;
}
merge(nums,left,mid,right);
}
gap *= 2;
}
}
public static void merge(int[] nums,int left,int mid,int right){
int[] tmp = new int[right-left+1];
int k = 0;
int s1 = left;
int s2 = mid+1;
while(s1 <= mid && s2 <= right){
if(nums[s1] <= nums[s2]){
tmp[k++] = nums[s1++];
}else{
tmp[k++] = nums[s2++];
}
}
while (s1 <= mid){
tmp[k++] = nums[s1++];
}
while (s2 <= right){
tmp[k++] = nums[s2++];
}
for (int i = 0; i < tmp.length; i++) {
nums[i+left] = tmp[i];
}
}
三、算法特性
时间复杂度: O(n ^ log n),划分产生高度为 log n 的递归树,每层合并的总操作数量为 n ,因此总体时间复杂度为 O(n ^ log n) 。
空间复杂度:O(n),递归深度为 log n ,使用 O(log n) 大小的栈帧空间。合并操作需要借助辅助数组实现,使用 O(n) 大小的额外空间。
稳定排序:在合并过程中,相等元素的次序保持不变。
原文地址:https://blog.csdn.net/f7ashion/article/details/134610284
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_12395.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。