精华内容
下载资源
问答
  • 文章目录一、归并排序的概念二、归并排序递归与非递归实现三、归并排序应用场景四、归并排序总结 一、归并排序的概念 二、归并排序递归与非递归实现 归并排序递归实现,分治为每个区间元素都有序,那么就得把区间 ...

    一、归并排序的概念

    在这里插入图片描述

    二、归并排序递归与非递归实现

    归并排序递归实现,分治为每个区间元素都有序,那么就得把区间 分治成为1才能保证区间中每个元素都有序,在归并:
    在这里插入图片描述

    //归并排序
    void _MergeSort(int*arr, int left, int right, int* tmp)
    {
    	if (left >= right)
    	{
    		return;
    	}
    	int mid = left + (right - left) / 2;
    	_MergeSort(arr, left, mid, tmp);
    	_MergeSort(arr, mid + 1, right, tmp);
    
    	int begin1 = left;
    	int end1 = mid;
    
    	int begin2 = mid + 1;
    	int end2 = right;
    
    	int i = left; 
    
    	while (begin1 <= end1&&begin2 <= end2)
    	{
    		if (arr[begin1] < arr[begin2])
    		{
    			tmp[i++] = arr[begin1++];
    		}
    		else if (arr[begin1]>arr[begin2])
    		{
    			tmp[i++] = arr[begin2++];
    		}
    	}
    
    	while (begin1 <= end1)
    	{
    		tmp[i++] = arr[begin1++];
    	}
    	while (begin2 <= end2)
    	{
    		tmp[i++] = arr[begin2++];
    	}
    
    	for (int j = left; j <= right; j++)
    	{
    		arr[j] = tmp[j];
    	}
    }
    void MergeSort(int* arr, int sz)
    {
    	int* tmp = new int[sz];
    	_MergeSort(arr, 0, sz - 1, tmp);
    	delete[] tmp;
    }
    

    归并排序非递归实现 ,借助gap值来归并:
    在这里插入图片描述
    注意归并时候发生的三种情况:
    在这里插入图片描述

    void _MergeSortNonR(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
    {
    	int i = begin1;
    	int j = begin1;
    	while (begin1 <= end1&&begin2 <= end2)
    	{
    		if (arr[begin1] < arr[begin2])
    		{
    			tmp[i++] = arr[begin1++];
    		}
    		else
    		{
    			tmp[i++] = arr[begin2++];
    		}
    	}
    	
    	while (begin1 <= end1)
    	{
    		tmp[i++] = arr[begin1++];
    	}
    	while (begin2 <= end2)
    	{
    		tmp[i++] = arr[begin2++];
    	}
    
    
    	for (; j <= end2; j++)//begin1加加j不受到影响
    	{
    		arr[j] = tmp[j];
    	}
    }
    void MergeSortNonR(int* arr, int sz)
    {
    	int* tmp = new int[sz];
    
    	int gap = 1;
    	while (gap < sz)
    	{
    		for (int i = 0; i < sz; i += 2 * gap)
    		{
    			int begin1 = i;
    			int end1 = i + gap - 1;
    
    			int begin2 = i + gap;
    			int end2 = i + 2 * gap - 1;
    
    			//如果第二个小区间不存在了
    			if (begin2 >= sz)
    			{
    				break;
    			}
    
    			//如果第二个小区间存在,但是第二个小区间不够gap个,结束位置就越界了,需要修正一下
    			if (end2 >= sz)
    			{
    				end2 = sz - 1;	
    			}
    			_MergeSortNonR(arr, begin1, end1, begin2, end2, tmp);
    		}
    	}
    }
    

    三、归并排序应用场景

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    四、归并排序总结

    在这里插入图片描述

    展开全文
  • 一、是什么归并排序(Merge Sort)是建立归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,...

    8b4394d7cc5a243091e686fc166cc724.png

    一、是什么

    归并排序(Merge Sort)是建立归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用

    将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序

    例如对于含有 n 个记录的无序表,首先默认表中每个记录各为一个有序表(只不过表的长度都为 1)

    然后进行两两合并,使 n 个有序表变为n/2  个长度为 2 或者 1 的有序表(例如 4 个小有序表合并为 2 个大的有序表)

    通过不断地进行两两合并,直到得到一个长度为 n 的有序表为止

    例如对无序表{49,38,65,97,76,13,27}进行归并排序分成了分、合两部分:

    如下图所示:

    74121d9ffb8fc5653d1a77e84a609ba5.png

    归并过程中,每次得到的新的子表本身有序,所以最终得到有序表

    上述分成两部分,则称为二路归并,如果分成三个部分则称为三路归并,以此类推

    二、如何实现

    关于归并排序的算法思路如下:

    • 分:把数组分成两半,再递归对子数组进行分操作,直至到一个个单独数字

    • 合:把两个数合成有序数组,再对有序数组进行合并操作,直到全部子数组合成一个完整的数组

      • 合并操作可以新建一个数组,用于存放排序后的数组

      • 比较两个有序数组的头部,较小者出队并且推入到上述新建的数组中

      • 如果两个数组还有值,则重复上述第二步

      • 如果只有一个数组有值,则将该数组的值出队并推入到上述新建的数组中

    3520bd85aa4ac57ad03e0b2e340a2782.gif

    用代码表示则如下图所示:

    function mergeSort(arr) {  // 采用自上而下的递归方法
        const len = arr.length;
        if(len < 2) {
            return arr;
        }
        let middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }
    
    function merge(left, right)
    {
        const result = [];
    
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
    
        while (left.length)
            result.push(left.shift());
    
        while (right.length)
            result.push(right.shift());
    
        return result;
    }

    上述归并分成了分、合两部分,在处理分过程中递归调用两个分的操作,所花费的时间为2乘T(n/2),合的操作时间复杂度则为O(n),因此可以得到以下公式:

    总的执行时间 = 2 × 输入长度为n/2sort函数的执行时间 + merge函数的执行时间O(n)

    当只有一个元素时,T(1) = O(1)

    如果对T(n) = 2 * T(n/2) + O(n)进行左右 / n的操作,得到 T(n) / n = (n / 2) * T(n/2) + O(1)

    现在令 S(n) = T(n)/n,则S(1) = O(1),然后利用表达式带入得到S(n) = S(n/2) + O(1)

    所以可以得到:S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S(1) + O(logn) = O(logn)

    综上可得,T(n) = n * log(n) = nlogn

    关于归并排序的稳定性,在进行合并过程,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也不会交换,由此可见归并排序是稳定的排序算法

    三、应用场景

    在外排序中通常使用排序-归并的策略,外排序是指处理超过内存限度的数据的排序算法,通常将中间结果放在读写较慢的外存储器,如下分成两个阶段:

    • 排序阶段:读入能够放进内存中的数据量,将其排序输出到临时文件,一次进行,将带排序数据组织为多个有序的临时文件

    • 归并阶段:将这些临时文件组合为大的有序文件

    例如,使用100m内存对900m的数据进行排序,过程如下:

    • 读入100m数据内存,用常规方式排序

    • 将排序后的数据写入磁盘

    • 重复前两个步骤,得到9个100m的临时文件

    • 将100m的内存划分为10份,将9份为输入缓冲区,第10份为输出缓冲区

    • 进行九路归并排序,将结果输出到缓冲区

      • 若输出缓冲区满,将数据写到目标文件,清空缓冲区

      • 若缓冲区空,读入相应文件的下一份数据

    参考文献

    • https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015

    • https://chowdera.com/2021/09/20210920201630258d.html#_127

    • https://juejin.cn/post/6844904007899561998

    --The End--

    系列正在更新:14/18

    点击下方卡片解锁更多

    fe678a2c32f8473ac21f2e32a2d66af1.png

    创作不易,星标、点赞、在看 三连支持

    展开全文
  • 在这种情况下可以使用外部归并排序: 若外存中还有N个文件记录,不能一次性读入内存,可以将外存中的文件记录分成若干长度为L的可以读进内存的段,并依次读入内存进行内部排序,将有序子文件(归并段)重新写入外存...

    归并排序既可以进行内部排序也可以进行外部排序。归并排序的时间复杂度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

    展开全文
  • 之前两篇关于排序算法的综述以及平方阶复杂度的3种具体类型的排序算法,这一篇将具体介绍其中平均时间复杂度在平方阶O(nlog2n)的三个排序算法,以及各种算法的代码实现(亲测正确)。 快速排序 快速排序是由东尼·...

    之前两篇关于排序算法的综述以及平方阶复杂度的3种具体类型的排序算法,这一篇将具体介绍其中平均时间复杂度在平方阶O(nlog2n) 的三个排序算法,以及各种算法的代码实现(亲测正确)。

    快速排序

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 O(nlogn)次比较。在最坏状况下则需要O(n^2)
     次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 O(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

    算法思想

    过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在简单排序基础上的递归分治法。

    算法步骤

    1.从数列中挑出一个元素,称为 “基准”(pivotpos)。
    2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    图示

    算法复杂度

    最优情况:
    Partition每次都划分得很均匀,如果排序n个关键字,其递归树的深度就为 [log2n]+1([x] 表示不大于 x 的最大整数),即仅需递归log2n次。第一次Partiation应该是需要对整个数组扫描一遍,做n次比较。然后,获得的枢轴将数组一分为二,那么各自还需要T(n/2)的时间(注意是最好情况,所以平分两半)。故为:O(nlog2n) 
    最坏情况:
    当待排序的序列为正序或逆序排列时为最糟糕情况下的快排。此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为:n(n-1)/2 ,故时间复杂度为:O(n^2)

    稳定性

    因为快排是根据基准pivotpos来进行的分区操作,当存在元素与基准相同时,由于分区的操作,最后会将基准值放在与之相同元素的后面,因此快速排序时一种不稳定的排序算法。

    代码实现(递归与非递归)

    // 分区操作
    int partition(int arr[], int low, int high)
    {
    	int pivot = arr[low];  //基准
    	while (low < high)
    	{
    		while (arr[high] >= pivot && low < high)
    			--high;  // 找到排在后面但是小于基准的最先元素
    		arr[low] = arr[high];
    		while (arr[low] <= pivot && low < high)
    			++low;
    		arr[high] = arr[low];
    	}
    	arr[low] = pivot;
    	return low;
    }
    
    //快速排序
    void Quick_Sort(int arr[], int low, int high)
    {
    	int pivotpos;
    	if (low < high)
    	{
    		pivotpos = partition(arr, low, high);
    		Quick_Sort(arr, low, pivotpos - 1);
    		Quick_Sort(arr, pivotpos + 1, high);
    	}
    }
    
    //非递归方法
    void Quick_Sort_NonRecursive(int arr[], int low, int high)
    {
    	int pivotpos;
    	std::stack<int> pos_stack;
    	pos_stack.push(low);
    	pos_stack.push(high);
    	while (!pos_stack.empty())
    	{
    		high = pos_stack.top();  // 注意出栈顺序
    		pos_stack.pop();
    		low = pos_stack.top();
    		pos_stack.pop();
    		if (low < high)
    		{
    			pivotpos = partition(arr, low, high);
    			//左边序列起始、终止位置入栈
    			pos_stack.push(low);
    			pos_stack.push(pivotpos - 1);
    			//右边
    			pos_stack.push(pivotpos + 1);
    			pos_stack.push(high);
    		}
    	}
    }
    

    快排优化

    根据上面时间复杂度的分析,可以看出快速排序的时间复杂度最优、最坏的关键在于基准的选择上。因此对于基准的选择的优化便是对于快速排序的算法优化。

    随机算法选取基准
    使用随机化算法(舍伍德算法)产生一个随机数rand,随机数的范围为[left, right],并用此随机数为下标对应的元素a[rand]作为中轴,并与最后一个元素a[right]交换,然后进行与选取最后一个元素作为中轴的快排一样的算法即可。
    三数取中(median-of-three)
    假设数组被排序的范围为left和right,center=(left+right)/2,对a[left]、a[right]和a[center]进行适当排序,取中值为中轴,将最小者放a[left],最大者放在a[right],把中轴元与a[left + 1]交换,并在分割阶段将i和j初始化为left+2和right-1。然后使用双向描述法,进行快排。
     

    归并排序

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

    算法思想

    将序列每相邻两个数字进行归并操作(merge),形成floor(n/2+n%2)个序列,排序后每个序列包含两个元素将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素。重复步骤2,直到所有元素排序完毕。

    算法步骤

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

    图示


     

    算法复杂度

    归并排序需要不仅时时间还有空间上的辅助,因此从时间复杂度和空间复杂度进行分析。

    时间复杂度
    总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列,时间为一常数,时间复杂度o(1).解决问题时间是两个递归式,把一个规模为n的问题分成两个规模分别为n/2的子问题,时间为2T(n/2).合并时间复杂度为O(n) O(n)O(n)。总时间T(n)=2T(n/2)+o(n) T(n)=2T(n/2)+o(n)T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解,其解是o(nlogn) o(nlogn)o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn) o(nlogn)o(nlogn)。
    空间复杂度
    如之前的算法步骤第一步,需要申请空间,该空间的作用时用于存放合并后的序列。因此需要初始序列规模n的空间,故空间复杂度为O(n) O(n)O(n)。

    稳定性

    元素的移动完全在合并操作上,对于合并的过程,我们完全可以添加条件限制相同的元素是否移动,所以合并排序是具有稳定性的排序。

    代码实现
     

    int * temp = new int[len];
    // 合并操作
    void merge(int arr[], int low, int mid, int high)
    {
    	int i, j, index;
    	for (int i = low; i <= high; ++i) //复制数组,空间复杂度为O(n)
    		temp[i] = arr[i];
    	for (i = low, j = mid + 1, index = low; i <= mid && j <= high; ++index)
    	{
    		if (temp[i] > temp[j])
    		{
    			arr[index] = temp[j];
    			++j;
    		}
    		else
    		{
    			arr[index] = temp[i];
    			++i;
    		}
    	}
    	while (i <= mid) arr[index++] = temp[i++];
    	while (j <= high) arr[index++] = temp[j++];
    	memset(temp, 0, sizeof(temp));
    }
    
    
    
    void Merge_Sort(int arr[], int low, int high)
    {
    	int mid;
    	if (low < high)
    	{
    		mid = (high + low) / 2;
    		Merge_Sort(arr, low, mid);
    		Merge_Sort(arr, mid + 1, high);
    		merge(arr, low, mid, high); // 归并
    	}
    }
    
    //非递归
    void Merge_Sort_NonRecursive(int arr[], int n)
    {
    	int step = 2, low, high, mid;  //二路归并步长
    	while (step <= n)
    	{
    		int curpos = 0;
    		while (curpos + step <= n)
    		{
    			high = curpos + step - 1;
    			low = curpos;
    			mid = curpos + step / 2 - 1;
    			merge(arr, low, mid, high);
    			curpos += step;
    		}
    		if (curpos < n - step / 2)  // 如过剩余个数比一个step长度还多,那么就在进行一次合并
    		{
    			mid = curpos + step / 2 - 1;
    			merge(arr, curpos, mid, n - 1);
    		}
    		step *= 2;
    	}
    	mid = step / 2 - 1; 
    	merge(arr, 0, mid, n - 1);
    }
    

    堆排序

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
    补充:
    堆:是一种特殊的数据结构。满足:

    必须时完全二叉树
    数组实现
    任一结点的值是其子树所有结点的最大值或最小值(根节点为:最大值时,称为“最大堆”,也称大顶堆;最小值时,称为“最小堆”,也称小顶堆。)

    算法步骤

    1.创建一个堆 H[0……n-1];
    2.把堆首(最大值)和堆尾互换;
    3.把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
    4.重复步骤 2,直到堆的尺寸为 1。

    图示

    时间复杂度

    堆排序的主要阶段为:初始化建立堆和重建堆。因此堆排序的时间复杂度由这两部分组成。

    初始化建立堆
    假如有N个节点,那么高度为h=logN h=logNh=logN,近似的时间复杂度就是O(N)。
    重建堆
    重建的过程,需要循环 n -1 次,每次都是从根节点往下循环查找,所以每一次时间是 logn,总时间:logn(n-1) = nlogn - logn。
    故综合以上可以得出堆排序时间复杂度:O(nlog2n) 因为堆排序是就地排序,空间复杂度为常数O(1) 。

    稳定性

    堆排序是不稳定的算法,它不满足稳定算法的定义。它在交换数据的时候,是比较父结点和子节点之间的数据,所以,即便是存在两个数值相等的兄弟节点,它们的相对顺序在排序也可能发生变化。

    代码实现
     

    /* 最大堆向下调整算法
    * param: index 调整开始位置
    *		 length 数组长度范围
    */
    void MaxHeap(int arr[], int index, int length)
    {
    	int node = index;
    	int child_index = node * 2 + 1;
    	int current = arr[node];
    	for (; child_index <= length; node = child_index, child_index = node * 2 + 1)
    	{
    		if (child_index < length && arr[child_index] < arr[child_index + 1])
    			++child_index;  // 子节点中的最大值
    		if (current > arr[child_index]) break;
    		else
    		{
    			arr[node] = arr[child_index];
    			arr[child_index] = current;
    		}
    	}
    }
    
    
    void Heap_Sort(int arr[], int n)
    {
    	for (int i = n / 2 - 1; i >= 0; --i)
    	{
    		MaxHeap(arr, i, n - 1);  // 建立最大堆
    	}
    	for (int i = n - 1; i > 0; --i)  // 从最后开始调整
    	{
    		int temp = arr[0];
    		arr[0] = arr[i];
    		arr[i] = temp;
    		MaxHeap(arr, 0, i - 1);  // 数组长度范围减一
    	}
    }
    

    适用场景总结

           当数据量,数据规模较大时,应该采用此3类排序算法,这样效率相比于之前的时间复杂度为O(n^2)的三种排序算法来说更高、更好些。
    这三类排序算法的结论:

    1.快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短
    2.堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况,适合超大数据量。这两种排序都是不稳定的
    3.若要求排序稳定,则可选用归并排序

    展开全文
  • 选择排序:稳定 适用于:数据量大,并且对稳定性有要求的情况。 public class MergeSort { public static void main(String[] args) { int[] a= {3,4,2,5,1}; mergeSort(a,0,a.length-1); System.out.print...
  • 1.归并排序的Java实现:代码如下:package com.zm.testSort;... * 归并排序 * @author zm */ public class MergeSort { public static void getMergeSort(int[] a) { if(a == null || a.length ) { ret
  • 排序算法——归并排序与快速排序

    万次阅读 多人点赞 2018-07-27 20:50:08
    今天总结一下两种性能优秀的排序算法,归并排序与快速排序。 首先,二者都运用了递归和分治的两种重要思想。在这里递归就不做详细介绍。 分治:顾名思义,分而治之,这是在排序中我们非常常见的一种思想,同时也是...
  • 归并排序 和快速排序一样,归并排序也是一种分治算法。它将输入数组分成两半,为这两半调用自己,然后合并已排序的两半。 merge函数的作用是合并两个部分。合并merge(arr, l, m, r)是一个关键过程,它假设arr[l…m] ...
  • 一、归并排序 基本思想:将数组A[0 … n-1]中的元素分成两个子数组A1[0 … n/2]和A2[n/2+1 … n-1]。分别对这两个子数组单独排序,然后将一排序的两个子数组归并成一个含有n个元素的有序数组。 归并排序包含不相邻...
  • 归并排序

    2021-03-10 14:56:55
    上一篇博文我初步讲解了插入排序,冒泡排序和选择排序。这几种排序算法的时间复杂度都是O()。时间复杂度比较高,比较适合小规模的...而且归并排序在解决大数据量时比较使用,读者可参考博文大数据中的归并排序。 ...
  • 摘要:归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用
  • 一、归并排序 1.1、分析 先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。 1.2、使用递推思路实现 ①先写出递推公式:【mergeSort(startIndex...
  • 》《顺序表数据结构在python中的应用》《python实现单向链表数据结构及其基本方法》《python实现单向循环链表数据结构及其方法》《python实现双向...文章python之战2019-04-241168浏览量算法基础:五大排序算法...
  • 归并排序的外部排序外部排序概念场景拓展实现函数归并外排序主函数将传入两个文件归并入mfile完成外排序 外部排序概念 参考:一眨眼的功夫了解什么是外部排序算法 按照内存大小,将大文件分成若干长度适当(小于...
  • 快速排序、归并排序、堆排序都是时间复杂度为O(N*logN)的排序,那么该用哪种排序算法呢? 快速排序、归并排序、堆排序空间复杂度的对比: 快速排序 归并排序 堆排序 O(logN) O(N) O(1) 发现,堆排序的堆...
  • java实现十大排序使用场景

    千次阅读 2020-04-22 20:12:24
    1、直接插入排序 1.1、基本思想 在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。 1.2、实例:...
  • O(nLogn)的归并排序

    2020-04-09 10:00:00
    之前几篇文章我介绍了三种O(n²)的排序算法《O(n²)的三个排序算法》(选择排序、插入排序...下面我将记录时间复杂度为nlog(n)的几种排序算法之一 —— 归并排序算法,这种排序算法适合大规模的数据排序,比之前的O(...
  • 归并排序及其适用范围

    千次阅读 2014-03-31 22:23:54
    ====[[C语言]]==== /*============================================================================= # # FileName: merge_sort_in_c.c # Desc: 归并排序 # # Author: gavinyao # Email: gav
  • 归并排序 详解

    千次阅读 2016-07-05 19:46:02
    该算法是采用分治法(Divide and Conquer)的一个非常典型的应用归并排序将两个已排序的表合并成一个表。2.归并排序优缺点优点 1.归并排序的效率达到了巅峰:时间复杂度为O(nlogn),这是基于比较的排序算法所能...
  • 目录写在前面参考源码1.选择排序特点算法步骤复杂度改进2.冒泡排序特点算法步骤复杂度最好情况最坏情况改进3....本文主要写了七种常见排序算法:选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序、
  • 每日一题--归并排序

    2020-07-14 19:33:54
    今天带来的是归并排序,与快排和堆排相比,归并排序使用场景就没有那么高了,面试中一般也很少遇到,不过它的排序思想还是很有意思的,主要是分拆和合并。理解了归并排序的思想,对一些其他的算法场景很有启发价值...
  • 因为对于这些排序算法,网上确实已经有很多图文并茂的讲解了,所以在此就不过多的解释,仅记录一下三种算法的实现和复杂度的对比 一、快速排序 import java.util.Random; public class QuickSort { private ...
  • 归并排序(MERGE-SORT)是利用分而治之的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。归并排序由...
  • 6种常用的排序算法的基本思想,性质和比较:快速排序,归并排序,冒泡排序、选择排序、插入排序、希尔排序。 (转载请注明出处) 了解并掌握排序的概念,并熟悉常见的几种排序算法; 掌握常见的几种排序算法的...
  • 另外,即使是同样的算法,不同的人写的代码,不同的应用场景下执行时间也可能差别很大。下面是一个测试数据: 测试的平均排序时间:数据是随机整数,时间单位是s 数据规模 快速排序 归并排序 希尔排序 堆排序 1000...
  • 数据结构—归并排序

    2018-09-13 17:00:47
    当我们要排序的文件太大以至于内存无法一次性装下或者在某些场景中有内存空间限制的时候,我们可以使用外部排序,将数据在外部存储器和内存之间来回交换,以达到排序的目的,这里我们先介绍外部排序算法,体会它面对...
  • 排序算法之归并排序(Merge Sort) 基本思想(分治法) 指的是两个已经排序好的序列合并成一个序列的操作。 算法分析: ——将长度为n的序列划分为n个长度为1的子序列。 ——进行两两归并比较,得到n/2个长度为2的...
  • 一、相关概念 逆序对:设 A 为一个有 n 个数字的有序集 (n&gt;1),其中所有数字各不相同。...归并排序归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(...
  • 试想一个场景,如果一份很大很大的数据需要排序,如果你没有足够的内存放入数据,这样子针对内存的内部排序是无法完成的,所以我们必须依靠磁盘去解决这个问题。 第一 将数据分成若干份(我们这里以10份为例子),每份...
  • 排序 插入类排序 1、直接插入排序 O(n2) O(n) O(n2) 每次将一个待排序元素按照关键字大小插入到已经排序的序列中去。 折半插入排序 O(n2) O(n) O(n2) 折半查找法寻找元素插入位置。与1最大不同在于,1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,187
精华内容 6,874
关键字:

归并排序应用场景