精华内容
下载资源
问答
  • 自然归并排序
    万次阅读
    2019-10-19 14:51:16

    一、归并排序

    1、介绍。

            归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

            归并排序是稳定排序,需要额外内存,空间复杂度O(n)。时间复杂度,最佳情况:O(nlogn)  最差情况:O(nlogn)  平均情况:O(nlogn)。

    2、步骤。

        (1)申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
        (2)设定两个指针,最初位置分别为两个已经排序序列的起始位置。
        (3)比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
        (4)重复步骤3直到某一指针超出序列尾,将另一序列剩下的所有元素直接复制到合并序列尾。

    3、代码。

    public static void main(String[] args) {
            System.out.println("------开始------");
            //生成生成两份一模一样的随机数组,其中一组用系统自带的方法进行排序,到时候进行验证。
            final int number = 100000;
            int[] sortArray = new int[number];
            int[] sortArrayCopy = new int[n
    更多相关内容
  • 自然归并排序

    2012-06-09 14:20:50
    掌握分治策略,自然归并以及基本的排序算法。比较自然归并排序和普通的顺序,冒泡以及选择排序的各自的特点
  • 内容索引:VC/C++源码,其它分类,排序算法,归并 C++ 使用指针自然归并排序算法示例,输出为控制台程序,方便大家测试,其实最关键的算法在代码里,输出程序仅供参考。
  • 1、普通归并排序 归并排序算法的基本思想是将待排序元素分成大小大致相同的两个子序列,分别对这两个字序列进行排序,最终将排好序的子序列合并为所要求的序列。归并排序算法完全依照下面3个步骤进行。 (1)分解...

    1、普通归并排序

    归并排序算法的基本思想是将待排序元素分成大小大致相同的两个子序列,分别对这两个字序列进行排序,最终将排好序的子序列合并为所要求的序列。归并排序算法完全依照下面3个步骤进行。

    (1)分解。将n个元素分成各含n/2个元素的子序列。

    (2)求解。用归并排序对两个子序列递归地排序。

    (3)合并。合并两个已经排好序的子序列以得到排序结果。

    核心代码如:

    void MergeSort(int a[],int p,int r){
            int q;
            if(p<r){
                q=(p+r)/2;
                MergeSort(a, p, q);
                MergeSort(a,q+1,r);
                Merge(a,p,q,r);
            }
        }

     

     

    完工代码如下:

    ​import java.util.Arrays;
    import java.util.Scanner;
    public class MergeSort1 {
        public static void main(String args[]) {
            MergeSort1 mer = new MergeSort1();
            Scanner input = new Scanner(System.in );
            System.out.print("请输入要排序的个数:");
            int n = input.nextInt();
            int [] array = new int [n];
            System.out.print("请输入排序数:");
            for(int i=0;i<n ;i++)
                array[i] = input.nextInt();
            System.out.println("原数据:" + Arrays.toString(array));
            mer.MergeSort(array,0,n-1);
            System.out.println("排序以后:" + Arrays.toString(array));
        }
        void Merge(int a[],int p,int q ,int r){
            int n1=q-p+1;
            int n2=r-q;
            int i,j ,k;
            int L [] = new int [n1+1];
            int R [] = new int [n2+1];
            for(i=0;i<n1;i++){
                L[i]=a[p+i];
            }
            for(j=0;j<n2;j++){
                R[j]=a[q+j+1];
            }
           L[n1]=R[n2]=1000;
            i= 0;
            j= 0;
            for(k=p;k<r+1;k++){
                if(L[i]<R[j]){
                    a[k]=L[i];
                    i++;
                }
                else{
                    a[k]=R[j];
                    j++;
                }
            }
        }
        void MergeSort(int a[],int p,int r){
            int q;
            if(p<r){
                q=(p+r)/2;
                MergeSort(a, p, q);
                MergeSort(a,q+1,r);
                Merge(a,p,q,r);
                System.out.println("分治递归排序以后:" + Arrays.toString(a));
            }
        }
    }
    ​

    结果截图


    2、自然归并排序

    算法描述:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段,直至整个数组已排好序。

    核心代码如下:

    public void mergeSort(int[] a) {
            int len = 0;
            while(indexLen(0,a)<a.length){
                for (int i = 0,k1=0,k2=0; i < a.length; ) {
                    k1=indexLen(i,a);
                    k2=indexLen(k1,a);
                    merge(a, i, k1,k2);
                    i=i+k1+k2;
                }
            }
        }

    完工代码如下:

    import java.util.Arrays;
    import java.util.Scanner;
    public class Sort {
        public static void main(String args[]) {
            Sort mer = new Sort();
            Scanner input = new Scanner(System.in );
            System.out.print("请输入要排序的个数:");
            int n = input.nextInt();
            int [] array = new int [n];
            System.out.print("请输入排序数:");
            for(int i=0;i<n ;i++)
                array[i] = input.nextInt();
            System.out.println("原数据:" + Arrays.toString(array));
            mer.mergeSort(array);
            System.out.println("排序以后:" + Arrays.toString(array));
        }
    //判断数组有序子序段的长度
        int indexLen(int j,int [] a) {
    
            int k=j+1;
            int len=1;
            for (; ;) {
                if(k>=a.length)
                    break;
                if(a[j]<a[k]) {
                    len++;
                    j++;
                    k++;
                }
                else break;
            }
            return len;
        }
        int index=0;
        public void Printf(int a[]){
            index=indexLen(index,a);
        }
        public void mergeSort(int[] a) {
            int len = 0;
            while(indexLen(0,a)<a.length){
                for (int i = 0,k1=0,k2=0; i < a.length; ) {
                    k1=indexLen(i,a);
                    k2=indexLen(k1,a);
                    merge(a, i, k1,k2);
                    i=i+k1+k2;
                    System.out.println("相邻两组合并排序以后:" + Arrays.toString(a));
                }
            }
        }
        public void merge(int[] a, int i, int len1,int len2) {
            int start = i;
            int X = i + len1;// 归并的前半部分数组
            int j = i + len1;
            int Y = j + len2;// 归并的后半部分数组
            int[] temp = new int[len1+len2];
            int count = 0;
            while (i < X && j < Y && j < a.length) {
                if (a[i] <= a[j]) {
                    temp[count++] = a[i++];
                }
                else {
                    temp[count++] = a[j++];
                }
            }
            while (i < X && i < a.length) {
                temp[count++] = a[i++];
            }
            while (j < Y && j < a.length) {
                temp[count++] = a[j++];
            }
            count = 0;
            while (start < j && start < a.length) {
                a[start++] = temp[count++];
            }
        }
    }

    结果截图

     

    展开全文
  • 自然归并排序java版

    2017-11-06 13:19:37
    自然合并的核心主要是一个Pass函数,这个函数中设置了一个array数组,来存放每一组有序元素的起始元素的下标,最后再将最后一个元素的下标+1存放为array数组的最后一个元素,这样,在后面的合并实现中会显现出这样记录的...
  • 完整的自然归并排序算法源程序,可自行输入待排元素个数以及数值,输出排好序的序列。
  • 自然归并排序 (1)思路: 1、找出需要排序数组中的所有有序子数组,将每个子数组的起始下标存在一个辅组数组中,假设为mark[]。 2、将有序字数组两两归并,最后得到有序数组。 3、需要注意被排序数组的长度N (2)...

    自然归并排序

    (1)思路:

    1、找出需要排序数组中的所有有序子数组,将每个子数组的起始下标存在一个辅组数组中,假设为mark[]。

    2、将有序字数组两两归并,最后得到有序数组。

    3、需要注意被排序数组的长度N<=2的特殊情形。

    (2)代码

    public class NatureMerge extends Sort {
    	public static <T extends Comparable<? super T>> int pass(T[] arr, int[] mark) {
    		int j = 0;
    		T temp = arr[0];
    		mark[j++] = 0;
    		for(int i = 1; i < arr.length; i++) {
    			if(temp.compareTo(arr[i]) <= 0) temp = arr[i];
    			else mark[j++] = i;
    		}
    		mark[j] = arr.length;
    		return j;
    	}
    	
    	public static <T extends Comparable<? super T>> void natureMerge(T[] arr, T[] aux, int[] mark) {
    		int max = pass(arr, mark);
    		
    		for(int sz = 1; sz < max; sz += sz) {
    			for(int i = 0; i < max - sz; i += sz + sz) {
    				merge(arr, aux, mark[i], mark[i + sz] - 1, mark[Math.min(i + sz + sz, max)] - 1);
    			}
    		}
    	}
    	
    	//要检查N<=2时的特殊境况
    	@SuppressWarnings("unchecked")
    	public static <T extends Comparable<? super T>> void sort(T[] a) {
    		int N = a.length;
    		if(N <= 1) return ;
    		if(N == 2) if(less(a[1], a[0])) exch(a, 0, 1);
    		int[] mark = new int[N];
    		T[] aux = (T[])new Comparable[N];
    		natureMerge(a, aux, mark);
    	}
    	
    	private static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int mid, int hi) {
    		for(int i = lo; i <= hi; i++) {
    			aux[i] = a[i];
    		}
    		int j = lo;
    		int k = mid + 1;
    		for(int i = lo; i <= hi; i++) {
    			if(j > mid) a[i] = aux[k++]; 
    			else if(k > hi) a[i] = aux[j++];
    			else if(less(aux[j], aux[k])) a[i] = aux[j++];
    			else a[i] = aux[k++];
    		}		
    	}
    	
    	protected static <T extends Comparable<? super T>> boolean less(T v, T w) {
            return v.compareTo(w) < 0;
        }
    	
    	protected static <T extends Comparable<? super T>> void exch(T[] a, int i, int j) {
            T swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    单链表归并排序

    public static <T extends Comparable<? super T>> Node<T> sort(Node<T> list) {
    		if(list == null || list.next == null) return list;
    		Turple<Node<T>, Node<T>> t = getTwoLists(list);
    		Node<T> l = sort(t.e1);
    		Node<T> r = sort(t.e2);
    		return merge(l, r);
    	}
    	
    	public static <T extends Comparable<? super T>> Node<T> merge(Node<T> left, Node<T> right) {
    		if(left == null) return right;
    		if(right == null) return left;
    		if(less(right.data, left.data)) {
    			Node<T> temp = left;
    			left = right;
    			right = temp;
    		}
    		Node<T> lf = left;
    		Node<T> rg = right;
    		Node<T> temp = null;
    		while(lf.next != null) {
    			if(less(right.data, lf.next.data)) {
    				while(rg.next != null && less(rg.next.data, lf.next.data)) {
    					rg = rg.next;
    				}
    				temp = right;
    				right = rg.next;
    				rg.next = lf.next;
    				lf.next = temp;
    				if(right == null) break;
    			}
    			lf = lf.next;
    		}
    		if(lf.next == null) {
    			lf.next = right;
    		}
    		return left;
    	}
    	
    	public static <T extends Comparable<? super T>> Turple<Node<T>, Node<T>> getTwoLists(Node<T> list) {
    		if(list.next == null) throw new ArrayIndexOutOfBoundsException();
    		Node<T> p1 = list;
    		Node<T> p2 = list;
    		Node<T> temp = null;
    		
    		while(p2.next != null) {
    			p2 = p2.next;
    			if(p2.next != null) {
    				p2 = p2.next;
    			}
    			temp = p1;
    			p1 = p1.next;
    		}
    		temp.next = null;
    		return new Turple<Node<T>, Node<T>>(list, p1);
    	}


    展开全文
  • **自然**归并排序指的是对数组先进行一次线性扫描,得到自然排好序的子数段{4,8},{7},{1,5,6},{2}。在对其进行两两合并成更大的排好序的数组。

    例:a[]={4,8,3,7,1,5,6,2}
    自然归并排序指的是对数组先进行一次线性扫描,得到自然排好序的子数段{4,8},{3,7},{1,5,6},{2}。在对其进行两两合并成更大的排好序的数组。

    #include <stdio.h>
    #define N 8
    int GetIndex(int a[N],int index[N]){
    int i,j=0;
    index[j++]=0;
    for(i=0;i<N-1;i++)
     {
       if(a[i]>a[i+1])
        index[j++]=i+1;
     }
     index[j++]=N;//后面mergesort中合并需要判断i的范围,否则index[i+2]-1无法表示。合并两个需要三个数组下标
     return j;
    
    }
    void merge(int a[N], int left, int mid, int right) {
        int i=left,j=mid+1,k=left;
        int t;
        int d[N];
        while(i <= mid && j <= right) {
            if(a[i] < a[j]){
                d[k++] = a[i++];
            } else {
                d[k++] = a[j++];
            }
        }
        if(i!=mid+1){
            for(t=i;t<=mid;t++){
                d[k++]=a[t];
            }
        }
        if(j != right+1) {
            for(t = j; t <= right; t++){
                d[k++] = a[t];
            }
        }
        for(i = left; i <= right; i++){   //把此次进行合并后的元素拷贝到原数组
            a[i] = d[i];				  //没有参与合并的数组元素不变.为了进行下一次自然分组。
        }
    }
    void mergeSort(int a[N],int index[N]){
        int length=GetIndex(a,index);
        int i;
        while(length!=2){
            for(i=0;i<length-2;i+=2){//      i+=2是每次合并两个 向右移动两个
                merge(a,index[i],index[i+1]-1,index[i+2]-1);
            }
            length=GetIndex(a,index);
        }
    }
    void print(int n,int a[])
    {   int i;
        for(i=0;i<n;i++)
        {if (i!=n-1)  printf("%d, ",a[i]);
        else  printf("%d", a[i]);
    }
    printf("\n");
    
    }
    int main()
    {
        int a[N]={4,8,3,7,1,5,6,2};
        int index[N];
        print(N,a);
        mergeSort(a,index);
        print(N,a);
        return 0;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 使用指针自然归并排序算法编写的C 源代码,输出为控制台程序(类似DOS窗口,如下图),方便大家测试,其实最关键的算法在代码里,输出程序仅供参考。
  • 黑体的注释是普通的自然归并,从相邻长度为1的子数组段进行合并也就是一开始将每两个相邻元素进行归并,然后再相邻四个元素左右两组都有序的合并成4个有序的........自下向上不断往上归并直到有序 /* * 自然合并...
  • 主要介绍了C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,需要的朋友可以参考下
  • } } //合并数组函数,实现自然归并排序 int margeSort(int *s, int n, int *sign, int num) { int jump = 1; int b[N]; while(jump ) { margePass(s, n, b, sign, num, jump); jump+=jump; copySort(s, n, b); } } ...
  • //Main: 代码如下:using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Merge{ class Program { static void Main(string[] args) { while (true) { Console....
  • 递归版归并排序  我们在 CLRS 中已经学会了归并排序的递归写法:  merge函数: def merge(left, right): # prerequisite: both left and right is sorted list ret = [] i = 0 j = 0 while i...
  • 主要介绍了C语言演示对归并排序算法的优化实现,归并排序的最差时间复杂度为(nlog n),最优时间复杂为(n),存在可以改进的空间,需要的朋友可以参考下
  • 最近梳理了下归并排序的递归、非递归、以及自然归并排序算法。 归并排序的基础:将两个有序数组合并为一个有序数组,需要O(n)的辅助空间。 图片来自:https://www.cnblogs.com/chengxiao/p/6194356.html ...
  • 最近在看一部美剧《breaking bad》,从中领会了不少东西。回头再看过去写的博客,感觉真是很糟糕。...这篇对自然归并排序算法时间复杂度的分析便是第一篇。 对于普通归并排序算法,我就不赘述了。任何一本算法...
  • 归并排序自然分组)

    千次阅读 2018-03-27 22:03:55
    这次总结归并排序自然分组的情况下的算法。算法思想:遍历把一个无序的集合,把局部有序的元素划分为一组,两两进行合并,一次合并完毕,再次进行自然分组,然后再两两合并,直到最后一次合并后只剩下一个分组,至此...
  •   归并排序是分治法的典型应用,其思想是不断地将两个有序的数组合并为一个有序数组。 递归实现    #include &lt;stdio.h&gt; void Merge(int a[], int left, int m, int right); void MergeSortAux...
  • 接着根据自然排序将相邻的排好序的子数组进行归并排序,这就是自然归并排序算法的基本思想。 通常情况下,自然归并算法需要合并的次数比归并算法要少,而在极端情况下,如:对于已经排好序的n元数组。自然
  • 归并排序 排序

    2018-01-13 09:13:40
    它的基本思想是:将待排序的数列分成两个小的数列,先对两个子集进行排序,然后进行两个有序子集的合并,形成... 设归并排序的当前区间是R[low..high],分治法的三个步骤是: ①分解:将当前区间一分为二,即求分裂点
  • 归并排序 (1)算法介绍  归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用,归并排序将两个已经有序的序列合并成一个有序的序列。  思路:假设我们有一个没有排好序的...
  • C++实现归并排序

    千次阅读 2019-02-23 20:15:10
    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
  • 1)归并排序的核心思想,先把arr的L--R上分为2部分,然后再归并这俩有序数组为一个整体有序数组2)自然用master公式计算得知,归并排序的时间复杂度为o(nlog(n))
  • 归并排序图文详解

    千次阅读 2021-10-19 19:08:46
    从两个有序数组归并开始讲到归并排序,不仅详解了归并的具体过程,还堆代码中的小细节做了分析,最后分析了归并排序的时间复杂度和空间复杂度。
  • C语言归并排序详解

    2021-05-25 03:36:34
    C语言归并排序详解发布日期:2015-12-31 11:16来源:标签:编程语言C教程C语言归并排序C语言归并排序算法本章我们主要学习C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,下面我们就做...
  • 归并排序

    2020-02-07 15:58:20
    归并排序的基本原理为:将序列平分为两个子序列(如果序列为奇数2*i+1个,则第一个子序列为i+1个,第二个子序列为i个),分别对子序列进行排序,再将已经有序的子序列合并,得到完全有序的序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,632
精华内容 5,452
关键字:

自然归并排序