精华内容
下载资源
问答
  • 归并排序既可以进行内部排序也可以进行外部排序。归并排序的时间复杂度O(N*lgN),空间复杂度为O(N) 在这种情况下可以使用外部归并排序: 若外存中还有N个文件记录,不能一次性读入内存,可以将外存中的文件记录分成...

    归并排序既可以进行内部排序也可以进行外部排序。归并排序的时间复杂度O(N*lgN),空间复杂度为O(N)

    在这种情况下可以使用外部归并排序:

    若外存中还有N个文件记录,不能一次性读入内存,可以将外存中的文件记录分成若干长度为L的可以读进内存的段,并依次读入内存进行内部排序,将有序子文件(归并段)重新写入外存。然后对归并段进行逐趟归并,使归并段由小到大直到有序。但是在外部排序中实现两两归并时因为不能将两个有序段及归并结果段同时放在内存中,所以最主要的是进行外存的读写。

    //内部归并排序的主要代码

     

    void Mergeselction(int*a, int*tmp, int begin1, int end1, int begin2, int end2)//将两个归并段,归并成一个有序的归并段
    {
       assert(a);
       int index = begin1;
       while (begin1 <= end1&&begin2 <=end2)
       {
          if (a[begin1 ]<=a[begin2])
          {
             tmp[index++] = a[begin1++];
          }
          else
          {
              tmp[index++] = a[begin2++];
          }
      }
      while (begin1 <=end1)
      {
         tmp[index++] = a[begin1++];
      }
      while (begin2<=end2)
      {
         tmp[index++] = a[begin2++];
       }
    }
    
    
    
    void _MergeSort(int*a, int *tmp,int left, int right)
    {
       assert(a);
       if (left < right)
       {
         int mid = left + (right - left) / 2;
         _MergeSort(a, tmp, left, mid);
         _MergeSort(a, tmp, mid + 1, right);
         Mergeselction(a, tmp, left, mid, mid + 1, right);
         memcpy(a + left, tmp + left, (right - left + 1)*sizeof(int));
      }
    }
    
    //
    void MergeSort(int *a, size_t size)
    {
       int *tmp = new int[size];
       _MergeSort(a, tmp, 0, size - 1);
       delete[] tmp;
    }

     

    转载于:https://www.cnblogs.com/Blog-day/p/5377846.html

    展开全文
  • 一、归并排序 基本思想:将数组A[0 … n-1]中的元素分成两个子数组A1[0 … n/2]和A2[n/2+1 … n-1]。分别对这两个子数组单独排序,然后将一排序的两个子数组归并成一个含有n个元素的有序数组。 归并排序包含不相邻...

    归并排序

    基本思想:将数组A[0 … n-1]中的元素分成两个子数组A1[0 … n/2]和A2[n/2+1 … n-1]。分别对这两个子数组单独排序,然后将一排序的两个子数组归并成一个含有n个元素的有序数组。

    归并排序包含不相邻元素的比较,但并不会直接交换。在合并两个已排序的数组时,如果遇到了相同的元素,只要保证前半部分数组优先于后半部分数组,相同元素的顺序就不会颠倒,所以归并排序属于稳定的非线性的排序算法

    归并排序算法虽然高效且稳定,但在处理过程中除了用于保存输入数据的数组外,还要临时占用一部分的内存空间。

    归并排序是个原地的排序,空间可以为O(1)

    1、时间复杂度

    算法的递推关系
    在这里插入图片描述
    若n=2k,则有
    在这里插入图片描述若2k<n<2k+1,
    在这里插入图片描述则时间复杂度为:T(n)=O(nlogn)


    2、代码实现

    const int maxn=100;
    int temp[maxn];
    void MergeSort(int *a,int low,int high)
    {
    	if(low>=high)//代码段①
    		return;
    	int mid=(low+high)/2;
    	MergeSort(a,low,mid);
    	MergeSort(a,mid+1,high);
    	Merge(a,low,mid,high);
    }
    
    void Merge(int *a,int low,int mid,int high)
    {
    	int i=low;
    	int j=mid+1;
    	int size=0;
    	for(;(i<=mid)&&(j<=high);size++)
    	{
    		if(a[i]<a[j])
    			temp[size]=a[i++];//代码段②
    		else
    			temp[size]=a[j++];
    	}
    	while(i<=mid)
    		temp[size++]=a[i++];
    	while(j<=high)
    		temp[size++]=a[j++];
    	for(i=0;i<size;i++)
    	{
    		a[low+i]=temp[i];
    	}
    }
    

    3、改进

    代码段①

    if(low>=high)//代码段①
    		return;
    

    可以进行改进,当长度<5或者<7,可以换成冒泡排序、选择排序,避免递归深度过大,效率能够提高。

    代码段②

    for(;(i<=mid)&&(j<=high);size++)
    	{
    		if(a[i]<a[j])
    			temp[size]=a[i++];//代码段②
    		else
    			temp[size]=a[j++];
    	}
    

    temp可以存储数据的索引,而非数据的值,避免数据的值过大的时候拷贝所耗费的时间与空间。

    4、应用场景

    外排序是指处理超过内存限度的数据的排序算法。通常将中间结果放在读写较慢的外存储器(通常是硬盘)上。

    外排序通常采用“排序-归并”策略

    • 排序阶段:读入能放在内存中的数据量,将其排序输出到临时文件,一次进行,将待排序数据组织为多个有序的临时文件。
    • 归并阶段:将这些临时文件组合为大的有序文件。

    【举例】
    使用100M内存对于900MB的数据进行排序:

    • 读入100M数据内存,用常规方式(如堆排序)排序。
    • 将排序后的数据写入磁盘。
    • 重复前两个步骤,得到9个100MB的块(临时文件)中。
    • 将100M内存划分为10份,前9份中为输入缓冲区,第10份输出缓冲区。
      (如前9份各8M,第10份18M;或10份大小同时为10M)
    • 执行九路归并算法,将结果输出到缓冲区
      (若输出缓冲区满,将数据写至目标文件,清空缓冲区。若输入缓冲区空,读入相应文件的下一份数据)
    展开全文
  • 归并排序

    2013-07-06 21:15:35
    归并排序应用场景是当文件太大,没有办法一次行读入内存。则可以考虑归并排序,步骤如下: 1. 先将大文件依次读取,固定长度的数据,然后使用排序算法,将这些数据做内存排序; 2. 将排序好的部分数据存入临时文件...

    归并排序的应用场景是当文件太大,没有办法一次行读入内存。则可以考虑归并排序,步骤如下:

    1. 先将大文件依次读取,固定长度的数据,然后使用排序算法,将这些数据做内存排序;

    2. 将排序好的部分数据存入临时文件中;

    3. loop 1~2 直到大文件中的数据,被读完且排序后存入到临时文件中;

    4. 读取这N个临时文件,选取最小的做归并排序。

     

    归并排序是一种稳定排序方法。

     

    程序代码如下,

    参考: http://blog.csdn.net/v_JULY_v/article/details/6451990

    但是原文中代码略有错误,如下代码中已经修改过了。

     

    void DoSorting(char* file2Sort, char* sortedFile, 
    						int number2sort)
    {
    	this->file2Sort = file2Sort;
    	this->sortedFile = sortedFile;
    	this->number2sort = number2sort;
    
    	// 文件分块在内存中排序,并且写到临时文件中
    	int file_count = MemorySort();
    	MergeSort(file_count);
    
    }
    
    int MemorySort()
    {
    	FILE* fin = fopen(this->file2Sort, "rt");
    	int n = 0, file_count = 0; 
    	int* array = new int[this->number2sort];
    
    	// 每次读 number2sort 整数 在内存中一次排序,并写入临时文件
    	while((n = readData(fin, array, this->number2sort) ) > 0)
    	{
    		qsort(array, n, sizeof(int), cmp_int); //memory sort quick
    
    		char* fileName = temp_filename(file_count++);
    		FILE* tempFile = fopen(fileName, "w");
    		printf("write tempal sorted list to file: %s\n", fileName);
    		free(fileName);
    		writeData(tempFile, array, n);    
            fclose(tempFile); 
    	}
    
    	delete [] array;
    	fclose(fin);
    	return file_count;
    }
    
    void writeData(FILE* f, int a[], int n)    
    {    
        for(int i = 0; i < n; i++)    
            fprintf(f, "%d ", a[i]);    
    }    
    
    int readData(FILE* fin, int* array, int num)
    {
    	int i = 0;
    	while(i < num && (fscanf(fin, "%d", &array[i] )) != EOF)
    	{
    		i++;
    	}
    	printf("read %d integer\n", i);
    	return i;
    }
    
    void MergeSort(int fileCnt)
    {
    	if(fileCnt <= 0)
    	{
    		return;
    	}
    
    	// 归并临时文件, 同时打开所有文件
    	FILE* *fArray = new FILE*[fileCnt];
    	for(int i = 0; i < fileCnt; i++)
    	{
    		char* fileName = temp_filename(i);
    		fArray[i] = fopen(fileName, "rt");
    		delete fileName;
    	}
    
    	int *data = new int[fileCnt];
    	bool *hasNext = new bool[fileCnt];
    	memset(data, 0, sizeof(int) * fileCnt);
    	memset(hasNext, 1, sizeof(bool) * fileCnt);
    	for(int i = 0; i < fileCnt; i++)
    	{
    		if(fscanf(fArray[i], "%d", &data[i]) == EOF)
    		{
    			hasNext[i] = false;
    		}
    	}
    
    	FILE* fout = fopen(this->sortedFile, "wt");
    
    	// Merge sort
    	while(true)
    	{
    		// find the min number in all the files 
    		// 原文中如下部分有错误, 原文中min=data[0] 当文件0先被读完了,就会发生错误
    		int min = INT_MAX;		
    		int min_index = -1;
    		for(int i = 0; i < fileCnt; i++)
    		{
    			if(hasNext[i] && min > data[i])
    			{
    				min = data[i];
    				min_index = i;
    			}
    		}
    		if(-1 == min_index)
    		{
    			break;
    		}
    		if(fscanf(fArray[min_index], "%d", &data[min_index]) == EOF)
    		{
    			hasNext[min_index] = false;
    		}
    		fprintf(fout, "%d ", min);
    		printf("%d ", min);
    	}
    
    	printf("\n");
    	delete [] data;
    	delete [] hasNext;
    	// close the file and release the memory
    	for(int i = 0; i < fileCnt; i++)
    	{
    		fclose(fArray[i]);
    	}
    	delete [] fArray;
    	fclose(fout);
    }


     

    展开全文
  • 距离上次写快排算法的文章已经过去一个半月了,和本文要提到的归并排序算法类似,快排也是分治思想的一种典型应用,如果有不熟悉快速排序的同学可以翻阅我之前写过的的快速排序算法的文章。分治算法首先为大家介绍...

    距离上次写快排算法的文章已经过去一个半月了,和本文要提到的归并排序算法类似,快排也是分治思想的一种典型应用,如果有不熟悉快速排序的同学可以翻阅我之前写过的的快速排序算法的文章。

    分治算法

    首先为大家介绍一下什么是分治,分治是将一个大问题分割成若干个和原来问题形式相同但规模更小的子问题,然后处理这些小问题,最终实现整个大问题的过程。

    f0022b26c175fecfef427287954309e2.png

    额...上面说的概念确实很难理解,我们换一个生活中的场景来介绍一下什么是分治吧。

    小明手里有8枚硬币,其中有1枚是假币,已知假币比真币轻,现在我们有一架天平,那么我们该怎么找出假币呢?

    首先我们将硬币分成两组,每组4枚硬币,分别放到天平上称,硬币一定在轻的那一组里,再次将轻的那一边的硬币分成两组,每组2枚硬币,然后再取轻的那一边在进行二分,直到最后将2枚硬币放在天平上,轻的那一枚就是假币。这里用的就是简单的分治思想,每次把问题规模缩小一半,这里不仅是分治思想,其实也是用到了二分法的思想。

    cf535b779a36487043cf8fadf2b6f7b2.png

    归并排序

    归并排序是分治算法的一种典型应用,基本思路如下:

    • 将数组的前一半进行排序
    • 将数组的后一半进行排序
    • 将两半数据归并成为一个有序的数组,并拷贝回原数组

    44cb81ffc3f4119aaca3389d631705fc.png

    不多逼逼,直接给你们看代码。

    public void mergeSort(int[] arr, int s, int e, int[] tmp) {
     if (s < e) {
      int m = s + ((e - s) >> 1);
      mergeSort(arr, s, m, tmp);
      mergeSort(arr, m + 1, e, tmp);
      merge(arr, s, m, e, tmp);
     }
    }
    
    private void merge(int[] arr, int s, int m, int e, int[] tmp) {
     int p = 0; //指向tmp数组当前位置的指针
     int p1 = s, p2 = m + 1; //p1和p2分别指向分成两组后两边数组的首位置
     while (p1 <= m && p2 <= e) {
      if (arr[p1] > arr[p2]) {
       tmp[p++] = arr[p2++];
      } else {
       tmp[p++] = arr[p1++];
      }
     }
     while (p1 <= m) {
      tmp[p++] = arr[p1++];
     }
     while (p2 <= e) {
      tmp[p++] = arr[p2++];
     }
     for (int i = 0; i < e - s + 1; ++i) {
      arr[s + i] = tmp[i];
     }
    }
    

    咱们来梳理一下上面的代码,首先是mergeSort方法,当起始位置小于终止位置的时候才会执行代码,否则直接结束这个方法。再看看这个判断语句里的内容,首先是求出数组的中点,对数组一分为二进行分治,然后这两个数组又递归调用这个方法,最后对两个已经排好序的数组执行merge方法,进行归并操作。我们可以知道的是,当分到一定程度(s和e指向相同的元素)时,会结束递归,进行归并。我们用一组数据来模拟这个过程。

    4ea2281a188d241a41526af38dbbe0b4.png

    以上是一个待排序的数组,数组长度为10,因此传入的s和e分别为0和9,求出的m值为4,于是将数组分为下标0~4和下标5~9的两个数组再分别进行归并排序。

    为了简化内容,我们尝试对前一个数组进行递归。此时传入的s和e分别是0和4,则m是2,再对前一个数组进行递归,s和e是0和2,m是1,继续递归,s和e是0和1,m是0,这时候两个数组都只有一个数了,这时候就需要对这两个数进行merge操作。所谓的merge操作,就是将两个数组中的元素按从小到大的顺序复制到tmp数组中,然后复制回arr数组中。咱们下面用图片来展示一下上面的代码到底对这个数组干了些什么。

    f5cb0e1dc3f7fd75d056ed374e4b325f.png

    实际上,上述过程只是逻辑上的切分和归并,事实上由于递归需要不断压栈以及以上代码需要顺序执行,切分和归并的次数还要更多一些。

    最后需要提到的是,归并排序是一种稳定的排序算法,时间复杂度为

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

    2018-02-26 14:50:08
    归并排序是排序算法中比较常用的排序算法,Java里Collections.sort排序方法内部实现在一定场景下就是使用归并排序来实现的。归并排序的核心思想是我们常说的分而治之,是分治的典型应用归并排序的基本思想是:要将...
  • java归并排序

    2019-07-22 01:17:53
    冒泡排序作为最基础的排序方法为人所熟知,其从思路到...归并算法是一种采用分治法思想的一种经典应用场景,其原理是将无序数组先分为最小的子数组(每个中含有两个数字),将所有子数组进行排序,随后使子数组两...
  • 归并排序大家都会写了吧,那你知道什么场景或什么题能派上用场吗?当涉及到数组元素中,每个元素要和左边所有,或右边所有元素进行比较的时候,这种情况下可以用归并排序,在排序的过程中,把事儿干了。 不理解的话...
  • 归并排序(Java)

    2021-04-14 21:34:00
    原理2.main函数部分验证四、如何优化五、应用场景总结 归并排序 英文:MergeSort 一、归并排序原理 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一...
  • 这使得归并排序的实用性大大降低,因为在日常的应用中,使用归并排序场景都可以使用快速排序来替代。但是它的优点是可以按照预期来切分数组,每一次都可以对半分,这样不会出现因为分割数组不均匀而使递归调用变成...
  • 两种重要的排序算法,重点掌握他们的思想,以及各自的典型应用场景。 一、题目陈述 如题。 二、解决思路 见各自代码。 三、代码实现 1. 快速排序 void quick_sort(int l,int r) { if(l>=r) return; int x=p[l+r...
  • 归并排序概念使用前提算法思路适用场景算法描述递归法(Top-down)分而治之迭代法(Bottom-up)迭代 概念   归并排序是建立在归并操作上的一种有效的排序算法。    该算法是采用分治法的一个非常典型的应用。  ...
  • 这个题是一个很水的排序题,C/C++本身就提供了排序函数而且速度已经很...其实,归并排序有好多应用场景,比喻求逆序对数就是其经典的用法。 算法思想很简单,就不多说了,直接贴代码吧。 poj2388 #include #include #de
  • 二分查找及其扩展应用场景 大端和小端的问题 2012-09-21 11:33:41| 分类: 算法、数据结构 | 标签:算法数据结构 归并排序 内部排序 面试 |举报 |字号大中小订阅 这三个排序以前都写过...
  • 归并排序与快速排序是两种有实际应用的排序算法,它们有一些共同的特点,整体思路上也比较相近。本文会从更简单的一些排序算法开始,过渡到归并排序和快速排序的实现,并对它们做一些简单的对比思考和总结。在这之前...
  • 常用排序应用场景

    2017-09-21 19:49:00
    一.排序算法分类 1.插入排序法 直接插入排序,希尔排序(面试最...4.归并排序 归并排序 5.基数排序 以上算是最常用的一些算法。 二.空间、时间复杂度、稳定性 三.性能分析 1.O(n^2)性能分析 平均...
  • 排序有大量的应用场景,它往往是解决问题的第一步,它很基础但很重要,比如快速排序就被誉为20世纪科学和工程领域10大算法之一。排序如此有用的一个重要原因是在一个有序数组中查找一个元素比在一个无序数组中查找要...
  • 分治算法与归并排序

    2020-06-13 19:35:45
    距离上次写快排算法的文章已经过去一个半月了,和本文要提到的归并排序算法类似,快排也是分治思想的一种典型应用,如果有不熟悉快速排序的同学可以翻阅我之前写过的的快速排序算法的文章。 分治算法 首先为大家...
  • 这篇博客主要实现一些常见的排序算法。例如: //冒泡排序 //选择排序 //简单插入排序 //折半插入排序 //希尔排序 ...另外,注释中有很多点,比如边界条件、应用场景等已经用 * 标记,* 越多,越应
  • 这题其实挺难想到的,我也是看视频才直到这题要用归并排序做(只能说能想到这种方法的人都太变态了,毕竟归并排序应用场景不多)。好了,不多废话,直接来分析思路。 我们先来回想一下归并排序的步骤: ①确定分界点...
  • 6种常用的排序算法的基本思想,性质和比较:快速排序,归并排序,冒泡排序、选择排序、插入排序、希尔排序。 (转载请注明出处) 了解并掌握排序的概念,并熟悉常见的几种排序算法; 掌握常见的几种排序算法的...
  • 多路归并排序也叫k路归并排序,实际上是归并排序的扩展版,同样也是归并排序的一种,通常的应用场景的针对大数据量的排序。 实现过程: 1、从字面可以看出,多路归并就是将待排的大数据量分成K路,然后将K路的每个...
  • 按算法分类 1.插入排序 直接插入排序,希尔排序 2.交换排序 冒泡排序、快速排序 3.选择排序 直接选择排序、堆排序 4.归并排序 5.基数排序
  • 距离上次写快排算法的文章已经过去一个半月了,和本文要提到的归并排序算法类似,快排也是分治思想的一种典型应用,如果有不熟悉快速排序的同学可以翻阅我之前写过的的快速排序算法的文章。分治算法首先为大家介绍...
  • 最近刚看完《算法》第四版的第二章,把排序算法都实现了下,总结一下这几种排序算法的优劣,改进方案和应用场景。 插入排序所需的时间取决于输入中元素的初始顺序,对一个很大且其中的元素已经有序(或者接近有序)的...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 178
精华内容 71
关键字:

归并排序应用场景