精华内容
下载资源
问答
  • 排序算法之 归并排序 及其时间复杂度和空间复杂度 在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序归并排序和快速排序有那么点异曲同工之妙,快速排序:是先...

    排序算法之 归并排序 及其时间复杂度和空间复杂度

    在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序;归并排序和快速排序有那么点异曲同工之妙,快速排序:是先把数组粗略的排序成两个子数组,然后递归再粗略分两个子数组,直到子数组里面只有一个元素,那么就自然排好序了,可以总结为先排序再递归;归并排序:先什么都不管,把数组分为两个子数组,一直递归把数组划分为两个子数组,直到数组里只有一个元素,这时候才开始排序,让两个数组间排好序,依次按照递归的返回来把两个数组进行排好序,到最后就可以把整个数组排好序;


    算法分析

            归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并
            基本思路:
            先递归的把数组划分为两个子数组,一直递归到数组中只有一个元素,然后再调用函数把两个子数组排好序,因为该函数在递归划分数组时会被压入栈,所以这个函数真正的作用是对两个有序的子数组进行排序;
            基本步骤:
            1、判断参数的有效性,也就是递归的出口;
            2、首先什么都不管,直接把数组平分成两个子数组;
            3、递归调用划分数组函数,最后划分到数组中只有一个元素,这也意味着数组是有序的了;
            4、然后调用排序函数,把两个有序的数组合并成一个有序的数组;
            5、排序函数的步骤,让两个数组的元素进行比较,把大的/小的元素存放到临时数组中,如果有一个数组的元素被取光了,那就直接把另一数组的元素放到临时数组中,然后把临时数组中的元素都复制到实际的数组中;

    实现代码

    #include<stdio.h>  
       
     #define LEN 12   // 宏定义数组的大小  
     static int tmp[LEN] = {0};// 设置临时数组  
       
    // 打印数组  
     void print_array(int *array)  
     {  
         int index = 0;  
         printf("\narray:\n");  
         for (; index < LEN; index++){  
             printf(" %d, ", *(array + index));  
         }  
         printf("\n");  
     }  
       
    // 把两个有序的数组排序成一个数组  
     void _mergeSort(int *array, int start, int middle, int end)  
     {  
        int first = start;  
        int second = middle + 1;  
        int index = start;  
        while ((first <= middle) && (second <= end)){  
            if (array[first] >= array[second])  
                tmp[index++] = array[second++];  
            else  
                tmp[index++] = array[first++];  
        }     
        while(first <= middle) tmp[index++] = array[first++];  
        while(second <= end) tmp[index++] = array[second++];  
       
        for (first = start; first <= end; first++)  
            array[first] = tmp[first];  
     }  
      
    // 递归划分数组  
     void mergeSort(int *array, int start, int end)  
     {  
         if (start >= end)  
             return;  
         int middle = ((end + start) >> 1);  
         mergeSort(array, start, middle);// 递归划分左边的数组  
         mergeSort(array, middle+1, end);// 递归划分右边的数组  
         _mergeSort(array, start, middle, end);// 对有序的两个数组进行合并成一个有序的数组  
     }  
       
     int main(void)  
     {  
         int array[LEN] = {2, 1, 4, 0, 12, 520, 2, 9, 5, 3, 13, 14};  
         print_array(array);  
         mergeSort(array, 0, LEN-1);  
         print_array(array);  
         return 0;  
     }  

      
    
    
            分析下上面代码:其实上面的代码主要的是两个函数,第一个是划分数组函数,第二个是对两个有序数组合并的归并函数;这里要借助一个临时数组,有的人在main函数中申请动态数组,然后让所有递归调用都使用该数组;也有的人在归并函数里申请个临时数组;而我的方法是定义一个全局的临时数组;其实我感觉这几个方法都是大同小异,因为不管是动态数组还是全局静态数组,在递归释放调用排序函数时,都会保存一份数据;如果是在排序函数中定义临时数组,那么应该和前面的方法一样的,因为是局部临时数组,存放在栈空间,当该函数调用完后,会马上释放。所以我个人感觉这三种方法都差不多(如果是在归并函数中定义的临时数组,则需要全部压栈;而其他的就只需要压入有用数据所占的空间就可以)

    运行结果:
     

    时间复杂度

            归并的时间复杂度分析:主要是考虑两个函数的时间花销,一、数组划分函数mergeSort();二、有序数组归并函数_mergeSort();
            _mergeSort()函数的时间复杂度为O(n),因为代码中有2个长度为n的循环(非嵌套),所以时间复杂度则为O(n);
          简单的分析下元素长度为n的归并排序所消耗的时间 T[n]:调用mergeSort()函数划分两部分,那每一小部分排序好所花时间则为  T[n/2],而最后把这两部分有序的数组合并成一个有序的数组_mergeSort()函数所花的时间为  O(n);

            公式:T[n]  =  2T[n/2] + O(n);
            
            公式就不仔细推导了,可以参考下: 排序算法之快速排序及其时间复杂度和空间复杂度里面时间复杂度的推导;

            所以得出的结果为:T[n] = O( nlogn )

            因为不管元素在什么情况下都要做这些步骤,所以花销的时间是不变的,所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为:O( nlogn );好像有人说最差的时间复杂度不是O(nlogn),我不知道怎么算出来的,知道的麻烦告知下,谢谢;
     

    空间复杂度

            归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间:n + logn;所以空间复杂度为: O(n)

    以时间换空间

            我看到网上很多blog分享空间复杂度只有O(1)的归并排序法;因为传统的归并排序所消耗的空间主要是在归并函数(把两个有序的函数合并成一个有序的函数),所以如果要让时间复杂度为 O(1)  ,那么也只能在归并函数中做文章了。代码就不列出来了,其主要思想就是借助于快速排序(其实就是相当于归并函数被快速排序函数替换了);这样的方法虽然可以减少内存的消耗,但是却会在时间上带来损失,因为这样时间复杂度却变成了  O(n^2)  了;所以这种方法并不是一个两全其美的idea;

    总结

            归并排序虽然比较稳定,在时间上也是非常有效的(最差时间复杂度和最优时间复杂度都为 O(nlogn)  ),但是这种算法很消耗空间,一般来说在内部排序不会用这种方法,而是用快速排序;外部排序才会考虑到使用这种方法;
         
            转载请注明作者和原文出处,原文地址:http://blog.csdn.net/yuzhihui_no1/article/details/44223225
            若有不正确之处,望大家指正,共同学习!谢谢!!!

    展开全文
  • 【AU】二路归并排序

    2021-03-25 20:09:08
    文章目录二路归并排序时间复杂度空间复杂度适用性稳定性代码 二路归并排序 时间复杂度 O(n log2n) 每趟归并的时间O(n),共需要进行 log2n 趟归并。 空间复杂度 O(n) 辅助空间一个长度n的数组 适用性 顺序存储...

    二路归并排序

    时间复杂度

    O(n log2n)
    每趟归并的时间为O(n),共需要进行 log2n 趟归并。

    空间复杂度

    O(n)
    辅助空间为一个长度为n的数组

    适用性

    顺序存储、链式存储

    稳定性

    稳定!

    代码

    import java.util.Scanner;
    
    public class MergeSort {
    
    	public static void merge(int []list,int low,int mid,int high) {
    		int []B=new int [list.length+1];
    		int i,j,k;
    		for(i=1;i<=high;i++) {
    			B[i]=list[i];
    		}
    		for(i=low,k=i,j=mid+1;i<=mid&&j<=high;k++) {
    			if(B[i]<=B[j]) {
    				list[k]=B[i++];
    			}else {
    				list[k]=B[j++];
    			}
    			
    		}
    		while(i<=mid) list[k++]=B[i++];
    		while(j<=high) list[k++]=B[j++];
    	}
    	public static void sort(int []list,int low,int high) {
    		if(low<high) {
    			int mid=(low+high)/2;
    			sort(list,low,mid);
    			sort(list,mid+1,high);
    			merge(list, low, mid, high);
    		}
    	}
    	public static void main(String[] args) {
    		Scanner  sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		int []list=new int[n+1];
    		for(int i=1;i<=n;i++) {
    			list[i]=sc.nextInt();
    		}
    		for(int i=1;i<=n;i++) {
    			System.out.print(list[i]+"  ");
    		}
    		System.out.println();
    		sort(list,1,n);
    		for(int i=1;i<=n;i++) {
    			System.out.print(list[i]+"  ");
    		}
    		sc.close();
    	}
    }
    
    
    展开全文
  • 时间复杂度:O(N*logN) (最好/坏情况)空间复杂度: O(N)原地二路归并排序为了解决原始二路归并排序空间复杂度较高的情况而产生的,思想很巧妙,很是佩服。它在将原始的空间复杂度由 O(N) 变为 O(1).

    二路归并排序

    原始二路归并排序

    思想:

    先将原始数组划分为n个较小的子数组,然后对每个子数组两两进行排序并合并为一个次子数组
    重复上述过程直到次子数组的个数为1即为排序后的原始数组

    时间复杂度:O(N*logN) (最好/坏情况)

    空间复杂度: O(N)

    原地二路归并排序

    为了解决原始二路归并排序空间复杂度较高的情况而产生的,思想很巧妙,很是佩服。它在将原始的空间复杂度由 O(N) 变为 O(1),时间复杂度没有变。

    原理

    见博客:http://blog.163.com/zhaohai_1988/blog/static/2095100852012721113044469/

    Java代码:

    package 算法视频.排序;
    
    public class 归并排序_要求空间复杂度为O_1 {
    
        public static void main(String[] args) {
            int[] a = { 6, 8, 5, 7, 9, 3, 2 };
            f1(a, 0, a.length - 1);
            printResult(a);
        }
    
        private static void f1(int[] a, int left, int right) {
            if (left >= right) {
                return;
            }
            int middle = (left + right) >> 1; // 以中间点为分割点分割数组
            f1(a, left, middle); // 将left到middle分割
            f1(a, middle + 1, right); // 将middle+1到right分割
            meger(a, left, middle, right); // 将分割后的数组合并
        }
    
        // 原地移动
        private static void meger(int[] a, int left, int middle, int right) {
            int i = left;
            int j = middle + 1;
            int index = j;
            while (i <= middle && j <= right) {
                // 先找到第一个数组中比第二个数组第一个数大的第一个值
                while (i <= middle && a[i] < a[j]) {
                    i++;
                }
                // 然后再找到第二个数组中比a[i]大的第一个值
                while (j <= right && a[i] > a[j]) {
                    j++;
                }
                // 此时a[left...i-1]均小于a[middle+1...j-1],交换位置并将i前移j-1-middle-1位即可,然后重复
                swap(a, i, index-1);
                swap(a, index, j - 1);
                swap(a, i, j - 1);
                i += j - index;
                index = j;
            }
        }
    
        private static void swap(int[] a, int i, int j) {
            if (i > j || i < 0 || j < 0) {
                return;
            }
            while (i <= j) {
                int tem = a[i];
                a[i] = a[j];
                a[j] = tem;
                i++;
                j--;
            }
        }
    
        private static void printResult(int[] a) {
            if (a == null) {
                return;
            }
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
    }

    测试结果:

    2 3 5 6 7 8 9 
    展开全文
  • 要求:空间复杂度为O(1) 思路:利用原数组A的空间,两个下标i和j分别遍历L1和L2。注意:当L2当前元素较小时,会覆盖L1的元素。可以利用插入排序,将arr[j]插入到L1中。 程序c++实现: #include <iostream> #...

    题目:数组A,前面一段是L1,后面一段L2。两个有序序列L1和L2,利用归并排序的merge,将数组A排序。要求:空间复杂度为O(1)

    思路:利用原数组A的空间,两个下标i和j分别遍历L1和L2。注意:当L2当前元素较小时,会覆盖L1的元素。可以利用插入排序,将arr[j]插入到L1中。

    程序c++实现:

     #include <iostream>
     #include <cstdlib>
     using namespace std;
     void print(int *arr, int start, int end)
     {
    	for (int i = start; i <= end; ++i)
    		cout << arr[i] << ' ';
    	cout << endl;
     }
     void randData(int *arr, int start, int end)
     {
    	for (int i = start; i <= end; ++i)
    		arr[i] = rand() % 20; 
    	print(arr, start, end);
     }
     
    void merge(int *arr, int start, int mid, int end)
    {
    	int i, j, k, key;
    	i = start;
    	j = mid;
    	while (i < j && j <= end)  //当i等于j或者j到达末尾时终止
    	{
    		if (arr[i] > arr[j])
    		{	
    			k = j;
    			key = arr[j];
    			while (k > i && arr[k - 1] > key)
    			{			
    				arr[k] = arr[k - 1];
    				--k;
     
    			}
    			arr[k] = key;
    			++j;
    		}
    		++i;
    	}
    }
    void mergeSort(int *arr, int start, int end)
     {
    	if(start < end)
    	{
    		int mid = (end + start) / 2;
    		mergeSort(arr, start, mid);
    		mergeSort(arr, mid + 1, end);
    		merge(arr, start, mid + 1,end);
    		print(arr, start, end);
    	}
     }
     /*11 4 2 13 12 2 1 16 18 15*/
     int main()
     {
    	bool bIsContinue = true;
    	char ch = 'n';
    	const int Len = 10;
    	int arr[Len];
    	print(arr, 0, Len - 1);
     
    	while (true == bIsContinue)
    	{
    		randData(arr, 0, Len - 1);
    		mergeSort(arr, 0, Len - 1);
    		cout << "the new array: ";
    		print(arr, 0, Len - 1);
    		cout << "please input yes or no" << endl;
    		cin >> ch;
    		if (ch == 'y' || ch == 'Y')
    			bIsContinue = true;
    		else
    			bIsContinue = false;
    	}
        return 0;
     }
     
    
    展开全文
  • 二路归并排序和多路归并排序

    千次阅读 2019-10-03 11:48:14
    其实归并排序挺好理解的,也挺好实现的。其实也挺像我们的平常分工合作的。就像一样事情分成几份,由不同的人去做。再合并起来,采用了分治的思想。 对于一个数列,也同是如此。 我们只需要不断地对着中点切分就...
  • 【Java常用排序算法】归并排序(二路归并排序

    千次阅读 多人点赞 2017-02-27 23:17:10
    归并排序 二路归并排序 Java实现
  • 归并排序的递归过程如下,该递归树的高度为log2n(计算过程:假设待排序的数组元素个数为n,设高度为x,x意味着n个元素需要连续分x次才剩下1个元素,即n/2^x=1,x=log2n),每一层的总比较次数为n,所以时间复杂度...
  • 算法描述分析: 归并排序(MERGE-SORT)是建立在归并操作...若将两个有序表合并成一个有序表,称为二路归并。 这是官方一点的对于归并排序的定义,简单的来说,我们把要排序的列表或者数组,每一次都给它递归生成n...
  • 二路归并排序

    千次阅读 2018-08-04 21:23:45
    二路归并排序主要运用了“分治算法”,分治算法就是将一个大的问题划分n个规模较小而结构相似的子问题。 二路归并排序主旨是“分解”与“归并”: 分: 1.一直分两组,分别对两个数组进行排序(根据上层对下层在...
  • 如果没有要求空间复杂度为O(1),可以遍历链表并将每个节点的值存入vector中,利用sort( )对vector排序后,最后再遍历一次链表,将排序后的vector中的元素依次赋给链表的节点值。时间复杂度O(nlogn),空间复杂度O(n...
  • 前面有篇文章已经写了选择类排序、交换类排序和插入类排序(传送门),下面将介绍二路归并排序和基数排序。 二路归并排序 1、执行过程        原始序列:45 35 65 95 75 15 25 &...
  • 归并排序,其实就是递归+合并。
  • *二路归并算法思想: * 将长度n的待排序数据表看成是n个长度1的有序表,并将这些有序表两两归并, * 便得到[n/2]个有序表;再将这[n/2]个有序表两两归并,如此反复,直到最后得到 * 长度n的有序表为止。 ...
  • 二路归并排序简介及其并行化

    千次阅读 2015-05-08 17:46:29
    一、归并排序简介 1.算法思想 归并排序属于比较类非线性时间排序,比较类排序中性能最佳,应用较为广泛。 ...归并排序是分治法(Divide and ...2.二路归并排序过程描述 设有数列{16,23,100,3,38,128,23}...
  • C++实现二路归并排序算法

    千次阅读 2020-11-05 22:21:20
    归并类:二路归并排序 基数类:多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下: 本文放出二路归并算法的排序算法代码。 二路归并排序 void merge(int R[], int low, int mid, int high) { int ...
  • 二路归并排序C++实现

    千次阅读 2019-07-13 11:20:21
    二路归并排序 基本思想 二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]第一个有序表,arr[center]到arr[right...
  • 排序算法之——二路归并排序 二路归并排序的思想: 一次排序过程,将已经各自有序的两个段的数据合并一个段,并且合并后依旧有序 开始,我们认为单个数据是有序的,一个数据就是一个段,一次排序之后,两个数据就是...
  • 算法思想:将无序序列拆分至只有一个关键字的子序列;然后两两归并,直至归并成一个序列 时间复杂度分析:共需...空间复杂度:需要转存整个无序序列,空间复杂度为O(n) 代码: void Merge(int arr[],int left...
  • 二路归并排序Python实现-III 归并排序 是一种 效率比较高并且稳定的算法。时间复杂度 O(NLog(N)),空间复杂度 O(N). 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法...
  • 两种解法,本质上都是二路归并排序,一个是递归写法,另一个是非递归写法。递归写法简单,工整;非递归写法不太容易理解,也不简洁。 二路归并排序的过程如下所示: 待排序序列:49,38,65,97,76,13,27。共

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,683
精华内容 4,673
关键字:

二路归并排序的空间复杂度为