算法——归并法排序

2022-3-5 diaba 算法 

package com.jiucaiyuan.net.algrithm.sort;

/**
 * 归并法排序
 *  思路：递归处理把数组分成左右两部分，左侧部分排成有序数组，右侧排成有序数组，然后再merge两个数组
 *
 * 算法时间复杂度是O(N*logN)  空间复杂度O(N)
 *
 *
 * Created by jiucaiyuan on 2022/3/5.
 */
public class ReduceMergeSort {
    public static void sort(int[] arr,int l,int r){
        if(l == r){
            return;
        }
        int mid = l + ((r-l)>>1);
        System.out.println("l="+l+"\tmid="+mid+"\tr="+r);
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    /*
     * 合并arr[l,mid] 和 arr[mid+1,r] 两个数组
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        System.out.println("l="+l+"\tmid="+mid+"\tr="+r);
        //合并后的数组
        int[] temp = new int[r - l +1];
        int i=0;
        int p1 = l;
        int p2 = mid + 1;
        //两个数组都有数时
        while(p1<=mid && p2<=r){
            temp[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        //前半段数组长
        while(p1<=mid){
            temp[i++] = arr[p1++];
        }
        //后半段数组长
        while(p2<=r){
            temp[i++] = arr[p2++];
        }
        //把合并后的temp数组复制到arr中
        for(int index=0;index<temp.length;index++){
            arr[l + index] = temp[index];
        }
    }
    public static void main(String[] args){
        int[] arr = {12,5,3,7,3,8,4,3,2,2,6,8,6,0,9,5,3};
        print(arr);
        sort(arr,0,arr.length-1);
        print(arr);
    }
    private static void print(int[] arr) {
        if(arr == null ){
            return;
        }
        for(int a : arr){
            System.out.print(a+"\t");
        }
        System.out.println();
    }
}

« 算法——荷兰国旗（数组分区） | 算法——快速排序»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022