算法-排序(归并排序)

    科技2022-07-10  133

    归并排序

    基本介绍图示代码

    基本介绍

    是利用归并的思想实现的排序方法, 该算法采用经典的分治(divide-and-conquer)策略 分治法将问题分(divide)成一些小的问题然后递归求解, 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之。

    图示

    代码

    public class MergetSort { 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); } } /** * 合并 * @param arr 原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param 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 数组的当前索引 // 1 、先把左右两边(有序)的数据按照规则填充到temp数组 while (i <= mid && j <= right){ if (arr[i] <= arr[j]){//左边元素小于右边元素,temp 填入左边元素 temp[t] = arr[i]; t += 1; i += 1; }else {//反之亦然 temp[t] = arr[j]; t += 1; j += 1; } } //2、把有剩余的数据依次填入到 temp 中 while (i <= mid){//左边有剩余 temp[t] = arr[i]; t += 1; i += 1; } while (j <= right){//右边有剩余 temp[t] = arr[j]; t += 1; j += 1; } //3、将temp数组的元素拷贝到arr 注意,并不是每次都拷贝所有 t = 0; int tempLeft = left; while (tempLeft <= right){ arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } }

    【结果】

    Processed: 0.011, SQL: 8