精华内容
下载资源
问答
  • 自然合并排序算法
    千次阅读
    2017-03-22 17:18:29

    合并排序

    package mergesort;
    
    import java.util.Scanner;
    
    public class mergesort {
    
        public void merge(int[] A, int p, int q, int r)
    
        {
    
            int nl = q - p + 1;
    
            int nr = r - q;
    
            int[] rArr = new int[nl + 1];
    
            int[] lArr = new int[nr + 1];
    
            for (int i = 0; i < nl; i++) {
    
                rArr[i] = A[i + p];
    
            }
    
            for (int j = 0; j < nr; j++)
    
            {
    
                lArr[j] = A[j + q + 1];
    
            }
    
            rArr[nl] = Integer.MAX_VALUE;
    
            lArr[nr] = Integer.MAX_VALUE;
    
            int n = 0;
    
            int m = 0;
    
            for (int i = p; i <= r; i++)
    
            {
    
                if (m <= nl && n <= nr)
    
                {
                    if (lArr[m] < rArr[n]) {
                        A[i] = lArr[m];
                        m++;
                    } else {
                        A[i] = rArr[n];
                        n++;
                    }
                } else {
    
                    if (m < nl)
    
                    {
    
                        A[i] = lArr[m];
    
                        m++;
    
                    }
    
                    else
    
                    {
    
                        A[i] = rArr[n];
    
                        n++;
    
                    }
    
                }
    
            }
    
        }
    
        public void mergerSort(int[] A, int p, int r)
    
        {
            if (p == r) {
    
                return;
    
            } else
    
            {
    
                int q = (r + p) / 2;
    
                mergerSort(A, p, q);
    
                mergerSort(A, q + 1, r);
    
                merge(A, p, q, r);
    
            }
    
        }
        public static void main(String[] args) {
    
            Scanner input = new Scanner(System.in);
    
            System.out.println("请输入数组长度:");
    
            int length = input.nextInt();
    
            int a[] = new int[length];
    
            for (int i = 0; i < a.length; i++)
    
            {
                int b = input.nextInt();
                a[i] = b;
    
            }
    
            System.out.println();
    
            int r = a.length - 1;
    
            mergesort MS = new mergesort();
    
            MS.mergerSort(a, 0, r);
    
            for (int i = 0; i < a.length; i++)
    
            {
    
                System.out.print(a[i] + "    ");
    
            }
    
            System.out.println();
    
        }
    }
    

    自然合并排序

    package naturalMS;
    
    import java.util.Arrays;
    import java.util.Random;
    import java.util.Scanner;
    
    public class NatureMs {
        public static void main(String args[]) {
            NatureMs mer = new NatureMs();
            int[] array = mer.getArray();
            System.out.println("OriginalArray:" + Arrays.toString(array));
            mer.mergeSort(array);
            System.out.println("SortedArray:" + Arrays.toString(array));
        }
    
        public int[] getArray() {
            Scanner cin = new Scanner(System.in);
            System.out.print("Input the length of Array:");
            int length = cin.nextInt();
            int[] arr = new int[length];
            Random r = new Random();
            for (int i = 0; i < length; i++) {
                arr[i] = r.nextInt(100);
            }
            cin.close();
            return arr;
        }
    
        public void mergeSort(int[] a) {
            int len = 1;
            while (len < a.length) {
                for (int i = 0; i < a.length; i += 2 * len) {
                    merge(a, i, len);
                }
                len *= 2;
            }
        }
    
        public void merge(int[] a, int i, int len) {
            int start = i;
            int len_i = i + len;// 归并的前半部分数组
            int j = i + len;
            int len_j = j + len;// 归并的后半部分数组
            int[] temp = new int[2 * len];
            int count = 0;
            while (i < len_i && j < len_j && j < a.length) {
                if (a[i] <= a[j]) {
                    temp[count++] = a[i++];
                } else {
                    temp[count++] = a[j++];
                }
            }
            while (i < len_i && i < a.length) {
    
                temp[count++] = a[i++];
            }
            while (j < len_j && j < a.length) {
                temp[count++] = a[j++];
            }
            count = 0;
            while (start < j && start < a.length) {
                a[start++] = temp[count++];
            }
        }
    }
    

    快速排序

    package fastsort;
    import java.util.Scanner;
    
    public class FastSort {
    
        public static void main(String[] args)
        {
            Scanner input = new Scanner(System.in);
            System.out.println("请输入数组长度:");
            int length = input.nextInt();
            int a[] = new int[length];
            int start = 0;
            int end = a.length - 1;
            sort(a, start, end);
    
            for (int i = 0; i < a.length; i++)
    
            {
    
                int b = input.nextInt();
                a[i] = b;
    
            }
            sort(a, start, end);
            for (int i = 0; i < a.length; i++)
    
            {
    
                System.out.print(a[i] + "    ");
    
            }
        }
    
        public static void sort(int[] a, int low, int high)
        {
            int start = low;
            int end = high;
            int key = a[low];
    
            while (end > start)
            {
                // 从后往前比较
                while (end > start && a[end] >= key) // 如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
                    end--;
                if (a[end] <= key) {
                    int temp = a[end];
                    a[end] = a[start];
                    a[start] = temp;
                }
                // 从前往后比较
                while (end > start && a[start] <= key)// 如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
                    start++;
                if (a[start] >= key) {
                    int temp = a[start];
                    a[start] = a[end];
                    a[end] = temp;
                }
                // 此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
            }
            // 递归
            if (start > low)
                sort(a, low, start - 1);// 左边序列。第一个索引位置到关键值索引-1
            if (end < high)
                sort(a, end + 1, high);// 右边序列。从关键值索引+1到最后一个
        }
    
    }
    

    随机选择元素的快速排序

    更多相关内容
  • 自然合并排序算法

    2014-08-17 10:58:48
    自然合并排序算法,对合并排序算法进行进一步的优化
  • 先举个例子看一下自然合并排序和合并排序的区别...自然合并排序算法是对合并排序算法的一种改进。设a[0:n-1]是无序数组,用一次对数组a的扫描可以找出其中自然排好序的子数组,然后将相邻的排好序的子数组段两两合并,

    先举个例子看一下自然合并排序和合并排序的区别:
    在这里插入图片描述
    可以看出自然合并排序在最初时就有已经排好序的子数组,再利用合并排序的原理对于已经排好序的子数组进行两两合并。
    一个解释:

    合并排序 :
    是将两个(或两个以上)有序表合并成一个新的有序表
    自然合并排序:
    就是在合并排序时,建立子数组段,通过数组已排序的(自然排序,不重新排序)子数组段。
    

    问题:

    自然合并排序算法是对合并排序算法的一种改进。设a[0:n-1]是无序数组,用一次对数组a的扫描可以找出其中自然排好序的子数组,然后将相邻的排好序的子数组段两两合并,继续合并相邻排好序的子数组段,直至将整个数组排好序。

    思路:
    自然合并排序是合并排序的改进,应用的原理是:对于一个给定的数组a,通常会有长度大于1的有序子序列,我们称之为自然有序子序列.自然归并排序是找出给定数组中的自然子序列,将其开始的下标位置保存起来,然后对两个子序列之间进行插入排序形成一个大的有序子序列,直到整个数组排序完成。
    大概思路我们首先定义一个全局变量n,控制数组的长度。在给定数组长度的前提,考虑数组子序列数最遭的情况就是整个数组对我们要求的序列刚好成一个反序列,即子序列的个数就是数组元素的个数。所以定义两个长度为n的数组 a、b,一个保存数组元素a[i],另一个保存自然子序列的起始下标值b[i]。
    下面的代码一共是1个主函数4个子函数,主函数首先调用GetIndex()函数,获得自然分组后每个子串的起始坐标,以及自然分组的个数,再在GetIndex()中调用MergeSort()函数将子序列划分,再在MergeSort()中调用MergePass()函数,将相邻子数组进行合并,再在MergePass()函数中调用Merge()函数合并对应索引的数组。


    上代码:

    #include<iostream>
    using namespace std;
    #include <stdlib.h>
    
    // 这个函数记录自然分组后每个子串的起始坐标
    void GetIndex(int a[], int t[], int n, int &m){
     
        
        /*a为输入数组,t为自然分组后每个分组的起始值组成的数组,
    	n为数组长度 ,m自然分组个数*/ 
        int j = 0;
        t[j++] = 0; 
        for(int i = 0; i < n-1; i++) {
            if(a[i+1] < a[i]) {
                t[j++] = i+1;
            }
        }
        m = j;      // m为自然分组的个数
    }
    
    //(3)
    // 合并c[l:m]和c[m+1:r]到d[l:r]
    void Merge(int *c,int *d,int l,int m,int r)
    
    {
    	/*
    	
    	*/
    	int i=l,j=m+1,k=l;//左右子数组的当前处理索引,合并后的索引
    	while(i<=m && j<=r) {
    		if(c[i]<=c[j])  d[k++]=c[i++];
    		else d[k++]=c[j++];
    	}
    	if(i>m)//左子数组全部并入数组d,同时右子数组还有值未并入数组d
    		for(int q=j; q<=r; q++)
    			d[k++]=c[q];
    	else
    		for(int q=i; q<=m; q++)
    			d[k++]=c[q];
    }
    
     //(2)
     // 将x中长度为s的相邻子数组合并,结果存入y中
    void MergePass(int *x,int *y,int *t,int s,int n,int cnt)
    {
    /*
    x为输入的数组,y为长度为n的数组 
    t是分组后子数组的索引的数组,cnt为自然分组个数 
    */ 
    
    
    // n: 数组元素数量
    
    	int i=0;  //子数组起始位置
    	while(i+2*s<=cnt) {   //s为子数组长度 ,cnt为自然分组个数 
    		int r=((i+2*s)<cnt) ?  t[i+2*s]:n; 
    		//
    		Merge(x,y,t[i],t[i+s]-1,r-1);
    		i+=2*s;
    	}
    	if(i+s<cnt) { //剩下的元素少于2s
    		//剩下的元素多于s
    		Merge(x,y,t[i],t[i+s]-1,n-1);
    	} 
    	else {
    		//剩下的元素不多于s
    		for(int j=t[i]; j<n; j++)
    			y[j]=x[j];
    	}
     
    }
    
    
     //(1):相邻两个数组合并 
    void MergeSort(int *a,int *t,int n,int cnt)
    {
    	/*a为原数组 
    	t为自然分组后每个分组的起始值组成的数组,
    	n为数组长度 ,cnt自然分组个数
    	*/
    	int b[n];
    	int s=1;//子数组长度
    	while(s<cnt) {
    		
    		//将长度为s的相邻子数组两两合并(合并成的新数组内部有序)
    		//并将这样的结果保存到数组b
    		MergePass(a,b,t,s,n,cnt);
    		
    		//子数组的长度增加一倍
    		s+=s;
    		//同样使相邻的两个(内部有序)子数组合并成一个长度为"2s"的内部有序新数组保存到数组a 
    		MergePass(b,a,t,s,n,cnt);
    		s+=s;
    	}
    }
    
    int main()
    {
    	int n;
    	cout<<"输入数组元素个数:";
    	cin>>n;
    	int a[n];
    	int t[n]; 
    	cout<<"输入"<<n<<"个元素:";
    	for(int i=0;i<n;i++){
    		cin>>a[i];
    	} 
    	//Print(a,n);
    	int cnt;        // 记录自然分组个数
        GetIndex(a, t, n, cnt);
    	MergeSort(a,t,n,cnt);
    	for(int i=0;i<n;i++) cout<<a[i]<<" "; 
    	return 0;
    }
    
    展开全文
  • 自然合并排序

    2014-05-08 20:56:15
    这是一个实现自然合并排序算法的c++程序,可助于大家参考。
  • 详解自然合并排序

    千次阅读 2019-05-07 21:27:56
    既然是详解自然合并排序,那就一步一步讲解算法: (‾◡◝) 学习自然合并排序,首先我们要先知道: 自然合并排序合并排序的区别: 合并排序 : 是将两个(或两个以上)有序表合并成一个新的有序表 自然合并排序: ...

    既然是详解自然合并排序,那就一步一步讲解算法: (‾◡◝)
    学习自然合并排序,首先我们要先知道:

    自然合并排序和合并排序的区别:

    合并排序 :
    是将两个(或两个以上)有序表合并成一个新的有序表
    自然合并排序:
    就是在合并排序时,建立子数组段,通过数组已排序的(自然排序,不重新排序)子数组段。

    下面通过步骤讲解自然合并排序到底是怎样操作的:( ﹁ ﹁ ) ~→

    自然合并排序步骤:

    简单的说,自然分组排序就是:
    (1)先检查数组内部有没有已经排好序的子数组段;
    将数组划分成一个一个有序的子数组段,
    子数组段个数最大为数组n  (´ー∀ー`)

    即没有已经排好序的,比如要求升序数组,数组是{9,8,7,6,5},那么子数组段就为{9}、{8}、{7}、{6}、{5}

    最小为1  (´ー∀ー`)

    即已经按照要求有序了,比如{5,6,7,8,9}。

    再来一个不极端的例子:

    比如:{4,8,3,7,1,5,6,2},自然排好序的子数组段{4,8}、{3,7}、{1,5,6}、{2};

    (2)分好子数组段后,从第一个开始将相邻的两个子数组段合并成一个数组。然后重新分段,再合并,直到子数组段变为1

    比如子数组段{4,8}、{3,7}、{1,5,6}、{2}
    第一次合并:{3,4,7,8}、{1,2,5,6}
    第二次合并:{1,2,3,4,5,6,7,8}
    结束

    好了。这就是大概步骤了,是不是觉得思想很简单,但是实现起来还是没有头绪  ( ̄_, ̄ )
    没关系,我们通过代码一点一点讲解

    自然合并排序算法讲解:

    (一)首先是第一步骤,先将原数组a进行分段,
    我们需要新开辟一个数组,用这个数组来记录下每个子数组段的首位置,这样就可以达到分割数组的目的,给数组起名为temp:

            for(i=0;i<n-1;i++) //分段
            {
                if(a[i]>a[i+1])
                {
                    temp[j++]=i+1;
                    k++;//k是总共有多少段
                }
            }
            temp[j]=n;
    

    因为循环里我是将i+1作为下标放进去,所以退出条件为n-1
    用k来表示总共有多少段,作为一会儿判断子段数为1时合并结束的条件
    最后多加一个n的目的是作为最后一段结束的位置,后面函数需要用,可以先往下看

    (二)用一个while循环,循环退出条件为k>1,也就是子数组段为1的时候退出
    i表示temp下标位置,j表示合并次数,应该小于段数k除以2,比如有6段就需要合并3次,3段合并1次,最后一段空出(我之前用i<k-2来表示结束条件,发现奇偶段会出现问题)

            int f=k;
            while(k>1)
            {
                for(j=0,i=0;j<k/2;j++,i+=2) //两个相邻的进行合并
                {
                    hebing(temp[i],temp[i+1],temp[i+2]);
                    f--;
                }
                newtemp(temp,k);
                k=f;
            }
            
    

    f的作用是暂代一下新的k值,因为在重新标记子数组段函数里需要知道原来有多少段,所以k值在没有经过这个函数前不能减小。
    for循环里合并子数组段函数传的参数是:第一个子数组段首位置、第二个子数组段首位置、第二个子数组段末位置(也就是第三个子数组段首位置减1,由于我后面函数是统一将下一个子数组段首位置设为前一个子数组段末位置,所以在这里没有减)

    (三)合并子数组段函数
    合并两个子数组的思想很简单,开辟一个新数组x,x的大小为最后一个数组末位置减去第一个数组首位置
    然后将两个数组大小进行比较,按顺序插入
    最后判断一下哪个数组有剩余,加入新数组里
    再将新数组里已经排好的值赋给原来数组a。

        void hebing(int begin,int mid ,int end ) //合并子数组段函数
        {
            int i=0,j;
            int x[end-begin];
            int l1=begin,l2=mid;  //标记一下
            while(l1!=mid && l2!=end)//合并入新数组x
            {
                if(b[l1]<b[l2])
                {
                    x[i++]=b[l1++];
                }
                else
                {
                    x[i++]=b[l2++];
                }
            }
            if(l1==mid) //如果l1排完了,该l2
            {
                while(l2!=end)
                {
                    x[i++]=b[l2++];
                }
            }
            if(l2==end) //如果l2排完了,该l1
            {
                while(l1!=mid)
                {
                    x[i++]=b[l1++];
                }
            }
    
            for(i=0,j=begin;i<end-begin;i++)  //排好序的新数组值赋给原数组
            {
                b[j++]=x[i];
            }
        }
    

    之前的给temp多赋值一个n,在这里就是作为最后一个子数组段的末位置传入的

    (四)重新标记子数组段函数
    这个函数思想也很简单,因为是相邻的两两合并,所以直接去掉temp里除了0外的偶数下标值
    但是因为每次i是加2的,所以容易跳过最后的单数的值,所以在最后判断一下,如果没有给加上,要不然最后一个子数组段没有末位置会出错

        void newtemp(int *temp,int f)  //重新标记子数组段函数
        {
            int i,j=0;
            for(i=0;i<=f;i+=2)    //赋新值,每次加2,跳过已经被合并的数组下标值
            {
                temp[j++]=temp[i];
            }
            if(temp[j-1]!=n)
            {
                temp[j]=n;
            }
        }
    

    好了,主要核心代码和思想就解释完了,
    完整代码:(我写的感觉不太好,大家尽量自己改进啊) ( -’`-; )

    #include<iostream>
    #include<vector>
    using namespace std;
    class solution
    {
    private:
        int *b;int n,k=1;
    public:
        int* ziran(int *a,int s)
        {
            b=a;n=s;
            int temp[n];
            temp[0]=0;
            int i,j=1;
            for(i=0;i<n-1;i++) //分段
            {
                if(a[i]>a[i+1])
                {
                    temp[j++]=i+1;
                    k++;//k是总共有多少段
                }
            }
            temp[j]=n;
            for(i=0;i<k;i++)//输出子段
            {
                cout<<temp[i];
            }
            cout<<endl;
            int f=k;
            while(k>1)
            {
                for(j=0,i=0;j<k/2;j++,i+=2) //两个相邻的进行合并
                {
                    hebing(temp[i],temp[i+1],temp[i+2]);
                    f--;
                }
                newtemp(temp,k);
                k=f;
            }
            return a;
        }
        
        void newtemp(int *temp,int f)
        {
            int i,j=0;
            for(i=0;i<=f;i+=2)
            {
                temp[j++]=temp[i];
            }
            if(temp[j-1]!=n)
            {
                temp[j]=n;
            }
        }
    
        void hebing(int begin,int mid ,int end )
        {
            int i=0,j;
            int x[end-begin];
            int l1=begin,l2=mid;
            while(l1!=mid && l2!=end)//合并入新数组x
            {
                if(b[l1]<b[l2])
                {
                    x[i++]=b[l1++];
                }
                else
                {
                    x[i++]=b[l2++];
                }
            }
            if(l1==mid) //如果l1排完了,该l2
            {
                while(l2!=end)
                {
                    x[i++]=b[l2++];
                }
            }
            if(l2==end) //如果l2排完了,该l1
            {
                while(l1!=mid)
                {
                    x[i++]=b[l1++];
                }
            }
    
            for(i=0,j=begin;i<end-begin;i++)
            {
                b[j++]=x[i];
            }
        }
    
    };
    
    int main()
    {
        int n,i;
        cout<<"数组个数:";
        cin>>n;
        int a[n];
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int *b;
        solution k;
        b=k.ziran(a,n);
        for(i=0;i<n;i++)
        {
            cout<<b[i];
        }
    }
    
    

    后记

    可能我指针学的不太好,所以这个题在写的时候有很多段错误的bug,而且不停徘徊在值和数组下标里很晕,太菜了...  ┭┮﹏┭┮
    自然合并排序在已知数组已经有很多有序的子段时,效率还是非常高的
    开始写这个的时候很懵
    然后csdn搜了半天,发现就是简单的几句话带过思想,然后直接是完整代码,感觉这样慢慢去研究代码又没有注释啥的很烦 (>﹏<)
    所以想写一篇比较详细的,之后也会更一些碰见比较烦的算法题。
    ︿( ̄︶ ̄)︿

    展开全文
  • Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘...
  • 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子...

    一、合并排序(归并排序)概念 / 思想

    定义:(引用自"百度百科")

    • 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
    • 合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
    • 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。合并排序也叫归并排序。

    算法步骤:(引用自"菜鸟教程")

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

    示例图:
    图-归并排序示例图

    二、分治算法实现

    1. 设计递归方程

    1. 我们需要将序列拆分,将当前区间一分为二,即求中间点;

    2. 递归地对两个子区间 L[left…mid] 和 R[mid+1…right] 进行归并排序(即再次执行第一步);

    3. 当拆分后的子序列只含有一个元素时,将已排序的两个子区间 L[left…mid] 和 R[mid+1…right] 合并为一个有序的区间[left…right]。

    2. 编写程序代码

    // 合并排序
    #include<iostream>
    
    using namespace std;
    
    void mergeSort(int array[], int left, int right);
    void merge(int array[], int left, int mid, int right);
    
    int main()
    {
    	// 待排序数组,也可进行改写,获取键盘输入进行排序
    	int array[] = { 10,5,8,6,3,9,4,1,2,7 };
    	int len = sizeof(array) / sizeof(int); // 数组长度
    	
    	mergeSort(array, 0, len-1);
    	cout << "合并排序:";
    	for (int i = 0;i < len;i++)
    		cout << array[i] << " ";
    	cout << endl;
    	
    	return 0;
    }
    
    void mergeSort(int array[], int left, int right)
    {
    	// 当子序列就只有一个元素的时候结束递归调用
    	if (left == right)
    		return;
    	else {
    		// 分治
    		// 判断中间位置,进行拆分
    		int mid = (left + right) / 2;
    		mergeSort(array, left, mid);
    		mergeSort(array, mid + 1, right);
    		// 合并
    		merge(array, left, mid, right);
    	}
    }
    
    void merge(int array[], int left, int mid, int right)
    {
    	// 声明一个指针,指向临时数组,临时存放排序后的元素
    	int* tempArray = new int[right - left + 1];
    
    	int left_1 = left;		// 指向 左待排序区域 第一个元素
    	int left_2 = mid + 1;	// 指向 右待排序区域 第一个元素
    	int k = 0;				// 指向 临时数组 第一个元素
    
    	// 顺序选取两个待排序区的较小元素,存储到tempArr数组中
    	while (left_1 <= mid && left_2 <= right) {
    		// 将较小的元素存入tempArr数组中,并将指针递增
    		if (array[left_1] <= array[left_2])
    			tempArray[k++] = array[left_1++];
    		else
    			tempArray[k++] = array[left_2++];
    	}
    	// 若比较完之后,有序区仍有剩余元素,则直接复制到tempArray数组中
    	while (left_1 <= mid)
    		tempArray[k++] = array[left_1++];
    	while (left_2 <= right)
    		tempArray[k++] = array[left_2++];
    
    	// 将临时数组中排序后的元素取出
    	for (int i = left, j = 0;i <= right;i++,j++)
    		array[i] = tempArray[j];
    
    	// 删除指针
    	delete[] tempArray;
    }
    

    3. 运行结果展示

    运行截图1

    4. 程序改进

    程序只是举例排序{ 10,5,8,6,3,9,4,1,2,7 },
    可以使用cin获取用户输入替代此数组,对用户输入的数据进行排序。

    三、自然合并排序

    1. 概念 / 基本思想

    • 自然合并排序是合并排序算法的一种改进;

    • 对于初始给定的数组,通常存在多个长度大于1的已排好序的子数组段。因此用一次线性扫描就可以找出所有这些排好序的子数组段,然后将相邻的排好序的子数组段两两合并。

    • 注:通常情况下, 按此方式进行合并排序所需的合并次数较少。

    • 举个栗子

      • 数组a中元素为{2, 5, 8, 3, 6, 10, 4, 9};
      • 用一次对数组a的线性扫描,找出自然排好序的子数组段:{2, 5, 8},{3, 6},{10},{4, 9};
      • 然后将相邻的排好序的子数组段两两合并:{2, 3, 5, 6, 8},{4, 9, 10};
      • 继续合并直至整个数组排好序{2, 3, 4, 5, 6, 8, 9, 10}。

    2. 编写程序代码

    // 待更新。。。
    

    3. 运行结果展示

    运行截图(待更新。。。)

    三、友情链接~


    最后,非常欢迎大家来讨论指正哦!

    展开全文
  • /************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入格式1,12,13):"); scanf("%d,%d,%d",&p,&q,&r); printf("p=%...
  • 实现并验证合并排序算法; Ex2:实现并验证快速排序算法 Ex3:用递归与分治的方法设计并实现寻找第k小元素算法
  • 合并排序算法C语言源程序,合并排序算法就是将多个有序数据表合并成一个有序数据表,进行两两合并和数据大小比较,算法程序亲测可用。
  • c语言合并排序算法_合并排序算法

    千次阅读 2020-07-28 22:29:17
    c语言合并排序算法 合并排序算法 (Merge Sort Algorithm) Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time. 合并排序遵循...
  • 合并排序(C语言实现)

    2020-12-31 16:55:49
    现在就用递归算法,采用上面的分治思想来解合并排序。  合并排序(非降序) 分解:把合并排序分解成与两个子问题 伪代码: 代码如下:MERGE_SORT(A, begin, end) if begin < end  then mid<- int((begin + ...
  • 合并排序法.txt

    2019-07-14 09:44:55
    使用插入排序算法对输入的n个整数,按照从小到大的顺序排序。 Input Description 第一行输入一个整数n(0)。 第二行输入n个整数。 Output Description 输出排序后的整数,每个整数之间以一个空格分隔。注意:最后...
  • 排序算法合并排序

    千次阅读 2019-10-25 10:09:58
    合并排序法 (Merge Sorting) 是外部排序最常使用的排序方法。 主要应用场景是:若数据量太大无法一次完全加载内存, 可使用外部辅助内存来处理排序数据,主要应用在文件排序。 排序方法: 将欲排序的数据分别存在...
  • 算法课的作业,利用分治合并排序。 #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:...
  • 合并排序算法排序过程 每个程序员都需要了解他们的算法和数据结构。 在研究它们时,您需要确保确切了解它的功能,时间和空间的复杂性以及采用这种方式的原因,并且不仅能够对其进行编码,而且能够手动执行。 这就是...
  • 合并排序算法

    2012-12-04 09:07:59
    合并排序算法,要下载的就赶紧行动吧,有助于大家更好的理解该算法
  • C语言实现合并排序

    2021-01-21 17:15:10
     现在用递归算法,采用上面的分治思想来解合并排序。  合并排序(非降序)  分解:把合并排序分解成与两个子问题  伪代码:  MERGE_SORT(A, begin, end)  if begin < end  then mid<- int...
  • 算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言。
  • 合并排序算法排序过程 外部分类 (External sorting) External sorting is a technique in which the data is stored on the secondary memory, in which part by part data is loaded into the main memory and then...
  • 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 归并排序是建立在归并操作上的一种有效的...
  • 合并排序算法的时间复杂性分析

    千次阅读 2017-03-13 13:18:57
    显然,当n=1时,合并排序一个元素需要常数时间,因而T(n)=O(1)。 当n>1时,将时间T如下分解: 分解:这一步仅仅是计算出子序列的中间位置,需要常数时间O(1)。 解决子问题:递归求解两个规模为n/2的子问题...
  • 文件合并排序 我们有一个包含整数的大文件... 任务是为该文件实现合并排序算法。 JVM 的内存比文件大小少得多。 package ua.goit.alg; public class Arrays { public static void mergeSort(File file) { } }
  • 分治算法-合并排序

    2021-09-04 20:09:26
    合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。 合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 230,794
精华内容 92,317
关键字:

自然合并排序算法