当前位置 博文首页 > 文章内容

    数据结构之排序(二)--归并排序:ZHAO

    作者:shunshunshun18 栏目:未分类 时间:2021-10-17 20:33:35

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    推荐 IIS7批量FTP管理工具 IIS7批量FTP管理
    IIS7批量FTP管理功能说明:
    1、可批量导入,导出FTP信息
    2、其他ftp工具有的功能,我们也有
    3、特色功能:可以定时上传下载
    4、数据信息列表化、一眼就能知道那个是那个
    5、批量连接 标签页式切换 方便快捷
    6、7大连接模式 更多好的兼容
    7、内嵌编辑器 有效解决普通txt记事本乱码
    8、锁屏功能 当程序有规定时间内没人操作,则自动锁程序。输入密码才可以正常操作

    本产品适用于:懒得记录FTP信息和有批量定时备份,上传下载的运维或站长。

    图:


    IIS7批量FTP管理

    一、递归实现归并排序

    其思想说白了就是先分后合,先将需要排序的数组迭代或递归每次分成两份直到分成n个数为止,然后再将n个数凉两两排序后合并成n/2个数组,以此类推直到合并排序成一个数组。


    代码实现:

       1、代码中采用的是线性表的顺序存储结构来存放数据的:

    typedef void List_Node;     //用于复用加入元素
    
    typedef unsigned long Seqlist_Node;   //为了重复使用,所以在这里使用的地址来操作的, 这里要用unsigned long类型,unsingesd int类型是在32位系统下使用的
    
    typedef struct  //存储线性表的结构体
    {
       	int MAXSIZE; //线性表最大存储
    	int length;  //线性表当前存储大小
    	Seqlist_Node* node;  //指向下一个元素的地址,这样做的好处是能动态的申请数组,如果不这样,这里是数组
    }Tseqlist;
    
    Tseqlist* List_Create(int MAXSIZE)   //创建线性表
    {
    	Tseqlist* list  = NULL;
    	if(MAXSIZE > 0)
    	{
    		list = (Tseqlist*)malloc( sizeof(Tseqlist) + sizeof(Seqlist_Node)*MAXSIZE );
    	}
    	if(list != NULL)
    	{
    		list->MAXSIZE = MAXSIZE;
    		list->length = 0;
    		list->node = (Seqlist_Node*)(list + 1);  //node指向下一个结构体元素的首地址
    	}
    	return list;
    }

        2、基于上面代码实现归并排序:

    在代码中merge函数是用来将一个数组的前半部分(已经有序)和它的后半部分(已经有序)排序成一个有序的数组,其中temp[]数组是过渡数组。

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    
    void merge(int arr[],int temp[],int left,int mid,int right){
            int i = left;//左序列指针
            int j = mid+1;//右序列指针
            int t = 0;//临时数组指针
            while (i<=mid && j<=right){
                if(arr[i]<=arr[j]){
                    temp[t++] = arr[i++];
                }else {
                    temp[t++] = arr[j++];
                }
            }
            while(i<=mid){//将左边剩余元素填充进temp中
                temp[t++] = arr[i++];
            }
            while(j<=right){//将右序列剩余元素填充进temp中
                temp[t++] = arr[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while(left <= right){
                arr[left++] = temp[t++];
            }
        }
    
    void mergSort(int arr[], int temp[], int start, int end)  //1.先将分成两份,排序并合并
    {
    	int m=0;  //分为两组数的中间数的位置
    	//递归结束条件
    	if(start < end)
    	{
    		//递归
    		m = (start + end)/2;
    		//1.分出的第一个
    		mergSort(arr, temp, start, m );  //将原始数据的第一部分归并排序到temp(即utlmate_arr)中保存
    
    		//2.分出的第二个
    		mergSort( arr, temp, m+1, end );  //将第二部分归并排序并保存
    
    		//3.排序合并
    
    		merge( arr,temp , start, m, end );  //将temp[start]~temp[m]插入到ultimate_arr[m+1]~ultimate_arr[emd]
    
    	}
    }
    
    void sortMerging( int arr[] ,int arr1[], int length)
    {
    	mergSort(arr, arr1, 0, length-1 );
    }  
    
    void main()
    {
    		int sr[9] ={50,10,90,30,70,40,80,60,20};
    
    		int sr1[9];
    
    		//merg(sr,sr1,0,4,8);
    
    
    	int i = 0;
    	for(; i<9;i++)
    	{
    		printf("%d-->",sr[i]);
    	}
    printf("\n\n\n");
    
    	sortMerging(sr,sr1,9);
    
    	for(i = 0; i<9;i++)
    	{
    		printf("%d-->",sr[i]);
    	}
    printf("\n");
    system("pause");
    }



    cs