精华内容
下载资源
问答
  • 综合排序
    2022-03-30 20:58:34

    《数据结构课程设计》报告

    日期:
    项目名称: 综合排序
    一、项目简介和需求分析
    排序(sorting是计箅机程序设计的一种重要操作,它的功能是将一组任意顺序数据元素(记录),根据某一个(或几个)关键字按一定的顺序里新排列成为有序的序列。由于待排序的记录数量不同,使得排序过程中涉及的存储器的不同,可将排序方法分为两大类:一类是内部排序,指的是待排序的记录存放在计算机随机存储器中进行的排序过程;另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需要对外存进行访问的排序过程。本次课程设计主要是关于内部排序的。
    内部排序的方法很多,但就其全面性能而言,很难提出一种被认为是最好的方法,每一种方法都有各自的优缺点,适合在不同的环境(如记录的初始排列状态等)下使用。
    本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质,排序的应用,排序的分类,利用C++语言采用数组存储结构编程实现了本排序综合系统,该系统包含了几种常见的排序方法,有直接插入排序、希尔排序、冒泡排序、快速排序、简单排序。

    二、项目设计思路:
    (包括数据结构(逻辑结构及存储结构的选择及理由)、程序功能模块设计、 每个模块的输入/输出设计等,可以画类图、流程图等)

    问题描述:
    排序是程序设计的基本操作,不同的排序算法的性能也不相同。
    问题要求:
    (1)至少采用四种排序方法实现随机生成100个数值的排序(可采用的排序方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 
    (2)统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。

    三、源程序及注释(说明每个文件的文件名即可,电子档的*.h和*.cpp文件压缩传到FTP上):

    
    
    摘   要	1
    1 引  言	2
    2 系统分析	3
    2.1 功能需求	3
    2.1.1总体要求	3
    2.1.2 本人所做模块	3
    2.2数据需求	3
    3 详细设计与分析	4
    31设计思路	4
    3.2整体设计方案	5
    3.3各种操作函数	6
    3.4主函数	6
    3.5编码	9
    4 测试系统	13
    4.1设计测试数据	14
    4.2测试结果与分析	14
    结  论	16
    致  谢	17
    参考文献	18
    附录	19
    
    
    摘   要
    排序(sorting是计箅机程序设计的一种重要操作,它的功能是将一组任意顺序数据元素(记录),根据某一个(或几个)关键字按一定的顺序里新排列成为有序的序列。由于待排序的记录数量不同,使得排序过程中涉及的存储器的不同,可将排序方法分为两大类:一类是内部排序,指的是待排序的记录存放在计算机随机存储器中进行的排序过程;另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需要对外存进行访问的排序过程。本次课程设计主要是关于内部排序的。
    内部排序的方法很多,但就其全面性能而言,很难提出一种被认为是最好的方法,每一种方法都有各自的优缺点,适合在不同的环境(如记录的初始排列状态等)下使用。
    本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质,排序的应用,排序的分类,利用C语言采用数组存储结构编程实现了本排序综合系统,该系统包含了几种常见的排序方法,有直接插入排序、希尔排序、冒泡排序、快速排序、简单排序。
    
    关键词:内部排序,外部排序,重新排列,关键字
    
    1 引  言 
    1.1问题的提出
    排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
    排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,其中包含冒泡排序,直接插入排序,简单选择排序,希尔排序,快速排序,堆排序等,各有其特点。
    对排序算法比较的分析可以遵循若干种不同的准则,通常以排序过程所需要的算法步数作为度量,有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间,例如,当键是较长的字符串时,常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录,且记录都很大时,还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑所用时间作为复杂性的度量。
    1.2C语言
    C语言既有高级语言的特点,又具有汇编语言的特点;既是一个成功的系统设计语言,有时一个使用的程序设计语言;既能用来编写不依赖计算机硬件的应用程序,又能用来编写各种系统程序;是一种受欢迎、应用广泛的程序设计语言。
    1.3C语言发展过程
    1973年,美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言,他取了BCPL的第二个字母作为这种语言的名字,这就是C语言。
    1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。
    1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming Language》,从而使C语言成为目前世界上流行最广泛的高级程序设计语言。	
    1.4任务与分析
    前面分析了排序的种类以及过程,因此,本系统实现了几种常用的排序方法, 包括:直接插入排序、希尔排序、冒泡排序、非递归的快速排序、简单排序。
    2 系统分析
    2.1 功能需求
    2.1.1总体要求
        任务:
    机函数产生N个随机整数(20000以上),对这作数进行多种方法进行排序。
    要求:
    1)	至少采用4种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。
    2)	统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。 
    如果采用4种或4种以上的方法者,可适当加分。
    2.1.2 本人所做模块
    	通过对任务的要求分析,我将任务分成了几个模块,从而实现了任务的总体要求。包括了输入模块、选择排序方法模块、输出模块。其中:
    1、输入模块
    利用随机函数产生N个数(20000以上),产生的数据个数由用户自己输入。
    2、选择排序方法模块
    在菜单中通过输入相应的选项编号来选择采用何种算法排序,包括的排序算法有:直接插入排序、希尔排序、冒泡排序、快速排序、简单排序。
    3、输出模块
    输出排序前的,或者排序后的数据元素到屏幕上显示,并且输出以某种算法排序后的数据元素到文件中保存。
    最后让主函数对这几个模块进行调用,从而实现全部功能。
    2.2数据需求
    利用随机函数产生的随机数。
    3 详细设计与分析
    31设计思路
    1、直接插入排序
    思路:设有一组关键字{K1,K2,……,Kn},排序开始便认为K1是一个有序的序列,让 K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为 2的有序序列,使之成为个表长为3的有序序列,依次类推,最后让Kn插入上述表长为 n-1的有序序列,得到一个表长为n的冇序序列。
    2、希尔排序
    思路:先取一个正整数dl(dl<n),把全部记录分成dl个组,所有距离为dl的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2<dl),重复上述分组和排序操作,直到取di=1,即所有记录成为一个组为此.一般选dl约为n/2,d2为dl/2,……,di=l
    3、冒泡排序
    思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第n个和第n-1个数,将小数放前,大数放后,然后比较第n-1个数和第n-2个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最小的数放到了最前。在第二趟:仍从第n个数开始比较,将小数放前,大数放后,一直比较到第二个数(第一的位置上已经是最小的),第二趟结束,在数第二的位置上得到一个新的最小数(其实在整个数列中是第二小的数)。如此下去,重复以上过程,直至最终完成排序。用二循环实现,外循环变量设i,内循环变量设为j。每次进行比较的两个元素都是与内循环j有关的,它们可以分别用a[j]和a[j+1]标识。
    4、快速排序
    思路:以第一个关键字K1为控制字,将[K1,K2..Kn]分成两个子区,使左区的所有关键字小于等于K1,右区所有关键字大于等于K1,在子区内数据尚处于无序状态。
    将右区首、尾指针保存入栈,对左区进行与第(1)步相类似的处理,又得到它的左子区和右子区。
    重复第(1)、(2)步,直到左区处理完毕。然后退栈对一个个子区进行相类似的处理,直到栈空。
    5、简单排序       
    思路:在n个记录中,用两重循环,外层循环i从第一个元素a[0]开始至最后一个 元素a[n-l],内层循环j从外层循环所值元素a[i]的下—个元素a[jl=a[i+l]开始至最后一个元素a[n-l]搜索,只要找到比a[i]小的元素,便与a[i]交换,如此重复执行操作,当外层循环完毕后,全部记录就排序完成了。
    3.2整体设计方案 
    此课题是研究的是排序问题,为了直观和方便,画出流程图如下图1:
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    	
    图1 程序总流程图
    
    
    通过流程图可以从中看出操作过程以及函数间的调用关系。
    3.3各种操作函数
    根据模块的划分,将函数对模块进行实现,主要函数如下:
    (1)创建一个数组函数:int creat()
    (2)输出数组函数:void print(struct element a[],int n)
    (3)保存函数:void save(struct element a[],int n,char filename[])
    (4)直接插入排序函数:void insertsort(struct element a[],int n)
    (5)希尔排序函数:void shellsort(struct element a[],int n)
    (6)冒泡排序函数:void bublesort(struct element a[],int n)
    (7)快速排序分区处理:int partition(struct element a[],int low,int high)
    (8)快速排序函数:void quicksort(struct element a[],int low,int high)
    (9)简单排序函数:void selesort(struct element a[],int n)
    3.4主函数
    //==========通过该函数对其他函数的调用,实现系统功能
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int num,c;
    	bool flag=0;
    	clock_t start,end;
    	char file1[300]="直接插入排序.txt";
    	char file2[300]="希尔排序.txt";
    	char file3[300]="冒泡排序.txt";
    	char file4[300]="快速排序.txt";
    	char file5[300]="选择排序.txt";
    	while(1)
    	{
    		menu();
    		printf("请输入操作选项:");
    		scanf("%d",&c);
    		if(c!=1&&flag==0)
    			printf("处理错误,请先产生随机数...\n");
    		else
    		{
    			switch(c)
    			{
    			case 1:num=creat();
    				print(list,num);
    				printf("\n");
    				flag=1;
    				break;
    			case 2:start=clock();
    				insertsort(list,num);
    				end=clock();
    				printf("直接插入排序后的结果:\n");
    				print(list,num);
    				save(list,num,file1);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 3:start=clock();
    				shellsort(list,num);
    				end=clock();
    				printf("希尔排序后的结果:\n");
    				print(list,num);
    				save(list,num,file2);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 4:start=clock();
    				bublesort(list,num);
    				end=clock();
    				printf("冒泡排序后的结果:\n");
    				print(list,num);
    				save(list,num,file3);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 5:start=clock();
    				quicksort(list,0,num-1);
    				end=clock();
    				printf("快速排序完成!\n");
    				printf("快速排序后的结果:\n");
    				print(list,num);
    				save(list,num,file4);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 6:start=clock();
    				selesort(list,num);
    				end=clock();
    				printf("选择排序后的结果:\n");
    				print(list,num);
    				save(list,num,file5);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 0:exit(1);
    			default:printf("输入错误,请重新输入...\n");
    			}
    		}
    	}
    	system("pause");
    	return 0;
    } 
    3.5编码
    //=========数据类型定义
    #define  size 1000000
    struct element
    {
    	int key;
    }list[size];
    
    //==========直接插入排序模块
    void insertsort(struct element a[],int n)
    {
    	int i,j;
    	struct element x;
    	for(i=1;i<n;i++)
    		if(a[i].key<a[i-1].key)
    		{
    			x=a[i];
    			a[i]=a[i-1];
    			for(j=i-1;x.key<a[j].key;j--)
    				a[j+1]=a[j];
    			a[j+1]=x;
    		}
    	printf("直接插入排序完成!\n");
    }
    
    //=========希尔排序模块
    void shellsort(struct element a[],int n)
    {
    	int i,j,dk;
    	struct element x;
    	dk=n/2;
    	while(dk>0)
    	{
    		for(i=dk;i<n;i++)
    			if(a[i].key<a[i-1].key)
    			{
    				x=a[i];
    				for(j=i-dk;j>0&&x.key<a[j].key;j-=dk)
    					a[j+dk]=a[j];
    				a[j+dk]=x;
    			}
    		dk=dk/2;
    	}
    	printf("希尔排序完成!\n");
    }
    
    //=========冒泡排序模块
    void bublesort(struct element a[],int n)
    {
    	int i,j;
    	struct element temp;
    	for(i=0;i<n;i++)
    	{
    		for(j=n;j>=i;j--)
    			if(a[j+1].key<a[j].key)
    			{
    				temp=a[j+1];
    				a[j+1]=a[j];
    				a[j]=temp;
    			}
    	}
    	printf("冒泡排序完成!\n");
    }
    
    //==========快速排序模块
    int partition(struct element a[],int low,int high)
    {
    	int i,j;
    	struct element x;
    	i=low;
    	j=high;
    	x=a[i];
    	while(i<j)
    	{
    		while((i<j)&&(a[j].key>=x.key))
    			j--;
    		if(i<j)
    		{
    			a[i]=a[j];
    			i++;
    		}
    		while((i<j)&&(a[i].key<=x.key))
    			i++;
    		if(i<j)
    		{
    			a[j]=a[i];
    			j--;
    		}
    	}
    	a[i]=x;
    	return i;
    }
    void quicksort(struct element a[],int low,int high)
    {
    	int i;
    	if(low<high)
    	{
    		i=partition(a,low,high);
    		quicksort(a,low,i-1);
    		quicksort(a,i+1,high);
    	}
    }
    
    //==========简单排序模块
    void selesort(struct element a[],int n)
    {
    	int i,j,z;
    	struct element temp;
    	for(i=0;i<n;i++)
    	{
    		z=i;
    		for(j=1+i;j<n;j++)
    		{
    			if(a[z].key>a[j].key)
    				z=j;
    		}
    		if(z!=i)
    		{
    			temp=a[i];
    			a[i]=a[z];
    			a[z]=temp;
    		}
    	}
    
    	printf("选择排序完成!\n");
    }
    4 测试系统
    对于所有执行过程,通过图片最好说明问题了:
    程序开始如图2所示:
    
    图2 开始界面图
    4.1设计测试数据
    	用随机函数产生的20个随机数作为测试实例:
    
    
    图3 产生随机数
    
    4.2测试结果与分析	
    
    图4 直接插入排序结果图
    
    
    图5 希尔排序结果图
    
    
    图6 冒泡排序结果图
    
    
    图7 快速排序结果图
    
    
    图8 简单排序结果图
    结  论
    通过这次课程设计的学习让我学会了许多,让我对我们的专业知识有了很大理解! 
    在这次课程设计中,独立完成了在数组存储结构下的每种排序算法。排序算法共有五个:插入排序、希尔排序、冒泡排序、快速排序、选择排序。同时也实现了随机数的生成。并把排序后的结果保存在不同的文件中。虽然在算法完成的过程中也在网上査阅了一些资料,但对这次课程设计的成果还是比较满意的。
    同时在完成这个课程设计后,我也学到了很多知识,并能熟练的掌握他们了。熟练的撑握C语言的文件读写操作。掌握了每种排序算法的基本思想,并学会了编写程序的一般步骤:思考问题,写出解决方案,写出伪代码,完成代码,调试程序。不像以前那样开始就直接写代码。
    致  谢
    这次课程设计能够顺利完成,当然要感谢老师和同学的帮助。没有老师的悉心指导和督促,就不可能这么顺利和按时完成任务,真的非常感谢!老师教导我们:首先要对程序的设计要求有一个比较明确的认识,然后系统分析与系统设计,最后是代码设计与调试。程序实现上,设计了简单的菜单界面,将各个功能集中出现在主菜单中,便于调用。在整个过程中周围的同学也给了不少帮助,而且帮忙解决了很多想不通的问题,在此真的非常感激每个人!希望在今后学习中大家一起互相学习,共同进步!编写程序的过程是辛苦与快乐的,程序的编写原则很重要,只要我们在编程,就必须不断改进,才能更好提高编程能力。
    参考文献
    [1]严蔚敏等编著.数据结构(C语言版).北京:淸华大学出版社.2003
    [2]严蔚敏等编著.数据结构题集(C语言版>.北京:清华大学出版社.2003
    [3]李春葆等编著.数据结构教程(C语言版>.北京:淸华大学出版社.2006
    [4]朱立华等编著.C语言程序设计.北京:人民邮电出版社.2009
    
    附录
    #include "stdafx.h"
    #include<iostream>
    #include<stdlib.h>
    #include<time.h>
    #define  size 1000000
    //===========^调用库函数
    
    struct element
    {
    	int key;
    }list[size];
    //==========^结构体模板
    
    int creat()
    {
    	int i;
    	int num;
    	printf("请输入元素的个数:");
    	scanf("%d",&num);
    	if(num>999999)
    	{
    		printf("输入超界!\n");
    		return 0;
    	}
    	for(i=0;i<num;i++)
    		list[i].key=rand()%10000;
    	return(num);
    }
    //==========^创建一个数组
    
    void print(struct element a[],int n)
    {
    	int i;
    	for(i=0;i<n;i++)
    		printf("%5d",a[i].key);
    	printf("\n");
    }
    //==========^输出数组
    
    void save(struct element a[],int n,char filename[])
    {
    	int wj=0;
    	FILE *fp;
    	if((fp=fopen(filename,"w"))==NULL)
    		printf("file writer error\n");
    	for(int m=0;m<n;m++)
    	{
    		wj=a[m].key;
    		fprintf(fp,"%d%d",wj);
    	}
    	fclose(fp);
    
    }
    //=========^保存到文件
    
    void insertsort(struct element a[],int n)
    {
    	int i,j;
    	struct element x;
    	for(i=1;i<n;i++)
    		if(a[i].key<a[i-1].key)
    		{
    			x=a[i];
    			a[i]=a[i-1];
    			for(j=i-1;x.key<a[j].key;j--)
    				a[j+1]=a[j];
    			a[j+1]=x;
    		}
    	printf("直接插入排序完成!\n");
    }
    //=========^直接插入排序
    
    void shellsort(struct element a[],int n)
    {
    	int i,j,dk;
    	struct element x;
    	dk=n/2;
    	while(dk>0)
    	{
    		for(i=dk;i<n;i++)
    			if(a[i].key<a[i-1].key)
    			{
    				x=a[i];
    				for(j=i-dk;j>0&&x.key<a[j].key;j-=dk)
    					a[j+dk]=a[j];
    				a[j+dk]=x;
    			}
    		dk=dk/2;
    	}
    	printf("希尔排序完成!\n");
    }
    //=========^希尔排序
    
    void bublesort(struct element a[],int n)
    {
    	int i,j;
    	struct element temp;
    	for(i=0;i<n;i++)
    	{
    		for(j=n-2;j>=i;j--)
    			if(a[j+1].key<a[j].key)
    			{
    				temp=a[j+1];
    				a[j+1]=a[j];
    				a[j]=temp;
    			}
    	}
    	printf("冒泡排序完成!\n");
    }
    //=========^冒泡排序
    
    int partition(struct element a[],int low,int high)
    {
    	int i,j;
    	struct element x;
    	i=low;
    	j=high;
    	x=a[i];
    	while(i<j)
    	{
    		while((i<j)&&(a[j].key>=x.key))
    			j--;
    		if(i<j)
    		{
    			a[i]=a[j];
    			i++;
    		}
    		while((i<j)&&(a[i].key<=x.key))
    			i++;
    		if(i<j)
    		{
    			a[j]=a[i];
    			j--;
    		}
    	}
    	a[i]=x;
    	return i;
    }
    void quicksort(struct element a[],int low,int high)
    {
    	int i;
    	if(low<high)
    	{
    		i=partition(a,low,high);
    		quicksort(a,low,i-1);
    		quicksort(a,i+1,high);
    	}
    }
    //==========^快速排序
    
    void selesort(struct element a[],int n)
    {
    	int i,j,z;
    	struct element temp;
    	for(i=0;i<n;i++)
    	{
    		z=i;
    		for(j=1+i;j<n;j++)
    		{
    			if(a[z].key>a[j].key)
    				z=j;
    		}
    		if(z!=i)
    		{
    			temp=a[i];
    			a[i]=a[z];
    			a[z]=temp;
    		}
    	}
    
    	printf("选择排序完成!\n");
    }
    //=========^简单选择排序
    
    void menu()
    {
    	printf("\n\t\t***********************主菜单***********************\n");
    	printf("\t\t|                 1--生成随机排序元素                |\n");
    	printf("\t\t|                 2--直接插入排序                    |\n");
    	printf("\t\t|                 3--希尔排序                        |\n");
    	printf("\t\t|                 4--冒泡排序                        |\n");
    	printf("\t\t|                 5--快速排序                        |\n");
    	printf("\t\t|                 6--简单选择排序                    |\n");
    	printf("\t\t|                 0--退出                            |\n");
    	printf("\t\t|                                                    |\n");
    	printf("\n                                                        \n");
    }
    //=========^该系统的菜单
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int num,c;
    	bool flag=0;
    	clock_t start,end;
    	char file1[300]="直接插入排序.txt";
    	char file2[300]="希尔排序.txt";
    	char file3[300]="冒泡排序.txt";
    	char file4[300]="快速排序.txt";
    	char file5[300]="选择排序.txt";
    	while(1)
    	{
    		menu();
    		printf("请输入操作选项:");
    		scanf("%d",&c);
    		if(c!=1&&flag==0)
    			printf("处理错误,请先产生随机数...\n");
    		else
    		{
    			switch(c)
    			{
    			case 1:num=creat();
    				print(list,num);
    				printf("\n");
    				flag=1;
    				break;
    			case 2:start=clock();
    				insertsort(list,num);
    				end=clock();
    				printf("直接插入排序后的结果:\n");
    				print(list,num);
    				save(list,num,file1);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 3:start=clock();
    				shellsort(list,num);
    				end=clock();
    				printf("希尔排序后的结果:\n");
    				print(list,num);
    				save(list,num,file2);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 4:start=clock();
    				bublesort(list,num);
    				end=clock();
    				printf("冒泡排序后的结果:\n");
    				print(list,num);
    				save(list,num,file3);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 5:start=clock();
    				quicksort(list,0,num-1);
    				end=clock();
    				printf("快速排序完成!\n");
    				printf("快速排序后的结果:\n");
    				print(list,num);
    				save(list,num,file4);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 6:start=clock();
    				selesort(list,num);
    				end=clock();
    				printf("选择排序后的结果:\n");
    				print(list,num);
    				save(list,num,file5);
    				printf("  The Time:%d ms\n",end-start);
    				printf("\n");
    				break;
    			case 0:exit(1);
    			default:printf("输入错误,请重新输入...\n");
    			}
    		}
    	}
    	system("pause");
    	return 0;
    }
    //=========^该系统主函数
    
    

    四、调试和运行程序过程中产生的问题及采取的措施:
    1、
    2、
    ……
    五、小组会议记录(包括时间、地点、参加人员和内容)
    1、
    2、
    ……
    六、总结及感想

    更多相关内容
  • 为了解决产品的多属性综合排序问题,提出了一种基于层次分析模型的建模方法。通过将决策问题按目标层、准则层和方案层等分解为不同的层次结构,然后求得每一层次各元素对上一层次某元素的优先权重,再用加权和的方法...
  • 综合排序

    千次阅读 2019-04-02 15:44:15
    个性化推荐太遥远,那列表综合排序该怎么做? 朱利安_AI产品经理 0.5 2017.09.05 01:05* 字数 2580 阅读 3796评论 3喜欢 38 这是 公众号:【朱利安笔记】2017年的原创文章,欢迎关注公众号,定期推送AI产品...

    个性化推荐太遥远,那列表综合排序该怎么做?

    96

    朱利安_AI产品经理 Db3aaf4f effd 43dc 9137 d6bf7f70211e

    0.5 2017.09.05 01:05* 字数 2580 阅读 3796评论 3喜欢 38

    这是 公众号:【朱利安笔记】2017年的原创文章,欢迎关注公众号,定期推送AI产品干货 ~

     

    移动互联网的app,老板们都不知道信了哪里的邪魔歪道,总觉的自家的app不做点社区,不做个积分体系,不来个个性化推荐就真不是在做产品了…

    但是数据量没有千万,谈个性化推荐真的是痴心妄想,推荐是需要训练的,没有数据何来推荐??

    有时想想,也怪不得每个老板心里都有一个个性化推荐的梦,毕竟今日头条仅凭算法,feed流中的广告做到个性化推荐,去年的年收入超过60亿,不眼红都不行!!

    列表综合排序

    吐槽完毕,说正事,个性化推荐或许还太遥远,但一个列表通过综合排序将优质的内容推荐给用户,还可以做到的。

    下面来讲讲综合排序。

     

    什么是综合排序?

    举个栗子,我们逛淘宝输入“栗子”,会出来一堆的东西,我们看到的是一个列表页面

    淘宝“栗子”

     

    如果我们点击“按价格排序”,那么我们就选中了一个维度,按照这个维度,将所有的结果进行了降序排序。

    按价格倒序排序

    而综合排序就是综合的多个维度,例如

    · 广告维度(卖家买了广告位,买了直通车,当然放前面了)

    · 活动维度(参加了双11的卖家,排名自然靠前)

    · 宝贝价格

    · 宝贝销量

    · 店铺信誉

    · 上架时间

    · 热度(可能和页面PV,或收藏等有关,这里脑洞举例下,没有考察过)

    等等

    综合排序是如何做到将多个维度综合最终得出排序的呢?

     

    排序的可以简单的分为两种

    1. 多维度分别单一排序

    2. 按总分值进行排序

     

    1.多维度分别单一排序

    即按照A维度降序或升序排序(以下均假设为降序);

    当A维度相同的情况下,再按照B维度降序排序;

    当B维度相同的情况下,再按照C维度降序排序;

    ……

    依次直到最后一个维度,如果还相同,这时候就要看是随机排序,还是按照唯一不重复的值进行排序。

    这样下来,我们就得到的一个排序的结果了。

    这种排序适合维度对结果影响非常明显的情况,或者维度较少的情况。

     

    例如淘宝中按照价格进行降序排序,这时候维度仅仅是价格吗?

    价格相同的拍排序

    肯定不是,当价格相同的时候,如何排序?

    假设取的是上架时间排序,上架时间越晚,排的越前(仅脑洞下);

    当上架时间又一样怎么办?

    再脑洞下,上架时间也相同时,按产品的ID倒序排序,因为产品的ID一定是不同的。

    这样就完成了按价格排序。

     

    上述的多维度分别单一排序仅适合维度较少,或者场景不复杂的情况。

    但维度一多的时候,特别是不同维度之间并没有绝对的我比你重要,你比他重要的关系,用多维度单一排序就非常不合适了。

     

    2.按总分值排序

    为了解决上述的问题,一般都采用按总分值进行排序。

    即将维度赋予一定的权重,然后将不同的维度乘以权重再进行乘积或者累加。

    总分=维度1*权重1 +或* 维度2*权重2 +或* 维度3*权重3 +或*……+或*维度N*权重N

    不太好理解?别急,我们再举一个栗子

     

    我们假设我们现在在使用在行的产品,我们要对在行上的专家进行排序。

    (以下都是仅为了方便说明的脑洞,实际并非这种排序)

     

    在行的综合排序

     

    脑洞维度如下:

    · 最近两周的预约该专家的人数

    · 行家提供的服务历史购买人数

    · 行家提供的服务的价格

    · 服务的收藏人数

     

    我们假设总分是60分

    · 最近两周预约该专家的人数占权重20分

    · 历史购买人数占权重20分

    · 专家提供的服务的价格占权重5分

    · 转发服务的收藏数占权重15分

     

    那么一个行家的某个服务的分数=(最近两周预约该专家的人数)*15+(历史购买人数)*20+(专家提供的服务的价格)*5+(转发服务的收藏数)*15

     

    桥到吗太…

    如果按照上面的公式,直接进行计算的话,会出现问题。例如不同专家的价格不同,我们实际想要的是价格越便宜,那么排名越前。但是如果直接乘以价格,价格设的越高,分值越大,显然有问题。

     

    这是为什么?

    因为没有归一化处理啊,没有对比就没有伤害,为了排序,我们需要对比下。

     

    对维度进行细分,给予不同的系数

    拿两周预约该专家的人数这个维度来说,我们常用的处理的方式可以是

    1)按照阶梯分段进行处理

    例如

    我们将0-300元划分为一个阶段,系数是1.0

    300-500元,系数是0.8;

    500以上,系数是0.6。

    这样,我们对价格就能进行划分

     

    2)按照百分比进行处理

    例如将价格进行正序排序,前15%的系数是1.0

    15%-50%的系数是0.8;

    50%-100%的系数是0.6。

     

    3)按照线性函数转化处理

    公式=(A-min)/(max-min)

    这样处理后,每个价格A都能得到一个百分比的值,价格越便宜,系数就越低,但这和我们的期望不符,需要再对公式根据业务需求进行调整。

     

    4) 按照对数进行处理

    取log(A),也是一种将数值进行归一化处理的方式

     

    5)按照公式进行处理

    上述的线性函数转化和对数的处理,一般并不能直接得出结果,所以需要在基础上对公式进行处理;或者业务需要的曲线是对数函数,幂函数等,这时候就需要取相应的公式将值进行转化。

    这里补充下,如果你是像我一样数学一般的话,那么多列出几组数据,再利用excel画出图表,通过图表自动生成趋势线和公式,这样就能快速的找到自己想要的公式了。

     

    所以,最终公式

    一个行家的某个服务的分数=(最近两周预约人数的系数)*15+(历史购买人数的系数)*20+(专家提供的服务的价格的系数)*5+(转发服务的收藏数的系数)*15

    如果我们换一个角度去思考,我们会发现,我们的所谓系数实际可能看成是另一个小的总分,总分内的不同情况下对应的系数,实际也就是不同的小维度,系数值就是权重

    这样一想的话,系数下面可以再内嵌系数,内嵌的系数再内嵌下一个系数。公式就能按照业务的需要进行非常灵活的处理了。

    例如还是刚刚行家的价格,我们可以取得前15%的行家价格,按照某个公式进行取分得出系数,15%-50%还是直接赋值0.8,50%-100%的再按照另外一个公式计算取得系数值。

     

    综上,按总分值进行排序的,可以简单的理解为

    总分=(维度A权重*归一化的系数值a) + or *  (维度B权重*归一化的系数值b)+ or * …… + or *(维度N权重*归一化的系数值n)

     

    以上就是综合排序的两种方式

    1. 多维度分别单一排序

    2. 按总分值排序

     

    另外,值得一提的是,威尔逊算法(听起来很高大上)是一种常用来对用户投票的内容进行排序的方法,也属于总分值排序;

    知乎目前采用的正是这种算法。

    但初期知乎采用的却是非常简单的赞同比排序,这种排序会导致一个很明显的问题

    例如

    A回答的点赞是50个,反对是2个,赞同比例96%;

    B回答的点赞是2个,反对0个,赞同比例100%;

    如果纯粹按照赞同比例进行排序的话,那么B回答就会在A前面,这显然不是我们希望的结果。

    而威尔逊算法解决了这个问题。

     

    威尔逊算法下的分值

     

    由于目前我自己也没研究透,和这个主题相关且很实用,顺带分享下,点这里查看威尔逊算法

    就先不装逼了,等我研究透了再写个文章细说下,逃了逃了…

     

    展开全文
  • 网页 资讯 视频 图片 知道 文库 贴吧 采购 地图 | 百度首页 登录 VIP新客立减2元 意见反馈 下载客户端 12/25/2019 数据结构课程设计综合排序 - 百度文库 东华理工大学 东华理工大学 首页 分类 精品内容 申请认证 ...
  • 手机站筛选包含:综合排序、销量优先、更多品牌价格区间HTML5特效代码
  • 综合排序算法

    2016-01-10 14:40:37
    冒泡,快速,希尔等排序问题,网络转载,供大家分享
  • 数据结构课程设计综合排序(希尔排序、快速排序、堆排序、归并排序),随机产生的10000个数据,并对数据进行排序。
  • 综合排序-数据结构课程设计.pdf
  • 数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
  • 利用模糊集理论确定辐射源威胁因子的隶属度函数...综合排序的模糊相对比值法。 实例证明该方法是可行而有效的,它不仅适用于辐射源威胁的综合排序问 题,而且适用于军事、 经济以及日常生活中的多属性决策问题。</p>
  • elasticsearch综合排序的小技巧

    千次阅读 2020-12-23 04:12:10
    需求说明事实上在工作中总是会遇到各种异想天开不知所措的需求,就比如当prd文档简单的写下了要求你按相关度+热度综合排序这样的需求。嗯,这看着其实不过分。事实上我更希望您能说明清楚排序规则,各种情况各种场景...

    需求说明

    事实上在工作中总是会遇到各种异想天开不知所措的需求,就比如当prd文档简单的写下了要求你按相关度+热度综合排序这样的需求。嗯,这看着其实不过分。

    事实上我更希望您能说明清楚排序规则,各种情况各种场景下的排序方式,而不是简短的这么一句话。不过大部分情况你永远都只能获得这一句话,那么,还是想想如何从这一句话中推断出需要的信息来进行需求分析吧。

    需求分析

    1.首先是相关度

    那基本上要求搜索词和文本的相关程度上的得分。正常的全文搜索的情况下相似度大部分可以使用TF-IDF或者BM25进行计算,效果上都差不多,当然也可能有更复杂的奇妙的需求逼着你去自定义打分的逻辑,但那都是迭代到一定程度的后话了。关于如何自定义打分可以参考我的一篇博客ElasticSearch插件编写-Similarity插件

    2.其次是热度

    这里就涉及到热度的计算,万幸产品们提供了一个热度计算的公式,有点复杂,大概可以概括为下面这样

    f1(点赞数, 阅读数, 评论数) + f2(当前时间-文档创建时间) + f3(随机数) f1,f2,f3为函数

    首先是f1,这些属于可以实时性要求不强,可以通过离线同步来定时计算f1(点赞数, 阅读数, 评论数)的数值然后写入索引。

    优点: 空间换时间,查询的时候节省了一部分计算的耗时

    缺点: 实时性不强

    其次是f2,这就有一些麻烦了,文档创建时间存储的是时间戳,需要用当前时间的时间戳相减来计算。这样的查询逻辑如何用es提供的语法来表达呢?普通的搜索器应该是无法支持我们的需求的,这个时候就需要引入脚本Script。我们可以编写一段如下的脚本

    "script_score": {

    "script": {

    "script": "f1=doc['f1']; createTime=doc['createTime'];return f1 + f2(nowTime, createtIME) + f3",

    "params": {

    "nowTime": "xxxxxxx"

    }

    }

    优点: 可以完美计算出热度对应得分,解决复杂逻辑的需求

    缺点: 计算量偏大,这个压测的结果可想而知,可能改成java原生插件好一些

    但即使是这样,会发现好像还是和需求不太一样。相关度+热度,并不是简单的相加减,而是要综合排序。综合排序是很模糊的四个字,犹抱琵琶半遮面般的含蓄,我的理解是相关度为主并综合考虑热度的设计。那么怎么办呢?有两个方案

    方案一

    直接相加或相乘或乱七八糟的计算合并相关度和热度的得分

    方案二

    优先排序相关度,相同情况下排序热度

    方案一是个优点缺点都很明显的方案,他可以更明显的表现出热度与相关度的激烈斗争,是两个因素之间互相对抗后形成的结局,但是需要对数字进行一些平滑,因为可能一不小心,两个分数计算出来不在一个量级,那么分数较低的因素将几乎被忽略不计。简单的说,控制好你想要的比例,比如希望相关度得分占60%,热度占40%的话,就要控制住两者的得分基本也维持在这一比例。

    方案二是一个很直白简单的方案

    "sort" : [ {

    "_score" : {

    "order" : "desc"

    }

    }, {

    "hotNums" : {

    "order" : "desc"

    }

    } ]

    就这么简单,直接排序,优点在于可解释,逻辑简单,计算快速,缺点在于其实热度对于排序的影响可能就没那么明显,相关度其实没那么容易一样的。但是还有一个问题,送佛送到西,产品给的公式是一个包括实时时间计算的公式,但是我上面代码是一个离线的死的不动的热度,虽然心里知道热度基本用不上,但是面子工程是要做的,那怎么办呢?

    这里了解后才发现es灵活到sort也可以放脚本…真的是灵活,类似如下处理

    "sort" : [ {

    "_score" : {

    "order" : "desc"

    }

    }, {

    "script": {

    "script": "f1=doc['f1']; createTime=doc['createTime'];return f1 + f2(nowTime, createtIME) + f3",

    "params": {

    "nowTime": "xxxxxxx"

    }

    } ]

    需求反思

    其实prd文档中很难能真的把规则说的清清楚楚,谁也不可能一开始就把整个规则设计清楚,这时就需要一步步去摸索到底要怎么做出来,还是要自己思考

    展开全文
  • 综合排序总结

    千次阅读 2019-06-20 13:53:55
    如果给你一个数组,长度很长,综合排序会先进行一个判断,判断数组里面放的数据类型是什么样的,是基础类型(int,double,char,float,short)还是你自定义的类型(student)。 如果装的是基础类型的数据,则会用快排(不...

    在这里插入图片描述
    最好情况下(基本有序),高效的算法是:
    直接插入排序、冒泡排序。

    无序情况下,高效的算法是:
    堆排序、快速排序、归并排序

    初始序列无关的排序算法:简单选择

    如果给你一个数组,长度很长,综合排序会先进行一个判断,判断数组里面放的数据类型是什么样的,是基础类型(int,double,char,float,short)还是你自定义的类型(student)。
    如果装的是基础类型的数据,则会用快排(不稳定);
    原因是:基础类型根本不用区分原始顺序,相同值无差异。

    如果数据的类型是你自己定义的(student)类型,则会用归并排序(稳定)。
    原因是:对一个班级,先按照整个分数排序,再按照班级排序,此时相同班级的个体可能是不一样的,是有差别的。

    如果你的数组长度很短,不管存放的是什么类型的数据,综合排序根本不会选择快排或者归并排序,它会直接用插入排序
    原因是:插入排序的常数项极低,在样本模数小于60的情况下直接用插入排序,为啥?因为,虽然插入排序是O(N2)的排序,但是当样本量在极小的情况下,O(N2)的劣势表现不出来,反而插入排序的常数项很低,导致在小样本的情况下插入排序会飞快!

    展开全文
  • 综合排序问题

    2014-07-02 20:46:19
    综合排序 【问题描述】: 利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序。 【基本要求】: 分别采用插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序以及归并排序。 统计每一种...
  • 针对系统特点确定了最小割集的数量和属性,利用权的最小平方法建立了加权规范化故障定位搜索决策矩阵,利用相对贴近度法对最小割集进行综合排序求出了搜索序列。针对充液阀故障引起压装机主缸不能工进这一工程问题,...
  • 无论从创造利润还是增强竞争力的角度, 企业对绿色战略供应商的... 以ARR电脑公司的绿色战略供应商的优选为案例, 针对所构建的指标体系, 运用多指标综合排序模型,对供应商进行综合排序, 得出其优先次序, 提高了优选效率.
  • 论文研究-可能度及区间数综合排序.pdf, 首先对可能度进行综述, 证明其中四种可能度计算方法相互等价. 给出了可能度公理, 证明了文献中经常出现的两种区间数综合排序方法...
  • 这是一个利用数据结构中的多种排序算法进行,包括冒泡排序,直接插入排序,希尔排序等的一项课程设计,通过使用多种排序,对大量的数据进行排序,并且以更为精确的最小时间进行分析,得出最佳时间排序算法
  • 论文研究-基于FQFD的固体火箭发动机技术特性综合排序方法.pdf, 针对固体火箭发动机指标体系复杂、评价困难,传统quality function deployment(QFD)方法处理不确定性和...
  • 资源仅供参考!不用做其他用途 内含:完整实验报告代码,和注释,包含所有排序代码
  • 综合排序-数据结构课程设计[1].pdf
  • 商品综合排序方法

    万次阅读 2018-09-13 11:07:31
    在浏览一些电商网站时,我们会发现电商网站列表基本上都是销量、价格、评价数、上架时间排序的,同时还会有综合排序,前面几种排序很简单,最后的综合排序一般是怎样排列的呢? 商品综合排序跟10项因素相关(会...
  • 一个综合排序公式,自己感觉很有用通达信指标公式源码.doc
  • 并利用灰色理论分析了影响因素(如介质比重Sm,温度t,pH值,材料硬度HRC,泵流量Q,扬程H,转速n和叶轮直径D2等),对烟气脱硫泵寿命L的综合影响,通过大量计算得到了这些因素的综合影响排序
  • 论文研究- 综合排序的双基点法的改进及灵敏度分析.pdf, 多指标(准则、属性)综合排序的方法基本上有:1.化多指标为单一指标的简单加权法;2.根据相对贴近度排序的双基点法(TOPSIS法);3.采用加权欧氏距离的LINMAP法;4....
  • 1) 至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能(以上机...
  • 做CMS系统时,经常会有一个需求,将文章按时间、以及管理员给定的权重值进行排序显示的需求。之前自己有写过一个排序的公式,已经用了一段时间了,感觉还不错,这里跟大家分享一下。 特点 该排序公式的特点 权重值...
  • 20210528-中信证券-ESG研究专题系列:行业视角详解碳中和,综合排序精选碳免疫企业.pdf
  • 传媒行业2019年年报总结:细分板块综合排序——游戏>出版>影视>广电>营销>教育.pdf
  • 段就像淘宝里面的综合排序,在显示页面的时候回按照这个排序字段进行排序,都是什么算法 如何设计,没有接触过,望指教![图片说明](https://img-ask.csdn.net/upload/201708/24/1503557865_820239.png)
  • jian dan pai xu\n"); mao pao pai xu\n"); kuai su pai xu\n"); gui bing pai xu\n"); dui pai xu\n"); exit\n");

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 130,646
精华内容 52,258
关键字:

综合排序

友情链接: adb.zip