Jimmy小站

小明也有大梦想 — 蒋明/铭
当前位置:网站首页 / 数据结构算法 / 正文

小明学排序-归并排序算法

2016-03-23 / 数据结构算法 / 3116 次围观 / 0 次吐槽

典型的排序算法--归并排序,按照自己理解的思路,做了一遍。关于排序算法的资源已经有很多,但是自己整理一遍还是有很大的收获的。主要是学习一种编程思想。

package net.jimmyme;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        
        int[] source = {101,8,9,13,45,17,26,99,78,11,46};
        int[] sourceAfterSort = new int[11];
        
        sourceAfterSort = mergeSort(source);
        System.out.println(Arrays.toString(sourceAfterSort));
        
    }
    
    public static int[] mergeSort(int[] source){
        
        if (source.length <= 1) {
            return source;
        }
        int length = source.length;
        int middle = length/2;
        int[] sourceLeft = new int[middle];
        int[] sourceRight = new int[length-middle];
        // 将前半部分复制到sourceLeft
        System.arraycopy(source, 0, sourceLeft, 0, middle);
        // 将后半部分复制到sourceRight
        System.arraycopy(source, middle, sourceRight, 0, length-middle);
        // 左右递归 进行排序
        int[] left = mergeSort(sourceLeft);
        int[] right = mergeSort(sourceRight);
        // 两边数组归并成一个数组,返回上一层递归
        return merge(left, right);
    }
    public static int[] merge(int[] left, int[] right){
        int leftLength = left.length;
        int rightLength = right.length;
        int[] source = new int[leftLength+rightLength];
        int leftIndex = 0;
        int rightIndex = 0;
        int sourceIndex = 0;
        while (leftIndex < leftLength || rightIndex < rightLength) {
            // 如果左边数组已经遍历完成,而右边还有剩余元素
            if(leftIndex == leftLength && rightIndex < rightLength){
                for (int i = rightIndex; i < rightLength; i++) {
                    source[sourceIndex] = right[rightIndex];
                    sourceIndex++;
                    rightIndex++;
                }
            }
            // 如果右边数组已经遍历完成,而左边还有剩余元素
            else if (rightIndex == rightLength && leftIndex < leftLength) {
                for (int i = leftIndex; i < leftLength; i++) {
                    source[sourceIndex] = left[leftIndex];
                    sourceIndex++;
                    leftIndex++;
                }
            }
            // 两边还有剩余元素  exists elements both sides
            else if (leftIndex < leftLength && rightIndex < rightLength) {
                // 哪边元素比较小就将该元素放入 source数组
                if (left[leftIndex] <= right[rightIndex]) {
                    source[sourceIndex] = left[leftIndex];
                    sourceIndex++;
                    leftIndex++;
                }
                else {
                    source[sourceIndex] = right[rightIndex];
                    sourceIndex++;
                    rightIndex++;
                }
            }
            
        }
        // both sides have on elements
        return source;
    }

}


推荐您阅读更多有关于“排序算法Java,”的文章

[一个Java程序猿的转型之路,读研深造,专注机器学习推荐算法]
本站所有文章如无特别注明均为原创。作者:吉米酱 ,复制或转载请以超链接形式注明转自 Jimmy小站
原文地址《小明学排序-归并排序算法
额 本文暂时没人评论 来添加一个吧

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996