排序(完整可运行代码)

排序算法所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序算法，就是如何使得记录按照要求排列的方法。

排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。

一个优秀的算法可以节省大量的资源。

在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

分类排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个关键字有序的序列。

稳定度(稳定性)一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。

然而，假设以下的数对将要以他们的第一个数字来排序。

(4,1)(3,1)(3,7)(5,6)在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有:(3,1)(3,7)(4,1)(5,6) (维持次序)(3,7)(3,1)(4,1)(5,6) (次序被改变)不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。

不稳定排序算法可以被特别地实现为稳定。

作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。

然而，要记住这种次序通常牵涉到额外的空间负担。

在计算机科学所使用的排序算法通常被分类为:(a)计算的复杂度(最差、平均、和最好性能)，依据列表(list)的大小(n)。

一般而言，好的性能是O(nlogn)，且坏的性能是O(n^2)。

对于一个排序理想的性能是O(n)。

而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlogn)。

(b)存储器使用量(空间复杂度)(以及其他电脑资源的使用)(c)稳定度:稳定的排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。

有一个小型超市，出售N（N>＝10）种商品，设计并实现一个系统，完成下列功能：1．保存及输出。

超市中的各种商品信息保存在指定文件中，可以把它们输出显示。

2．计算并排序。

计算每类商品的总价值（sum，单精度）及平均价（aver，单精度，输出一位小数），将每类商品按平均价从大到小的顺序排序打印出来。

3．统计。

统计输出库存量低于100的货号及类别。

统计输出有两种以上（含两种）商品库存量低于100的商品类别。

1.2总体结构本程序主要分为八个模块：主模块、信息输出修改模块、新建信息模块、排序模块、计算模块、统计模块1、统计模块2、打印模块。

1）主模块：通过调用各分模块实现功能；2）信息输出修改模块：输出显示文件中商品信息内容，添加商品信息，删除商品信息，修改商品信息；3）新建商品信息模块：建立一个新结构体，为链表存信息用，并且将信息保存在指定的文件中；4）排序模块：把文件中顺序零乱的商品信息按单价的大小从高到低进行排序，放到链表里存储；5）计算模块：将所有商品的价格与库存量进行累加求和；6）打印模块：将商品信息按每类平均价格排序（从高到低）按顺序打印出来；7）统计模块1：统计库存量低于100的货名及类别；8）统计模块2：统计商品库存量有2种以上（含2种）低于100的商品类别。

附录（程序清单）#include "stdio.h" /*输入，输出头文件*/#include "stdlib.h" /*申请空间头文件*/#include "string.h" /*对字符串加工头文件*/#include "conio.h" /*清屏头文件*/FILE *fp;int n=0; /*定义文件指针类型*/int i,j,a[4],m; /*定义整数类型*/float aver[4],sum[4],g[4],h; /*定义浮点类型*/char c[5]="elec"; /*定义字符数组类型*/char d[5]="comm"; /*定义字符数组类型*/char e[5]="food"; /*定义字符数组类型*/char f[5]="offi"; /*定义字符数组类型*/struct good /*定义结构体*/{int num; /*商品编号*/char name[20]; /*商品名称*/char kind[40]; /*商品类型*/float price; /*商品价格*/char unit[10]; /*商品单位*/int quantity; /*商品数量*/struct good *next; /*定义结构体指针类型*/}*head,*p1,*p2;struct good *createlist() /*创建链表函数*/ {struct good *head1,*p1,*p2; /*定义结构体指针类型*/if((fp=fopen("goods message.txt","w"))==NULL) /*判断能否打开文件*/ {printf("can not open the file");exit(0); /*结束程序*/}head1=(struct good *)malloc(sizeof(struct good)); /*申请头结点空间*/ p1=head1;p2=head1;printf("*********************************************\n");printf("请输入信息:编号，名称，类型，价格，单位，数目\n");printf(" （以输入“－1”表示结束输入）\n");printf("*********************************************\n");printf("____________________\n");scanf("%d %s %s %f %s %d",&p1->num,p1->name,p1->kind,&p1->price,p1-> unit,&p1->quantity); /*输入商品信息*/printf("____________________\n");p1->next=NULL;fprintf(fp,"%d %s %s %f %s %d",p1->num,p1->name,p1->kind,p1->price,p1->unit,p1->quantity);/*将商品信息写入文件*/while(1){p1=(struct good *)malloc(sizeof(struct good)); /*申请新空间*/ printf("*********************************************\n");printf("请输入信息:编号，名称，类型，价格，单位，数目\n");printf(" （以输入“－1”表示结束输入）\n");printf("*********************************************\n");printf("____________________\n");scanf("%d",&p1->num);if(p1->num==-1) /*申请空间结束条件*/{printf("____________________\n\n");fprintf(fp,"%d",-1);fclose(fp);return head1; /*返回头指针*/}scanf("%s %s %f %s %d",p1->name,p1->kind,&p1->price,p1->unit,&p1->quan tity); /*输入商品信息*/printf("________________\n");fprintf(fp,"%d %s %s %f %s %d",p1->num,p1->name,p1->kind,p1->price,p1->unit,p1->quantity);/*将商品信息写入文件*/p1->next=NULL;p2->next=p1;p2=p1;}}struct good *paixu(struct good*head2) /*链表排序函数*/{struct good *p6,*p7,*r,*s; /*定义结构体指针类型*/for(i=0;i<=3;i++) /*赋初值值*/{a[i]=0;sum[i]=0;aver[i]=0;}p6=(struct good *)malloc(sizeof(struct good)); /*申请新空间*/ p6->next=head2;head2=p6;while(p6->next!=NULL) /*判断循环结束条件*/{p7=p6->next;r=p6;while(p7->next!=NULL) /*判断循环结束条件*/{if((p7->next->price)>(r->next->price)) /*判断是否调换*/r=p7;p7=p7->next;}if(p6!=r) /*判断循环结束条件*/{s=r->next; /*指针调换*/r->next=s->next;s->next=p6->next;p6->next=s;}p6=p6->next;}p6=head2;head2=head2->next;free(p6); /*释放第一个无效空间*/return head2;}void jisuan(){p1=head;do{if(strcmp(p1->kind,c)==0) /*判断是否为电器类型*/{sum[0]=sum[0]+(p1->price)*(p1->quantity); /*求电器总价*/a[0]=a[0]+p1->quantity; /*求电器总件数*/}if(strcmp(p1->kind,d)==0) /*判断是否为日用品类型*/{sum[1]=sum[1]+(p1->price)*(p1->quantity); /*求日用品总价*/ a[1]=a[1]+p1->quantity; /*求日用品总件数*/}if(strcmp(p1->kind,e)==0) /*判断是否为办公用品类型*/{sum[2]=sum[2]+(p1->price)*(p1->quantity); /*求办公用品总价*/ a[2]=a[2]+p1->quantity; /*求办公用品总件数*/}if(strcmp(p1->kind,f)==0) /*判断是否为食品类型*/{sum[3]=sum[3]+(p1->price)*(p1->quantity); /*求食品总价*/a[3]=a[3]+p1->quantity; /*求食品总件数*/}p1=p1->next;}while (p1!=NULL); /*遍历链表结束条件*/for(i=0;i<4;i++)aver[i]=sum[i]/a[i]; /*求每类商品平均价*/printf("****************************************************\n");printf("商品类型\t 平均价\t 总库存量\n");printf("****************************************************\n");printf("____________________________________________________\n");printf("电器总价值:%0.1f\t平均价:%0.1f\t总库存量:%d\n",sum[0],aver[0],a[0]); printf("____________________________________________________\n");printf("日用品总价值:%0.1f\t平均价:%0.1f\t总库存量:%d\n",sum[1],aver[1],a[1]);printf("____________________________________________________\n"); printf("食品总价值:%0.1f\t平均价:%0.1f\t总库存量:%d\n",sum[2],aver[2],a[2]); printf("____________________________________________________\n");printf("办公用品总价值:%0.1f\t平均价:%0.1f\t总库存量:%d\n",sum[3],aver[3],a[3]);printf("____________________________________________________\n"); }void shuchu() /*输出商品信息函数*/{do{struct good *p3,*p4,*p5; /*定义结构体指针类型*/int n=0,p=0,q=0,r=0;printf("所有商品信息：\n");printf("编号，名称，类型，价格，单位，数目\n");printf("**********************************\n");if((fp=fopen("goods message.txt","rb+"))==NULL) /*判断能否打开文件*/{printf("can not open the file");exit(0); /*结束程序*/}head=(struct good *)malloc(sizeof(struct good)); /*申请头结点空间*/p3=head;fscanf(fp,"%d %s %s %f %s %d",&p3->num,p3->name,p3->kind,&p3->price,p3->unit,&p3->quantity);/*从文件中写到链表*/while(1){p4=(struct good *)malloc(sizeof(struct good)); /*申请头结点空间*/fscanf(fp,"%d ",&p4->num);if(p4->num!=-1) /*判断循环结束条件*/{fscanf(fp,"%s %s %f %s %d",p4->name,p4->kind,&p4->price,p4->unit,&p4->quantity); /*从文件中写到链表*/p4->next=NULL;p3->next=p4;p3=p4;}else{p3->next=NULL;break;}}fclose(fp); /*关闭文件*/p3=head;while(p3!=NULL){printf(" %d %s %s %0.1f %s %d\n\n",p3->num,p3->name,p3->kind,p3->price,p3->unit,p3->quantity);printf("__________________________________\n");p3=p3->next;}printf("**********************************\n");printf("//////////////////////////////////\n");while(n!=4){p3=head;printf("**********************************\n");printf("1 添加商品信息\n");printf("2 删除某商品信息\n");printf("3 修改某商品信息\n");printf("4 返回（当你完成了对某一商品的添加、删除或者修改后请按4返回）\n");printf("**********************************\n");scanf("%d",&n);if(n==1) /*添加商品信息*/{printf("请输入商品编号名称类型价格单位数目\n");printf("**********************************\n");p4=(struct good *)malloc(sizeof(struct good)); /*申请空间*/scanf("%d %s %s %f %s %d",&p4->num,p4->name,p4->kind,&p4->price,p4-> unit,&p4->quantity); /*输入商品信息*/p4->next=NULL;while(p3->next!=NULL) /*判断循环结束条件*/{p3=p3->next;}p3->next=p4;p3=head;if((fp=fopen("goods message.txt","w"))==NULL) /*判断能否打开文件*/{printf("can not open the file");exit(0); /*结束程序*/}while(p3!=NULL){fprintf(fp,"%d %s %s %f %s %d",p3->num,p3->name,p3->kind,p3->price,p3->unit,p3->quantity)/*将商品信息写入文件*/p3=p3->next;}fprintf(fp,"%d",-1);fclose(fp); /*关闭文件*/printf("**********************************\n");printf("__________________________________\n");printf("------------请按4返回-------------\n");printf("__________________________________\n");printf("**********************************\n");}if(n==2) /*删除商品*/{printf("**********************************\n");printf("请输入需要删除的商品编号\n");printf("**********************************\n");scanf("%d",&p);printf("**********\n");printf("1 确认删除\n2 取消删除\n");printf("**********\n");scanf("%d",&r);if(r==1){if((head->num)==p){head=head->next;free(p3); /*释放空间*/}else{p4=head;p3=p4->next;while(p3!=NULL) /*判断循环结束条件*/{if((p3->num)==p){p5=p3->next;free(p3); /*释放空间*/p4->next=p5;break;}p3=p3->next;p4=p4->next;}}if((fp=fopen("goods message.txt","w"))==NULL) /*判断能否打开文件*/{printf("can not open the file");exit(0); /*结束程序*/}p3=head;while(p3!=NULL) /*判断循环结束条件*/{fprintf(fp,"%d %s %s %f %s %d",p3->num,p3->name,p3->kind,p3->price,p3->unit,p3->quantity); /*将商品信息写入文件*/p3=p3->next;}fprintf(fp,"%d",-1);fclose(fp); /*关闭文件*/}if(r==2)continue; /*继续循环*/printf("**********************************\n");printf("__________________________________\n");printf("------------请按4返回-------------\n");printf("__________________________________\n");printf("**********************************\n");}if(n==3) /*修改某商品信息*/{printf("请输入需要修改的商品编号\n");scanf("%d",&q);while(p3!=NULL) /*判断循环结束条件*/{if((p3->num)==q) /*判断是否为所需要修改的商品*/{printf("请输入商品单价与库存量（如果单价不变请输入原来的单价）\n");scanf("%f %d",&p3->price,&p3->quantity); /*输入商品价格与库存量*/}p3=p3->next;}if((fp=fopen("goods message.txt","w"))==NULL) /*判断能否打开文件*/{printf("can not open the file");exit(0); /*结束程序*/}p3=head;while(p3!=NULL) /*判断循环结束条件*/{fprintf(fp,"%d %s %s %f %s %d",p3->num,p3->name,p3->kind,p3->price,p3->unit,p3->quantity);/*将商品信息写入文件*/p3=p3->next;}fprintf(fp,"%d",-1);fclose(fp); /*关闭文件*/printf("**********************************\n");printf("__________________________________\n");printf("------------请按4返回-------------\n");printf("__________________________________\n");printf("**********************************\n");}if(n==4) /*退出*/break;}printf("**********\n");printf("1 继续修改\n---------\n2 返回\n");printf("**********\n");scanf("%d",&p);if(p==1)continue; /*继续循环*/if(p==2)break; /*跳出循环*/}while(n!=2);fclose(fp); /*关闭文件*/}void printf0(struct good *p) /*遍历链表并打印电器类商品函数*/{struct good *p3; /*定义结构体指针类型*/p3=p;while (p3!=NULL) /*判断遍历链表循环结束条件*/{if(strcmp(p3->kind,c)==0) /*判断商品类型是否为电器类型*/{printf("%d\t%s\t%s\t%0.1f\t%s\t%d\n",p3->num,p3->name,p3->kind,p3->price, p3->unit,p3->quantity); /*输出电器类商品信息*/ printf("________________________________________________\n");}p3=p3->next;}return;void printf1(struct good *p) /*遍历链表并打印日用品类商品函数*/{struct good *p3; /*定义结构体指针类型*/p3=p;while (p3!=NULL) /*判断遍历链表循环结束条件*/{if(strcmp(p3->kind,d)==0) /*判断商品类型是否为日用品类型*/{printf("%d\t%s\t%s\t%0.1f\t%s\t%d\n",p3->num,p3->name,p3->kind,p3->price, p3->unit,p3->quantity); /*输出日用品类商品信息*/ printf("________________________________________________\n");}p3=p3->next;}return;}void printf2(struct good *p) /*遍历链表并打印办公用品类商品函数*/{struct good *p3; /*定义结构体指针类型*/p3=p;while (p3!=NULL) /*判断遍历链表循环结束条件*/{if(strcmp(p3->kind,e)==0) /*判断商品类型是否为办公用品类型*/{printf("%d\t%s\t%s\t%0.1f\t%s\t%d\n",p3->num,p3->name,p3->kind,p3->price, p3->unit,p3->quantity); /*输出办公用品类商品信息*/ printf("________________________________________________\n");}p3=p3->next;}return;}void printf3(struct good *p) /*遍历链表并打印食品类商品函数*/{struct good *p3; /*定义结构体指针类型*/p3=p;while (p3!=NULL) /*判断遍历链表循环结束条件*/{if(strcmp(p3->kind,f)==0) /*判断商品类型是否为食品类型*/{printf("%d\t%s\t%s\t%0.1f\t%s\t%d\n",p3->num,p3->name,p3->kind,p3->price, p3->unit,p3->quantity); /*输出食品类商品信息*/ printf("________________________________________________\n");}p3=p3->next;}return;}void shunxudayin(){for(i=0;i<4;i++)g[i]=aver[i]; /*将平均价赋给新数组*/for(j=0;j<3;j++) /*将新数组用冒泡排序法排序*/for(i=j+1;i<4;i++){if(g[j]<g[i]){h=g[j];g[j]=g[i];g[i]=h;}}printf("\n****************************\n");printf("商品平均价格排序表（从高到低）\n");printf("****************************\n");printf("________________________________________________\n"); printf("编号\t名称\t类别\t单价\t单位\t数量\n");printf("________________________________________________\n"); for(j=0;j<4;j++)for(i=0;i<4;i++){if (aver[i]==g[j]) /*判断每类商品平均价格的先后顺序*/switch(i){case 0:printf0(head); /*调用遍历链表并打印电器类商品函数*/break;case 1:printf1(head); /*调用遍历链表并打印日用品类商品函数*/break;case 2:printf2(head);/*调用遍历链表并打印办公用品类商品函数*/break;case 3:printf3(head); /*调用遍历链表并打印食品类商品函数*/break;}}}void tongji1(){p1=head;printf("\n************************\n");printf("库存量低于100的货名及类别\n");printf("************************\n");printf("________________________\n");printf("商品名称\t商品类型\n");printf("________________________\n");while(p1!=NULL) /*判断遍历链表循环结束条件*/{if(p1->quantity<100) /*判断库存量是否小于100*/{printf("%s\t%s\n",p1->name,p1->kind); /*输出商品名称及类别*/ printf("________________________\n");}p1=p1->next;}}void tongji2(){printf("\n**********************************************\n");printf("商品库存量有2种以上（含2种）低于100的商品类别:\n");printf("**********************************************\n");printf("________\n");if((a[0]<100)&&(a[0]>=2)) /*判断电器类库存量是否为2种以上（含2种）低于100*/{printf("电器\n");printf("________\n");}if((a[1]<100)&&(a[1]>=2)) /*判断日用品类库存量是否为2种以上（含2种）低于100*/{printf("日用品\n");printf("________\n");}if((a[2]<100)&&(a[2]>=2)) /*判断食品类库存量是否为2种以上（含2种）低于100*/{printf("食品\n");printf("________\n");}if((a[3]<100)&&(a[3]>=2)) /*判断办公用品类库存量是否为2种以上（含2种）低于100*/{printf("办公用品\n");printf("________\n");}}int main(int argc, char* argv[]){struct good *p1,*p2; /*定义结构体指针类型*/while(1){printf("***********************************************\n");printf("1 ----------输出查看或者修改已存信息-----------\n");printf("-----------------------------------------------\n");printf("2 -----重新输入新信息（并且删除原有信息）------\n"); printf("-----------------------------------------------\n");printf("3 统计商品信息（如果您还没有查看过信息请先按1）\n"); printf("-----------------------------------------------\n");printf("4 -------------------退出---------------------\n");printf("***********************************************\n");scanf("%d",&m);if(m==1)shuchu(); /*调用输出信息函数*/if(m==2){system("cls");head=createlist(); /*调用建立链表函数*/}if(m==3){printf("统计结果如下\n");head=paixu(head); /*调用链表排序函数*/ jisuan(); /*调用计算函数*/shunxudayin(); /*调用顺序打印函数*/tongji1(); /*调用统计1函数*/tongji2(); /*调用统计2函数*/}if(m==4){p1=head;while(p1!=NULL) /*判断遍历链表结束条件*/ {p2=p1->next;free(p1); /*释放空间*/p1=p2;}break;}}return 0; /*结束程序*/}。

排序一直是数据结构中的常用算法，STL提供的排序算法非常丰富，如何有效使用就值得探讨。

在网上没有找到条款31的翻译，于是我自己翻译了。

－－Winter如何进行排序？让我数数有几种方法。

一旦程序员需对容器元素进行排序，sort算法马上就会出现在他的脑海(可能有些程序员会想到qsort，但详细阅读条款46后，他们会放弃使用qsort的想法，转而使用sort算法)。

sort是一个非常优秀的算法，但并当你并不真正需要它的时候，其实就是一种浪费。

有时你并不需要一个完整的排序（简称为全排序）。

例如，你现有一个包含Widget对象（Widget意为“小挂件”）的vector 容器，并且你想把其中质量最好的20个Widget送给你最好的客户，那么你需做的只是找出这20个质量最好的Widget元素，剩下的并不需关心它们的顺序。

这时你需要的是部分排序（相对于全排序），恰好在算法中就有一个名副其实的部分排序函数函数：partial_sort：bool qualityCompare(const Widget& lhs, const Widget& rhs){// lhs的质量不比rhs的质量差时返回true，否则返回false}…partial_sort (widgets.begin(), // 把质量最好的20元素widgets.begin() + 20, // 顺序放入widgets容器中widgets.end(),qualityCompare);… // 使用widgets...通过调用partial_sort，容器中开始的20个元素就是你需要的质量最好的20个Widget，并按顺序排列，质量排第一的就是widgets[0], 紧接着就是widgets[1]，依次类推。

这样你就可以把质量第一的Widget送给你最好的顾客，质量第二的Widget就可以送给下一个顾客，很方便吧，更方便的还在后面呢。

如果你只是想把这20个质量最好的Widget礼物送给你最好的20位顾客，而不需要给他们一一对应，partial_sort在这里就有些显得大材小用了。

简单且实用的冒泡排序算法的控制台应用程序。

运行界面如下：using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace冒泡排序{class Program{///<summary>///交换两个整型变量的值///</summary>///<param name="a">要交换的第一个整形变量</param>///<param name="b">要交换的第一个整形变量</param>private static void Reverse(ref int a, ref int b){int temp = a;a = b;b = temp;}static void Main(string[] args){while (true){string[] strInput;//用来接收用户输入的字符串int[] intInput;string[] separator = { ",", " " };//设置分隔符Console.WriteLine("请输入数据，以\",\"或空格分隔，或按\"q\"退出。

");string str = Console.ReadLine();//接收键盘输入if (str == "q"){return;}strInput = str.Split(separator,StringSplitOptions.RemoveEmptyEntries);//将用户输入的字符串分割为字符串数组intInput = new Int32[strInput.Length];//将字符串数组的每一个元素转换为整型变量//转换时如果出现格式错误或溢出错误则提示try{for (int i = 0; i < strInput.Length; i++){intInput[i] = Convert.ToInt32(strInput[i]);}}catch (FormatException err){Console.WriteLine(err.Message);}catch(OverflowException err){Console.WriteLine(err.Message);}//排序算法主体for (int i = 0; i < intInput.Length - 1; i++)//这里的Length要减1否则会超界{for (int j = 0; j < intInput.Length - i - 1; j++)//这里的Length要减i以减少重复运算{//如果元素j比它之后的一个元素大,则交换他们的位置//如此循环直到遍历完整个数组if (intInput[j] > intInput[j + 1]){Reverse(ref intInput[j], ref intInput[j + 1]);}}}string strOutput = "";//用于输出的字符串foreach (int temp in intInput){strOutput += Convert.ToString(temp) + ",";}Console.WriteLine("排序后的数据为：\r\n{0}\r\n", strOutput);}}}}。