`
fxly0401
  • 浏览: 151067 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

归并排序

阅读更多
归并排序的时间复杂度为
    T(n)=T(n/2)+T(n/2)+2n-1 = O(nlogn),
该算法优于选择排序、插入排序和冒泡排序。
import java.util.Arrays;
public class MergeSort {
/**@author liuwei
* @param args
*/
    public static void mergeSort(int[] data){
        System.out.println("开始排序:");
        sort(data,0,data.length-1);
    }
    /*将索引从left到right范围的数组元素进行归并排序
     * data 待排序数组
     * left 待排序数组的第一个元素索引
     * right 待排序数组的最后一个元素索引
     */
    private static void sort(int[] data, int left, int right) {
        // TODO Auto-generated method stub
        if(left<right){
            //找出中间索引
            int center=(left+right)/2;
            //对左边数组进行递归
            sort(data,left,center);
            //对右边数组进行递归
            sort(data,center+1,right);
            //合并
            merge(data,left,center,right);
           
        }
    }
    /*将两个数组进行归并,归并前两个数组已经有序,归并后依然有序
     * data 数组对象
     * left 左数组的第一个元素的索引
     * center 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
     * right 右数组的最后一个元素的索引
     */
    private static void merge(int[] data, int left, int center, int right) {
        // TODO Auto-generated method stub
        int [] tmpArr=new int[data.length];
        int mid=center+1;
        //third记录中间数组的索引
        int third=left;
        int tmp=left;
        while(left<=center&&mid<=right){
            //从两个数组中取出最小的放入中间数组
            if(data[left] < (data[mid])){
                tmpArr[third++]=data[left++];
            }else{
                tmpArr[third++]=data[mid++];
            }
        }
        //剩余部分依次放入中间数组
        while(mid<=right){
            tmpArr[third++]=data[mid++];
        }
        while(left<=center){
            tmpArr[third++]=data[left++];
        }
        //将中间数组中的内容复制回原数组
        while(tmp<=right){
            data[tmp]=tmpArr[tmp++];
        }
        System.out.println(Arrays.toString(data));
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] data={21,30,49,30,16,9,-16,10,25,18};
        System.out.println("排序之前:\n"+Arrays.toString(data));
        mergeSort(data);
        System.out.println("排序之后:\n"+Arrays.toString(data));
    }
}
结果输出:
排序之前:
[21, 30, 49, 30, 16, 9, -16, 10, 25, 18]
开始排序:
[21, 30, 49, 30, 16, 9, -16, 10, 25, 18]
[21, 30, 49, 30, 16, 9, -16, 10, 25, 18]
[21, 30, 49, 16, 30, 9, -16, 10, 25, 18]
[16, 21, 30, 30, 49, 9, -16, 10, 25, 18]
[16, 21, 30, 30, 49, -16, 9, 10, 25, 18]
[16, 21, 30, 30, 49, -16, 9, 10, 25, 18]
[16, 21, 30, 30, 49, -16, 9, 10, 18, 25]
[16, 21, 30, 30, 49, -16, 9, 10, 18, 25]
[-16, 9, 10, 16, 18, 21, 25, 30, 30, 49]
排序之后:
[-16, 9, 10, 16, 18, 21, 25, 30, 30, 49]
分享到:
评论

相关推荐

    归并排序Java_归并排序_

    归并排序是一种高效的排序算法,基于分治策略。在Java中实现归并排序,我们可以创建一个名为`MergeSort`的类来封装整个过程。归并排序的基本思想是将待排序的序列分成两个或更多的子序列,对每个子序列分别进行排序...

    C++实现归并排序

    【归并排序】是一种高效的排序算法,其基本思想源于分治法(Divide and Conquer)。归并排序通过不断地将数组划分为较小的子序列,然后对这些子序列进行排序,最后将排序好的子序列合并成一个完整的有序序列。在这个...

    归并排序算法实现

    ### 归并排序算法实现详解 #### 一、引言 归并排序是一种经典的排序算法,采用分治法的思想,将待排序数组分为若干个子序列,这些子序列是已排序的,然后再按照一定的方式合并这些子序列得到最终排序后的数组。...

    C#排序算法之归并排序

    C#排序算法之归并排序 C#排序算法之归并排序是一种基于分治策略的排序算法,通过将数组分割成两个子数组,递归地对每个子数组进行排序,然后将两个有序的子数组合并成一个有序的数组。下面是对C#实现归并排序的详细...

    C语言分治法实现归并排序

    本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并...

    python编程实现归并排序

    归并排序是一种高效的、稳定的排序算法,其核心思想是“分而治之”。在Python中实现归并排序,我们可以分为以下几个步骤来理解: 1. **分割**:首先,我们需要将原始数组不断地分成两半,直到每个子数组只剩下一个...

    C#归并排序的实现方法(递归,非递归,自然归并)

    归并排序是一种高效的排序算法,基于分治策略。在C#中,归并排序可以通过递归、非递归以及自然归并三种方式实现。以下是这三种实现方法的详细解释: 1. **递归归并排序**: 递归归并排序是归并排序最直观的实现...

    归并排序算法.docx

    归并排序(Merge Sort)是一种基于分治策略的高效排序算法。它的基本思想是将待排序的序列分为两部分,分别对这两部分进行排序,然后将排好序的子序列合并成一个完整的有序序列。这一过程可以递归地进行,直到每个子...

    三路归并_C语言_三路归并排序_三路归并_

    **三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...

    C语言演示对归并排序算法的优化实现

    归并排序是一种分治策略的排序算法,它的基本思想是将大问题分解成小问题来解决。在归并排序中,我们将一个大数组分成两个或更多个小数组,然后对每个小数组进行排序,最后将这些小数组合并成一个大的有序数组。这个...

    归并排序的实现代码与思路

    归并排序是一种基于分治策略的高效排序算法,它的核心思想是将大问题分解成小问题,然后分别解决小问题,最后将小问题的结果合并,得到大问题的解。在这个过程中,归并排序将待排序的序列不断地分成两半,直到每个子...

    归并排序 排序

    归并排序是一种基于分治策略的高效排序算法,它的核心思想是将大问题分解成小问题,逐个解决,然后再将结果合并,最终得到整个问题的解决方案。在归并排序中,这一过程主要分为三个步骤:分解、求解和组合。 1. **...

    归并排序_归并排序_

    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案&quot...

    通过javascript实现归并排序.rar

    归并排序(Merge Sort)是一种经典的分治算法,它将一个数组分成两个子数组,分别对这两个子数组进行排序,然后再将两个已排序的子数组合并成一个完整的有序数组。压缩包文件代码是一个使用JavaScript实现归并排序的...

    归并排序(视频+代码)

    1,归并排序的概念 1.1,算法介绍 和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一...

    Java实现归并排序

    归并排序(Merge Sort)是一种基于分治策略的高效排序算法。它的基本思想是将待排序的元素序列分成两个或更多的子序列,分别对每个子序列进行排序,然后将排好序的子序列合并成一个有序序列。这个过程可以递归进行,...

    java归并排序

    归并排序是一种基于分治思想的高效排序算法,它的主要特点是将大问题分解为小问题来解决。在Java中实现归并排序,我们可以分别实现递归版和非递归版,这两种方法各有其特点和适用场景。 ### 1. 分治策略 归并排序...

    归并排序代码

    内部排序之归并排序的代码实现,代码风格简单 易于看懂

    C++实现希尔、快速、堆排序、归并排序算法

    本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...

Global site tag (gtag.js) - Google Analytics