精华内容
下载资源
问答
  • 归并排序递归和非递归实现。

    一  递归 :


    /**  递归版本
    *  采用分治的方法,将n个元素自顶向下分成两个n/2的子问题, 再将子问题进行划分,
    *  最终将整个问题分解成每个字表长度为 1 的有序表,然后自底向上成对归并。
    **/
    
    #include <stdio.h>
    
    int b[100]; //中间过程数组
    
    void merge(int a[], int low, int mid, int high){
    	// 此时a[] 的a[low,mid] 和a[mid+1,high]各自都是有序的,属于成对的两个子问题
    	//需要合并成一个有序表
    	int i, j, k;
    	i = low;
    	j = mid + 1;
    	k = 0;
    	for (k=0; i <= mid&&j <= high; k++){
    		//将较小的先放入b[]
    		if (a[i] < a[j])
    			b[k] = a[i++];
    		else
    			b[k] = a[j++];
    	}
    
    	while (i <= mid)  b[k++] = a[i++];
    	while (j <= high) b[k++] = a[j++];
    
    	// 将已有序的数据b[0,k-1]拷贝到a[low,high]中
    	for (i = low,j=0; i <= high; i++,j++){
    		a[i] = b[j];
    	}
    }
    
    void mergeSort(int a[], int low, int high){
    	if (low < high){//划分
    		int mid = (low + high) / 2;
    		mergeSort(a, low, mid); //左子问题
    		mergeSort(a, mid + 1, high);//右子问题
    		merge(a, low, mid, high);//归并两个子问题
    	}
    }
    
    int main(){
    
    	int a[8] = {
    		1, 6, 3, 2, 9, 8, 7, 5
    	};
    
    	//8个元素
    	int n = 8;
    
    	mergeSort(a, 0, n - 1);
    
    	for (int i = 0; i < n; i++){
    		printf("%d ", a[i]);
    	}
    
    	printf("\n");
    
    	return 0;
    }


    二 非递归:

    整个思想如下图,和递归方法思想是一致的。


    /**  非递归版本
    *	同样对数据进行划分,每一趟从左到右,从上到下,依次归并
    *   merge()函数和递归版本一样。主要区别在于mergeSort()里的每次步长的计算和归并。
    **/
    
    #include <stdio.h>
    
    int b[100]; //中间过程数组
    
    void merge(int a[], int low, int mid, int high){
    	// 此时a[] 的a[low,mid] 和a[mid+1,high]各自都是有序的,属于成对的两个子问题
    	//需要合并成一个有序表
    	int i, j, k;
    	i = low;
    	j = mid + 1;
    	k = 0;
    	for (k=0; i <= mid&&j <= high; k++){
    		//将较小的先放入b[]
    		if (a[i] < a[j])
    			b[k] = a[i++];
    		else
    			b[k] = a[j++];
    	}
    
    	while (i <= mid)  b[k++] = a[i++];
    	while (j <= high) b[k++] = a[j++];
    
    	// 将已有序的数据b[0,k-1]拷贝到a[low,high]中
    	for (i = low,j=0; i <= high; i++,j++){
    		a[i] = b[j];
    	}
    }
    
    void mergeSort(int a[],int n){
    	int step = 1;//步长 分别是1,2,4,8...
    
    	while (step <= n){
    		int low = 0;
    		while (low + step <= n){
    			int mid = low + step - 1;
    			int high = mid + step;
    			if (high > n){
    				high = n;  //数据个数不是2的整数次方,最后的数据可能不足step个。
    			}
    
    			merge(a,low, mid, high);
    			low = high + 1; //按照上图 ,从左到右
    		}
    
    		step *= 2; //按照上图 ,从上到下
    	}
    }
    
    int main(){
    
    	int a[8] = {
    		1, 6, 3, 2, 9, 8, 7,5
    	};
    
    	//8个元素
    	int n = 8;
    
    	mergeSort(a,n - 1);
    
    	for (int i = 0; i < n; i++){
    		printf("%d ", a[i]);
    	}
    
    	printf("\n");
    
    	return 0;
    }

    展开全文
  • 文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序与快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能
  • 基本思路: 归并排序(MERGE-SORT)... //归并排序递归体,把整个序列递归分为两个长度为1的子序列,然后对其子序列进行比较归并。得到有序子序列 public static void MergeSort(int []array,int left,int right){ if

    基本思路:
    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
    在这里插入图片描述
    在这里插入图片描述

     //归并排序递归体,把整个序列递归分为两个长度为1的子序列,然后对其子序列进行比较归并。得到有序子序列
        public static void MergeSort(int []array,int left,int right){
            if (left >= right-1)return;
            int mid = (left + right)/2;
            MergeSort(array,left,mid);
            MergeSort(array,mid,right);
            Merge(array,left,mid,right);
        }
    
        /**
         * 将切分的数组进行归并排序
         * @param array 待排序数组
         * @param left 左边数组第一个元素索引
         * @param mid 左边数组最后一个元素索引,mid为右边数组第一个元素索引
         * @param right 右边数组最后一个元素索引
         */
        public static void Merge(int []array,int left,int mid,int right){
            int []tem = new int [right - left ];
            int i = left,j = mid;
            int k = 0;
            while (i < mid && j < right) {
                // 加入等于,保证稳定性
                if (array[i] <= array[j]) {
                    tem[k++] = array[i++];
                } else {
                    tem[k++] = array[j++];
                }
            }
            //处理完,剩余元素放进去。
            while (i < mid){
                tem[k++] = array[i++];
            }
            while (j < right){
                tem[k++] = array[j++];
            }
            //从临时数组搬运到原数组
            for(int t = 0;t < right - left;t++){
                array[left+t] = tem[t];
            }
        }
    
        //归并排序非递归实现
        public static void MergeSort2(int []array){
            //引入一个gap变量进行分组.gap为1时,[0]和[1]进行归并,[2]和[3]进行归并
            //gap为2时,[0,1]和[2,3]进行归并
            if(array.length == 1 || array == null)return;
            //gap表示归并的数组大小,每归并一次,长度就是上次的二倍。
            for(int gap = 1;gap < array.length;gap = gap *2){
                //相邻组就是 [left,mid) [mid,right)
                for (int i = 0;i < array.length;i = i + 2*gap){
                    int left = i;
                    int mid = i+gap;
                    int right = i+gap *2;
                    //防止下标越界
                    if(mid > array.length)mid = array.length;
                    if(right > array.length)right = array.length;
                    Merge(array,left,mid,right);
                }
            }
    
        }
    

    测试代码:

        public static void main(String[] args) {
            int[] array = {2,5,7,8,3,6,9};
            //InsertSort(array);
            //ShellSort(array);
            //SelectSort(array);
            //HeapSort(array);
            //BubbleSort(array);
            //QuickSort2(array);
            MergeSort2(array);
            System.out.println(Arrays.toString(array));
        }
    }
    
    [2, 3, 5, 6, 7, 8, 9]
    

    附:常用排序算法总结在这里插入图片描述

    展开全文
  • 普通的归并排序递归实现比较简单,就不在此赘述,一看就懂。下面贴上代码。 #include using namespace std; template void merge(T arr[], const int start, const int middle, const int end, const int size) {

    一:归并排序

    普通的归并排序递归实现比较简单,就不在此赘述,一看就懂。下面贴上代码。
    #include <iostream>
    #include <assert.h>
    using namespace std;
    
    template <typename T>
    void merge(T arr[], const int start, const int middle, const int end, const int size)
    {                             
        T *room = new T[size*2];    //归并排序虽然是O(nlgn)时间,但是需要者O(n)的空间
        assert(room != NULL);
    
        int left = start;          
        int right = middle+1;
    
        int i = 0;
        while(left <= middle && right <= end){    //按值由小到达copy进room数组中
            if(arr[left] < arr[right])
                room[i++] = arr[left++];
            else
                room[i++] = arr[right++];
        }   
                                
        while(left <= middle)         //程序退出循环只有两种可能,分别处理
            room[i++] = arr[left++];
        while(right <= end)
            room[i++] = arr[right++];
    
        for(int i=start,j=0; i<=end; ++i,++j)   //将排序完成的一串数copy回原数组
            arr[i] = room[j];
    
        delete []room;
    }
    
    template <typename T>
    void merge_sort(T arr[], int start, int end)   //归并排序主函数,start和end分别为起始和终止的下标
    {
        if(start < end){      //如果start=end直接返回,因为单个元素天然有序
            int middle = (int)((start+end)/2);    //求中点
            merge_sort(arr, start, middle);       //归并左半部分
            merge_sort(arr, middle+1, end);       //归并右半部份
            merge(arr, start, middle, end, end-start+1);     //合并两部分
        }   
    }
    
    template <typename T>
    void print(T arr[], const int size)  //打印函数
    {
        for(int i=0; i<size; ++i)
            cout<<arr[i]<<' ';
        cout<<endl;
    }
    
    int main()
    {
        int array[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
        int len = sizeof(array)/sizeof(int);
        merge_sort(array, 0, len-1);
        print(array, len);
        return 0;
    }

    二:自然合并排序

    这个排序是归并排序的变体,基于非递归实现。它是由小到大合并排序完成的子数组完成排序的。
    我们可以首先将数组a中相邻元素两两配对。用合并算法将它们排序,构成n/2组成都为2的排好序的子数组段,然后再将它们排序成长度为4的排好序的字数组段,如此继续下去,直至整个数组排好序。

    注意有两种特殊情况:
    调用归并操作将相邻的一对子数组进行归并时,有些情况需要对最后一组进行特殊处理:
    ① 若最后子数组个数小于等于步长s,则最后一个子数组无须和其它子数组归并(即本趟轮空),直接拷贝  
    ② 若子文件个数为偶数,则要注意最后一对子文件中后一子文件的区间上界是n。
    例如:            数组 : 5 4 3 2 1 1 2
    第一次2个一组归并: 4 5    2 3    11    2   //第一步2个一组合并,s为1,最后一组只有2一个元素,直接轮空。也可以理解为子数组个数为奇数个,直接轮空
    下一次4个一组归并 :   2 3 4 5    11 2        //此时s=2, 11 2的长度为3,大于s,但是小于2s,那么将11和2进行归并即可。
    这两种情况代码体现在这里:
        if(i+s < n)
            merge(x, y, i, i+s-1, n-1);
        else{
            for(int j=i; j<n; ++j){
                y[j] = x[j];
            }
        }
    
    其实,用通俗的话来说,就是前面的合并完了剩下的不足一个就直接轮空,够一点几个就把那一个和另外半个合并就行了!
    全部代码如下:
    #include <iostream>
    #include <assert.h>
    using namespace std;
    
    template <typename T>
    void merge(T x[], T y[], int start, int centre, int end)
    {
        int left = start;
        int middle = centre;
        int right = middle + 1;
    
        while(left <= centre && right <= end){
            if(x[left] < x[right])
                y[start++] = x[left++];    //这部分就是简单的比较拷贝,只是和上面归并排序程序不同的是
            else                           //这部分是从start开始copy的,之前的归并排序每次从0开始copy
                y[start++] = x[right++];
        }   
    
        while(left <= middle)
            y[start++] = x[left++];
        while(right <= end)
            y[start++] = x[right++];
    }
    
    template <typename T>
    void merge_pass(T x[], T y[], int s, int n)   
    {
        int i = 0;
        while(i <= n-2*s){      //当i和n相差2s,说明存在可合并的子数组  //举例两元素数组a[] = {1, 2},i=0,同时s=1时,n-2*s=0此时等于i,可进行合并 
            merge(x, y, i, i+s-1, i+2*s-1);    //采用传递起始,中间,终点下标形式,需要-1,例如上面的数组,s=1时终点下标0+2*1-1=1
            i += 2*s;           //每次按步长走
        }   
    
        if(i+s < n) //如果前面子数组合并完成,还剩一组子数组,例如5,4,3,2,1,1,2步长为2时,54和32合并,剩余11大小满足子数组,就合并它和2
            merge(x, y, i, i+s-1, n-1);
        else{          //如果剩余元素为奇数且不满一组子数组时,直接copy,如5,4,3,2,1,两两合并,剩1,此时i=4,n=5,s=1,则i+s=n,直接拷贝
            for(int j=i; j<n; ++j){
                y[j] = x[j];  //从i开始直接copy
            }
        }   
    }
    
    template <typename T>
    void merge_sort(T arr[], const int size)   //归并排序函数
    {
        T *extra = new T[size];    //申请额外空间
        assert(extra != NULL);
    
        int step = 1;    //步长初值为1
        while(step < size){
            merge_pass(arr, extra, step, size);   //将arr数组copy至extra数组,底层实现具体排序
            step <<= 1;        //步长翻倍
            merge_pass(extra, arr, step, size);   //再次copy回arr数组
            step <<= 1;        //继续翻倍,相当于每次拷来拷去的过程同时进行归并排序
        }   
    }
    
    template <typename T>
    void print(T *arr, const int size)
    {
        for(int i=0; i<size; ++i)
            cout<<arr[i]<<' ';
        cout<<endl;
    }
    
    int main()
    {
        int array[] = {10, 9, 30, 8, 7, 5, 4, 3, 2, 1}; 
        int len = sizeof(array)/sizeof(int);
        merge_sort(array, len);
        print(array, len);
        return 0;
    }
    
    *以上代码均经过验证

    展开全文
  • 归并排序 递归算法

    千次阅读 2018-10-23 22:51:49
    利用递归思想将数组一直划分为要排序的另一半,最后就回将问题化简为相邻两个数的排序,然后将排好序的数组归并到一个数组中,然后继续向上递归直至排序完成。   int a[10]={15, 18, 45, 96, 23, 58, 75, 1, ...

    数组排序任务可以如下完成:

    (1):将前一半排好序

    (2):将后一半排好序

    (3):把两半归并到一个新的有序数组中,然后再拷贝回原来的数组,排序完成

    利用递归思想将数组一直划分为要排序的另一半,最后就回将问题化简为相邻两个数的排序,然后将排好序的数组归并到一个数组中,然后继续向上递归直至排序完成。

     

    int a[10]={15, 18, 45, 96, 23, 58, 75, 1, 52, 69};

    将排好序的数组先存储在b数组中,然后将b数组中的数字按顺序放入a数组中。
    int b[10];

    int main()
    {
        int size = sizeof(a) / sizeof(int);
        
        Mergesort(a, 0, size - 1, b);
        
        for(int i = 0; i < size; i++)
        { 
            cout << a[i] << ",";
        } 
        cout << endl;
        return 0;
    }


    将两个排好序的数组归并到一个数组中


    void Merge(int a[], int s, int m, int e, int tmp[])
    {//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序,然后再拷贝回a[s,m]
     //归并操作时间复杂度:O (e-m+1),即 O(n) 
        
        int pb = 0;
        int p1 = s, p2 = m+1;
        
        while(p1 <= m && p2 <= e)
        {
            if(a[p1] < a[p2])
            { 
               tmp[pb++] = a[p1++];
            } 
            else
            { 
               tmp[pb++] = a[p2++];
            } 
        }
        
        while(p1 <= m)
        {
            tmp[pb++] = a[p1++];
        }
        while(p2 <= e)
        {
            tmp[pb++] = a[p2++];
        }
        
        for(int i = 0; i < e - s + 1; i++)
        {    
            a[s + i] = tmp[i];
        }
    }


    void Mergesort(int a[], int s, int e, int tmp[])
    {
        if(s < e)
        {
            int m = s + (e-s) / 2;
            
            Mergesort(a, s, m, tmp);
            Mergesort(a, m+1, e, tmp);
            Merge(a, s, m, e, tmp); 
        }  
    }
     

    展开全文
  • 本篇文章我将主要向大家介绍归并排序递归实现和非递归实现。 文章目录1. 归并的思想2. 归并排序递归实现3. 归并排序的非递归实现4. 归并排序的特性总结 1. 归并的思想 归并排序(MERGE-SORT)是建立在归并操作...
  • 2 * Merge_Sort: 归并排序的递归实现 3 * 注:算法导论上给出的合并排序算法 4 * 递归过程是将待排序集合一分为二, 5 * 直至排序集合就剩下一个元素为止,然后不断的合并两个排好序的数组 6 * T(n) = O(nlgn) ...
  • 归并排序递归算法

    千次阅读 2014-02-02 16:02:13
    归并排序的思想: 假设初始序列含有n个记录,则可以看成是n个 有序的子序列,每个子序列的长度为1,然后两两 归并,得到n/2个长度为1或者2的有序子序列 在两两归并,如此重复,直到一个长度为n的有序 序列为止...
  • 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。 归并排序中最重要的操作是如何将将二个有序数列合并。 原理是比较两个数列的第一个数,谁小就先取谁,再继续比较下一...
  • 关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java) 关于快速排序的,可以参考我的这篇博客 快速排序的相关算法题(java) 转载请注明原博客地址: ...
  • 归并排序递归思想,代码详解!!!!
  • 这是一段归并排序,下面的代码, 其中对数组左边拆解,右边拆解,然后排序那段的执行流程不太理解。 当递归调用左边拆解结束后如何继续执行?递归是用栈来实现,如何用栈来理解这段代码? static void mergesort...
  • 归并排序:分治、递归思想 将一个数组A分成左右两部分A1、A2,那么对A的排序可以分为以下两步 1.将A1、A2分别排好序 2.将A1、A2两个各自有序的数组合并成一个有序数组,这个过程叫做归并(merge) (分治思想) ...
  • 归并排序是效率非常高的一种排序方式,和快速排序一样用了分治的思想。分治法的精髓在于将一个复杂问题分割成为多个简单的子问题,然后将子问题逐个解决,最终合并在一起以后就是复杂问题的解了。 归并排序对数组...
  • 我们这么理解,我们知道当一个列表越长我们进行排序消耗就越大,那么我们把这个列表分为无数个小的列表,然后对他们进行排序,然后再组合,那么也会节省不少精力 我们直接看代码 首先我们的第一步是 分: merger...
  • 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就...
  • 归并排序的非递归实现如下,思想和递归正好相反,原来的递归过程是将待排序集合一分为二,直至排序集合就剩下一个元素位置,然后不断的合并两个排好序的数组。所以非递归思想为,将数组中的相邻元素两两配对。用...
  • 递归和迭代两种实现方法。对于顺序存储如数组,一般为O(n)的空间;list的空间直接为O(1)。 空间上可以使用原地归并避免O(n)的空间。但较麻烦,且需要多次移动,除非有特殊说明或空间非常宝贵,否则不建议原地归并...
  • 【图文】归并排序 1.递归排序 2.非递归排序
  • 下面小编就为大家带来一篇老生常谈比较排序之归并排序(递归)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 以下是对归并排序递归实现与非递归实现代码进行了详细的介绍,需要的朋友可以过来参考下
  • 插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序递归归并排序、基数排序
  • 归并排序递归递归实现

    千次阅读 2017-03-08 23:29:26
    归并排序就是将2个有序表组合成一个新的有序表。假定待排序表有n个元素,则可以看成是n个有序的子表,每个子表长度为1,然后两两归并…...稳定性:稳定归并排序递归实现:#include <iostream>using namespace std;type
  • c代码-排序:归并排序递归算法
  • 主要介绍了Java排序算法三之归并排序递归与非递归的实现示例解析,文章通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 基于递归归并排序比较简单,只需要自上而下进行排序即可;而非递归版本的归并排序则需要自下而上进行排序; 时间复杂度:O(nlogn),空间复杂度:O(n); 归并排序为稳定排序算法; 此外,归并排序可用于求解逆序对...
  • 逆序对——归并排序递归实现过程中可以实现,本题可以加深对归并排序递归实现过程的理解。 要使用归并排序首先就要将数据分解,一直分解到每一个单位,然后就是进行合并了,这是递归过程。 题解 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,419
精华内容 25,767
关键字:

归并排序递归过程