您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
归并排序法(图文)
第十三双眼睛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:
很赞哦! ()