精华内容
下载资源
问答
  • 归并排序C++算法实现

    万次阅读 2019-03-31 15:41:17
    定义:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子...

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

    简单的来说,归并排序主要分为三步,一是对数组的划分,二是对数组的排序,三是对数组的合并。划分的大小是可以随自己的想法而设置,但是一般都是以2为单位,这样最小的一组的排序就比较方便。

    具体一个简单的例子:

    设有数列{6,202,100,301,38,8,1}

    初始状态:6,202,100,301,38,8,1

    第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

    第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

    第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

    总的比较次数为:3+4+4=11;

    逆序数为14;

    在利用算法实现的时候,需要利用递归的思想,函数的入口是整个数组,不断进行划分,直到划分的数组只剩下一个或两个元素为止,对这一组进行排序后,再按原来划分的大小还原并排序,这里利用一个新的数组比较方便,将两个排序后的数组,再从小到大一个一个放入新的数组。

    具体代码:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    void merge(int *data,int start,int end,int *result) 
    {
        int left_length = (end - start + 1) / 2 + 1;    
        int left_index = start;
        int right_index = start + left_length;
        int result_index = start;
        while(left_index<start + left_length && right_index <end + 1)  //store data into new array
        {
            if(data[left_index] <= data[right_index])
                result[result_index++] = data[left_index++];
            else
                result[result_index++] = data[right_index++];
        }
        while(left_index < start + left_length)
            result[result_index++] = data[left_index++];
        while(right_index <end+1)
            result[result_index++] = data[right_index++];
    }
    
    void merge_sort(int *data,int start,int end,int *result)
    {
        if(1 == end - start)   //last only two elements
        {
            if(data[start] > data[end])
            {
                int temp = data[start];
                data[start] = data[end];
                data[end] = temp;
            }
            return;
        }
        else if (end == start)
            return; //last one element then there is no need to sort;
        else{
            //continue to divide the interval
            merge_sort(data, start, (end - start + 1) / 2 + start, result);
            merge_sort(data, (end - start + 1) / 2 + start + 1, end, result);
            //start to merge sorted data
            merge(data, start, end, result);
            for (int i = start; i <= end;++i)
            {
                data[i] = result[i];
            }
        }
    
    }
    //example
    int main()
    {
        int data[] = {5,3,6,7,3,2,7,9,8,6,34,32,5,4,43,12,37};
        int length = 17;
        int result[length];
        cout << "before sorted:"<<'\n';
        for (int i = 0; i < length;i++)
            cout << data[i]<<' ';
        cout << '\n'
             << "after sorted:"<<'\n';
        merge_sort(data, 0, length - 1, result);
        for (int i = 0; i < length;i++)
            cout << result[i]<<' ';
        return 0;
    }

    排序实现

    展开全文
  • 插入排序包括:直接插入排序、希尔排序、归并排序。 直接插入排序算法,将数组划分为两种,“有序数组块”和“无序数组块”,一个个从无序数组取出元素,插入到有充数组的合适位置上,即完成排序,最大的缺点在于要...
        

    一天一个算法,边回想算法细节,边捡回C++,试验性程序,留作记念。

    插入排序包括:直接插入排序、希尔排序、归并排序。
    直接插入排序算法,将数组划分为两种,“有序数组块”和“无序数组块”,一个个从无序数组取出元素,插入到有充数组的合适位置上,即完成排序,最大的缺点在于要对数组元素进行移动。

    希尔排序加入了一种叫做“缩小增量排序法”的思想,增量取法为:count/2、(count/2)/2、...、1。
    希尔算法实现如下:

    #include <iostream>
    
    using namespace std;
    int arrs[] = { 23, 65, 12, 3, 8, 76, 345, 90, 21, 75, 34, 61 };
    int arrLen = sizeof(arrs) / sizeof(arrs[0]);
    
    void shellSort(int * arrs){
        int step = arrLen / 2;      //初始增量
        while(step > 0){
            //无序部分
            for(int i = step; i < arrLen; i++){
                int temp = arrs[i];
                int j;
                //子序列中的插入排序,这是有序部分
                for(j = i-step; j>=0 && temp < arrs[j]; j=j-step)
                    //在找到当前元素合适位置前,元素后移
                    arrs[j+step]=arrs[j];       
                arrs[j+step]=temp;
            }
            step /= 2;
        }
    }
    
    int main()
    {
        shellSort(arrs);
        for (int i = 0; i < arrLen; i++)
            cout << arrs[i] << endl;
        return 0;
    }
    

    归并排序是采用分治法的一个非常典型的应用,它要做两件事情:
    第一: “分”, 就是将数组尽可能的分,一直分到原子级别。
    第二: “并”,将原子级别的数两两合并排序,最后产生结果。

    至于二个有序数列合并,只要比较二个数列的第一个数,谁小就先取谁安放到临时队列中,取了后将对应数列中这个数删除,直到一个数列为空,再将另一个数列的数据依次取出即可。

    #include <iostream>
    
    using namespace std;
    int arrs[] = { 23, 65, 12, 3, 8, 76, 345, 90, 21, 75, 34, 61 };
    int arrLen = sizeof(arrs) / sizeof(arrs[0]);
    int * tempArr = new int[arrLen];
    
    void mergeArray(int * arrs, int * tempArr, int left, int middle, int right){
        int i = left, j = middle ;
        int m = middle + 1, n = right;
        int k = 0;
    
        while(i <= j && m <= n){
            if(arrs[i] <= arrs[m])
                tempArr[k++] = arrs[i++];
            else
                tempArr[k++] = arrs[m++];
        }
        while(i <= j)
            tempArr[k++] = arrs[i++];
        while(m <= n)
            tempArr[k++] = arrs[m++];
    
        for(i=0; i < k; i++)
            arrs[left + i] = tempArr[i];
    }
    
    void mergeSort(int * arrs, int * tempArr, int left, int right){
        if(left < right){
            int middle = (left + right)/2;
            mergeSort(arrs, tempArr, left, middle);
            mergeSort(arrs, tempArr, middle + 1, right);
            mergeArray(arrs, tempArr, left, middle, right);
        }
    }
    
    int main()
    {
        mergeSort(arrs, tempArr, 0, arrLen-1);
        for (int i = 0; i < arrLen; i++)
            cout << arrs[i] << endl;
        return 0;
    }
    
    展开全文
  • 作者: dreamcatcher-cx ...本文版权归作者和博客园共有,欢迎转载,但...归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小...

    作者: dreamcatcher-cx
    出处: http://www.cnblogs.com/chengxiao/
    本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在页面明显位置给出原文链接。

    基本思想

    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    分而治之

    在这里插入图片描述
    可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

    合并相邻有序子序列

    再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。
    在这里插入图片描述
    在这里插入图片描述

    代码实现(C++实现)

    #include <iostream>
    using namespace std;
    void merge(int a[], int begin, int mid, int end, int temp[]){
    	int i = begin;
    	int j = mid+1;
    	int t = begin;
    	while(i<=mid && j<=end){
    		if(a[i] <= a[j])
    			temp[t++] = a[i++];
    		else
    			temp[t++] = a[j++];
    	}
    	while(i<=mid){
    		temp[t++] = a[i++];
    	}
    	while(j <= end){
    		temp[t++] = a[j++];
    	}
    	for(int i = begin; i <= end; i++)
    		a[i] = temp[i];
    }
    void mergesort(int a[], int begin, int end, int temp[]){
    	if(begin >= end)
    		return;
    	int mid = (begin + end) /2;
    	mergesort(a, begin, mid, temp);
    	mergesort(a, mid+1, end, temp);
    	merge(a, begin, mid, end, temp);
    }
    
    int main(void){
    	int a[10] = {3, 1, 5, 2, 7, 8, 9, 0, 6, 4};
    	int temp[10];
    	mergesort(a, 0, 9,temp);
    	return 0;
    }
    

    执行结果
    0 1 2 3 4 5 6 7 8 9

    结语

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    展开全文
  • 本文主要是针对归并排序进行分析,分别从递归的角度和分治的角度对归并进行认识,并附上c++实现 一、归并排序介绍(代码在大标题二) 同样,这里我们以一个乱序数组为例。有数组 a[5] a[0] a[1] a[2] a[3] a...


    前言

    本文继续排序算法的回顾。本文主要是针对归并排序进行分析,分别从递归的角度和分治的角度对归并进行认识,并附上c++的实现


    一、归并排序介绍(代码在大标题二)

    同样,这里我们以一个乱序数组为例。有数组 a[5]

    a[0] a[1] a[2] a[3] a[4]
    3 2 7 1 0

    len = 5
    startIndex = 0
    endIndex = n - 1 = 5 - 1 = 4

    1.1 思路

    归并排序的中心思路可以概括为从局部有序到整体有序。具体来说,就是可以将原数组进行分割(分治),分别进行运算(递归),实现局部有序,然后通过一个外排进而实现整体有序

    1.2 基本流程

    结合a[5],就是先将数组切成两半
    在这里插入图片描述
    然后进行局部的排序,并借助两个指针实现外排(借助辅助数组,a和b中的较小值填入辅助数组,并且右移,直到其中一个指针遍历了其所在的子数组的全部元素,结束并将另外的数组的剩余元素全部拷贝到辅助数组),进而实现整体有序。(图片这里仅展示了第一次分治的过程,实际上伴随着递归,子数组也会被再一次分治,外排,直到无法进行分割,直观来说,就是辅助数组被构建了logN次)
    在这里插入图片描述
    最后将辅助数组数据拷贝到原数组即可。

    时间复杂度分析:

    • 子数组元素的数量是原数组元素的数量的一半
      T(N) = 2T(N/2)
    • 此外,外派的复杂度为O(N),故有
      T(N) = 2T(N/2) + O(N)
    • 根据Master公式有
      log(b, a) > d 复杂度为O(N^log(b, a) )
      log(b, a) = d 复杂度为O((N^d) * logN)
      log(b, a) < d 复杂度为O(N^d )
      所以有归并的时间复杂度为:O(N*logN)

    二、代码

    #include <iostream>
    #include <vector>
    using namespace std;
    
    void Merge(vector<int> &v, int start, int mid, int end)
    {
    	vector<int> temp(end - start + 1, 0);
    	int i = 0;
    	int p1 = start;	//左侧指针
    	int p2 = mid + 1;	//右侧指针
    	//越界时跳出
    	while (p1 <= mid && p2 <= end)
    	{
    		temp[i++] = v[p1] < v[p2] ? v[p1++] : v[p2++];
    	}
    	//拷贝剩余的数据到辅助数组
    	while (p1 <= mid)
    	{
    		temp[i++] = v[p1++];
    	}
    	while (p2 <= end)
    	{
    		temp[i++] = v[p2++];
    	}
    	//数据拷贝
    	for (i = 0; i < temp.size(); i++)
    	{
    		v[start + i] = temp[i];
    	}
    }
    
    void SortProcess(vector<int> &v, int start, int end)
    {
    	if (start == end)
    	{
    		return;
    	}
    	int mid = start + ((end - start) >> 1);
    	SortProcess(v, start, mid);
    	SortProcess(v, mid + 1, end);
    	//合并
    	Merge(v, start, mid, end);
    }
    
    void MergeSort(vector<int> &v)
    {
    	if (v.size() < 2)
    	{
    		return;
    	}
    	//分插
    	SortProcess(v, 0, v.size()-1);
    }
    
    
    int main()
    {
    	//测试
    	vector<int> v = { 3,2,7,1,0 };
    
    	for (int i = 0; i < v.size(); i++)
    	{
    		cout << v[i] << "\t";
    	}
    	cout << endl;
    
    	MergeSort(v);
    
    	for (int i = 0; i < v.size(); i++)
    	{
    		cout << v[i] << "\t";
    	}
    	cout << endl;
    
    	system("pause");
    	return 0;
    }
    

    总结

    笔者在回顾的时候,这段编码还是错误挺多次的,主要问题出现在Merge函数部分,即辅助数组构建时候出了问题,究其原因,主要是对递归的理解不到位。总结来讲,归并排序的各个阶段不难理解,但是当这些内容串联起来是容易犯一些错误。

    展开全文
  • #include <iostream> #include <vector> using namespace std; void merge(vector<int>& a, int left, int mid, int right){ vector<int> temp; int m = left, n = mid + ... while ...
  • 归并排序算法的分治思想 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列 解决:使用归并排序递归的排序两个子序列 合并:合并两个已排序的子序列以产生已排序的答案 当待排序的序列长度为1时,...
  • 归并排序算法C++实现

    2010-11-20 09:23:00
    归并排序算法是几种排序算法里面时间性能较好的了为O(nlogn) 归并排序时分治法的一个典型应用,它先将要排序的序列分成两分,分别对每一份用归并排序尽心排序,然后在将两份合并在一起,形成一个有序 的序序列。 ...
  • 归并排序算法C++实现归并排序概述归并排序图示归并排序程序实现 归并排序概述 第一步:首先将数组对半分 再对半分 直到不能分为止 归并排序图示 归并排序程序实现 #include <iostream> #include <vector...
  • 归并排序c++实现

    2021-03-11 14:02:52
    归并排序算法c++实现 void merge(vector<int>&vec,int left,int rightBegin,int rightbound) { int i = left; int j = rightBegin; int k = 0; vector<int>vecTmp(rightbound - left+1,0); ...
  • 文章目录归并排序介绍c++实现递归方式迭代实现c++源码及测试代码测试结果 归并排序介绍 归并排序(merge sort)算法采用了分而治之的策略,将大问题分解为小问题去求解,将小问题求解的结果进行合并形成大问题的解,...
  • C++实现归并排序算法

    2020-08-19 11:32:31
    主要为大家详细介绍了C++实现归并排序算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 归并排序C++实现

    2021-03-30 09:05:33
    6.归并排序归并排序的基本思想代码实现适用说明 归并排序的基本思想 1.基本思想(递归): 思路来源:两个有序序列,按序合并只需遍历一趟,效率较高; 归并排序:利用分-治-合的思想,先将待排序列划分为子序列,...
  • 归并排序 C++实现

    2020-05-14 21:42:03
    参考以下博文实现归并排序,在此记录,便于温习。 图解排序算法(四)之归并排序https://www.cnblogs.com/chengxiao/p/6194356.html 基本思路:(递归实现) 划分。将数组划分为两个长度较短的子片段,直到子片段中只有...
  • 归并排序思想:将原数组拆成前后两半,对前半部分和后半部分分别执行排序过程,再将排好序的前后两部分合并。 典型的分治问题,而分治一般用递归去解。 归并排序也是基于比较的排序。 代码: template<typename T...
  • 主要介绍了C++实现归并排序算法,结合实例形式详细分析了归并排序算法的原理、实现步骤、操作技巧与使用方法,需要的朋友可以参考下
  • 关于归并排序C++实现及复杂度分析
  • 【排序算法归并排序(C++实现)

    万次阅读 多人点赞 2018-04-03 23:24:02
    转自jimye原创博客,出处链接:https://blog.csdn.net/left_la/article/details/8656953个人加...常见的归并排序有两路归并排序(Merge Sort),多相归并排序(Polyphase Merge Sort),Strand排序(Strand Sort)。...
  • 归并排序是典型的分治法思想排序,其先归再并,基本思想如下: 1. 从下往上的归并排序:将待排序的数列分成若干个长度为1的子数列,然后将这些数列两两合并;得到若干个长度为2的有序数列,再将这些数列两两...
  • C++ 归并排序算法实现

    2016-04-07 14:22:44
    c++归并排序函数实现如下:void merge_sort(vector<int> &data, int start, int end) { if (start ) { int mid = (start + end) / 2; merge_sort(data, start, mid); merge_sort(data, mid + 1
  • C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
  •  if(r[i][j]) //含有2个元素的子序列合并后又会形成含四个已经排序好的序列,二个含有四个排序好的元素的序列会合并成  //含有8个元素的有序序列,后面以此类推,每次合并的两个序列都是提前排序好的。   r1...
  • 归并排序 c++实现

    2018-09-03 17:38:33
    归并排序归并排序采用的是分冶算法,将两个有序排列,合成新的有序排列。 时间复杂度是 O(nlogn); 优点是高效稳定,缺点是会多占用一部分内存。 coder: #include&lt;iostream&gt; #include&lt;...
  • void merge_sort(vector<int>& A, int l, int r){ if(l < r){ int m = (l+r) / 2; merge_sort(A, l, m); merge_sort(A, m+1, r); merge...
  • C++实现快速排序归并排序算法设计,用快速排序和归并排序算法,对记录进行排序。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 993
精华内容 397
关键字:

归并排序c++算法实现

c++ 订阅