您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

归并排序法(图文)

第十三双眼睛2023-10-18【数据结构与算法】人已围观

简介归并排序法

package com.xingchen.day006;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int [] arr = {8,4,5,7,1,3,6,2};
int [] temp = new int[arr.length];
mergeSort(arr,0, arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) /2;
//向左递归
mergeSort(arr,left, mid, temp);
// 向右递归
mergeSort(arr, mid+1, right, temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
int i = left; //初始化i标识左边有序序列的初始索引
int j = mid + 1; // 初始化J,标识右边有序序列的初始索引
int t = 0;// 指向temp数组的当前索引
while (i <=mid && j <= right) {
// 如果左边的当前元素小于等于右边的序列的当前元素,就把左边的当前元素填充到temp中
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
i++;
t++;
} else {
// 将右边序列的数字填充到temp中
temp[t] = arr[j];
t++;
j++;
}
}
// 先把左右两边的数据按规则填充到temp数组,之道左右两边有一边全部处理完毕
// 最后把剩余的一边的数据全部填充到temp中
// 将temp数组的数据全部拷贝到arr
// 说明左边的序列还有剩余
while (i<=mid) {
temp[t] = arr[i];
t++;
i ++;
}
while (j<=right){
temp[t] = arr[j];
t++;
j++;
}
// 将temp数组拷贝到arr
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft ++;
}
}
}

Tags：

很赞哦！ ()

上一篇：快速排序法(图文)

下一篇：基数排序法(图文)