《数据结构》课件-项目九 排序

用排序实现商品排名项目概述排序无处不在，工作生活中我们经常会遇到排序的问题。购买商品时要货比三家，就要对各个商家的产品质量和价格进行列表排序。期末考试后为了了解同学们各自的水平，老师通常会按照学生成绩排序。为体现各国竞技运动实力，对获奖奖牌进行排名。不同排名方式，体现了不同的利益诉求和价值倾向，如在奖牌排行榜中，以金牌数量为基准的排名，是一种“永远争第一”的心态，体现了一种不断超越自我、超越对手的决心，以及对世界巅峰和人类运动极限的不懈追求。而以奖牌数为基准的排名，则相对客观地反映了一个国家对其竞技能力的成长性和延续性的关注。生活的艺术在某种程度上，就是排序的艺术。把所有的事情，捋一捋，标上个一、二、三、四，实在顾及不到的，只有在第一时间说“不”，这既是对自己的尊重，也是对他人的尊重。项目目标序号学习目标知识要点1理解排序的基本概念和分类排序的基本概念、排序的分类2理解各类排序的基本思想并能用Java语言实现排序的算法插入排序：直接插入排序、希尔排序选择排序：直接选择排序、堆排序交换排序：冒泡排序、快速排序归并排序基数排序3能根据问题的特点选择合适的排序算法用排序实现商品排序项目情境-编程实现商品列表排序

1．情境描述

随着电商网站迅速发展，人们购物习惯和方式相较过去已经发生了巨大的改变。相比线下实体店，电商网站有着明显的空间和人工成本优势，真正实现二十四小时不关店。并且，网络商城的商品更加丰富，实体店找不到的商品，网上几乎都能找到，在加上便捷的物流体系，就能够快速送达消费者手中，具有极大便利性。而在电商平台中无论有多少类型的数据，用户总是在通过简单的操作后找到同类型的信息，这些都离不开电商网站里的各种排序功能。电商网络基本提供了按销量排序、按评论数排序、按新品排序、按价格排序等，某某拟购买一20元至100元的鼠标，他通过电商网站搜索这个价位综合排名的鼠标商品信息2．基本要求

编写程序实现对商品列表排序：1.按商品价格升序排序；2.按商品的品牌的英文升序排序，当商品的名牌相同时，按评论数降序排序，当评论数相同时，按价格升序排序。任务一

分析商品排序中数据的逻辑结构学习目标理解排序的基本概念理解排序的分类12

为完成商品列表排序编程任务，首先对问题抽象，建立问题的抽象数据类型。一是确定数据对象的逻辑结构，找出构成数据对象的数据元素之间的关系。二是确定为求解问题需要对数据对象进行的操作或运算，本任务主要是对数据对象进行排序运算。最后将数据的逻辑结构及其在该结构上的运算进行封装得到抽象数据类型。任务描述步骤一：分析数据的逻辑结构任务实施商品列表的逻辑结构在商品列表排序问题中，表中商品列表信息构成了问题要处理的数据对象该数据对象由若干条商品信息组成，每一商品信息为一个数据元素，每个数据元素由品牌、型号、评论数和价格4个数据项组成。信息表中第一个商品信息可视为开始结点，它的前面无数据元素；最后一道商品视为终止节点，它的后面无数据元素；其他的商品则各有一个也只有一个前趋和和一个后继。因此商品列表的数据结构为线性表。步骤二：分析数据的排序运算任务实施排序的定义排序排序是将一组“无序”的数据元素序列调整为“有序”的数据元素序列，使之按关键字递增(或递减)次序排列起来将无序的数据：{2,46,31,13,6,22,10,36,28,18,45}{2,6,10,13,18,22,28,31,36,45,46}调整为了有序的数据：假设含n个数据元素序列的原有关系式为：{R1,R2,…，Rn}其相应的关键字序列为：

{K1,K2,…，Kn}这些关键字相互之间可以进行比较，存在这样一个关系：{Kp1≤Kp2≤…≤Kpn}将原有关系式的数据元素序列重新排列为：{Rp1,Rp2,…,Rpn}，这个操作过程称为排序。排序的定义按价格排序前电商网站鼠标商品列表被排序的对象由一组数据元素组成。数据元素则由若干个数据项组成。如电商网站鼠标商品列表中，每个数据元素由序号、品牌、型号、评论数、价格5个数据项组成，其中有一项用来标识一个数据元素，称为主关键字项。用于排序的价格数据项称为次要关键字。该序列的起始值为：{30,69,59,27,34,49,53,99,89,28},对它们排序后为{27,28,30,34,49,53,59,69,89,99},因此商品关系列表也发生了变化。按价格排序后电商网站鼠标商品列表排序的分类排序的分类外部排序内部排序插入排序选择排序交换排序归并排序基数排序按是否涉及数据的内、外存交换分按策略分内部排序：在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序（简称内排序）外部排序：若排序过程中要进行数据的内、外存交换，则称之为外部排序插入排序是每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子列表中的适当位置，直到全部记录插入完成为止。内部排序-插入排序初始时：2自成1个有序区，无序区为46，31，13，6，22，10，36，28，18，45第1趟：46插入到有序区第2趟：31插入到有序区第3趟：13插入到有序区第4趟：6插入到有序区第5趟：22插入到有序区第6趟：10插入到有序区第7趟：36插入到有序区第8趟：28插入到有序区第9趟：18插入到有序区第10趟：45插入到有序区选择排序每一趟从待排序的记录中选出关键字最小或最大的记录，顺序放在已排好序的子列表的最后，直到全部记录排序完毕。内部排序-选择排序第1趟：选取元素2放在有序区第2趟：选取元素6放在有序区第3趟：选取元素10放在有序区第4趟：选取元素13放在有序区第5趟：选取元素18放在有序区第6趟：选取元素22放在有序区第7趟：选取元素28放在有序区第8趟：选取元素31放在有序区第9趟：选取元素36放在有序区第10趟：选取元素45放在有序区，元素46放在有序区末尾。交换排序两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。内部排序-交换排序

第1趟交换后，46排在第11位

第2趟交换后，45排在第10位

第3趟交换后，36排在第9位

第4趟交换后，31排在第8位

第5趟交换后，28排在第7位

第6趟交换后，22排在第6位

第7趟交换后，18排在第5位

第8趟交换后，13排在第4位

第9趟交换后，10排在第3位

第10趟交换后，6排在第2位，2排在第1位归并排序将两个或两个以上的有序子序列“归并”为一个有序序列。内部排序-归并排序

把数据分成含有3个元素组成的4子序列首先子序列中3个元素排序，然后第1和2子序列合并排序，第3和第4子序列合并排序最后第1和2子序列合并后的子序列与第3和第4子序列合并后的子序列再进行合并排序，得到最终的排序序列基数排序无须比较关键字，通过“分配”和“收集”过程来实现排序。内部排序-分配排序初始序列：70，30，40，10，80，20，90，100，75，60，45第一次排序：按个位数字提取个位数字：7，0，0，0，0，0，0，0，5，0，5按照个位数字进行桶排序个位为0的桶：[30,20,90,100,60]个位为5的桶：[75,45]个位为7的桶：[70]合并桶得到中间结果：[30,20,90,100,60,75,45,70,40,10,80]（注意：这里为简化说明，实际实现中可能还需进一步按稳定性要求排序）第二次排序：按十位数字提取十位数字：3，2，9，1，6，7，4，7，4，1，8按照十位数字进行桶排序：十位为1的桶：[10,100]十位为2的桶：[20]十位为3的桶：[30]十位为4的桶：[40,45]十位为6的桶：[60]十位为7的桶：[70,75]十位为8的桶：[80]十位为9的桶：[90]合并桶得到最终结果：[10,100,20,30,40,45,60,70,75,80,90]第三次排序：按百位数字百位为0的桶：[10,20,30,40,45,60,70,75,80,90]十位为1的桶：[100]合并桶得到最终结果：[10,20,30,40,45,60,70,75,80,90,100]这就是基数排序对给定序列的处理过程。步骤三：定义抽象数据类型任务实施定义抽象数据类型ADTProductRanking数据对象：D={ai|0≤i≤n-1,n≥0,ai为商品}数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=0,...,n-2}基本操作：public

voidinsertSort();//用插入排序实现商品按价格排序public

voidshellSort();//用希尔排序实现商品按价格排序public

voidselectSort();//用直接选择排序实现商品按价格排序public

voidheapSort();//用堆排序实现商品按价格排序public

voidbubbleSort();//用冒泡排序实现商品按价格排序public

voidquickSort();//用快速排序实现商品按价格排序public

voidmergeSort();//用归并排序实现商品按价格排序public

voidradixSort();//用基数排序实现商品按价格排序public

voidbrandSort();//用基数排序实现商品按品牌排序步骤四：创建一个商品列表排序类任务实施创建一个商品列表排序类定义了一个名为Product的类，用于表示一个具有品牌、型号、评论数和价格属性的产品。以下是对这段代码功能的详细分析：类定义：定义了一个公开的类Product，这意味着这个类可以在其他任何地方被访问和实例化。成员变量：Stringbrand;：表示产品的品牌，类型为String。Stringtype;：表示产品的型号，类型为String。intreviews;：表示产品的评论数，类型为int。intprice;：表示产品的价格，类型为int。构造函数：用于创建Product类的实例并初始化其成员变量。当创建Product对象时，需要提供这四个参数（品牌、型号、评论数和价格）。方法重写：toString()方法被重写以返回包含产品品牌、型号、评论数和价格的字符串表示，格式为"[品牌,型号,评论数,价格]"。public

classProduct{Stringbrand;//品牌

Stringtype;//型号

int

reviews;//评论数

int

price;//价格publicProduct(Stringbrand,Stringtype,int

reviews,int

price){

super();

this.brand=brand;

this.type=type;

this.reviews=reviews;

this.price=price;}

@Override

publicStringtoString(){

return

"["+brand+","+type+","+reviews+","+price+"]";}}定义了一个名为ProductSort的类，它用于对一组Product对象进行排序。以下是对这段代码功能的详细分析：构造函数：ProductSort(Product[]r)是一个构造函数，它接收一个Product类型的数组r作为参数，并将这个数组赋值给类的成员变量r。这样，ProductSort类的实例就可以访问并操作这个Product数组了。扩展性：注释中提到“//在后面添加各类排序算法”，这表明类的设计考虑到了未来可能需要对Product数组进行不同类型的排序操作。因此，尽管当前类中没有实现任何排序逻辑，但它为添加这些逻辑提供了基础结构。排序算法的添加：基于类的当前设计，可以在ProductSort类中添加多种排序算法的方法，例如冒泡排序、快速排序、归并排序等。这些方法将使用类的成员变量r（即Product数组）作为输入，并可能修改这个数组以反映排序后的结果。灵活性和通用性：通过将Product数组作为类的成员变量，ProductSort类可以轻松地实现多种排序算法，而无需在每次调用排序方法时都传递数组作为参数。这增加了代码的灵活性和通用性。public

classProductSort{Product[]r;

publicProductSort(Product[]r){

this.r=r;}

//在后面添加各类排序算法}排序算法如春风化雨，将杂乱无章的数据梳理成有序的乐章。快速排序如闪电般迅捷，归并排序如细流般稳定，冒泡排序如微风般温柔。每一种算法都承载着智慧与力量，让数据在有序中绽放光彩，为我们的生活带来无尽的便利与美好。任务二

用直接插入排序实现商品按价格排序学习目标理解直接插入排序法和希尔排序的思想能用Java语言实现插入排序法和希尔排序12

插入排序(InsertionSort)的基本思想是：每次将一个待排序的数据元素，按其关键字大小插入到前面已经排好序的数据序列的适当位置，直到全部数据元素插入完成为止。本任务使用两种插入排序方法：直接插入排序和希尔排序完成电商网站商品列表按价格排序。任务描述步骤一：用直接插入排序实现商品按价格排序任务实施直接插入排序将待排序的数据元素存放在数组r[0…n-1]中。初始时，r[0]自成1个有序区，无序区为r[1…n-1]。从i=1起直至i=n-1为止，依次将r[i]插入当前的有序区r[0…i-1]中，生成含n个数据元素的有序区。r[i-1]……r[1]r[0]r[n-1]……r[i+1]r[i]有序区无序区基本思想基本思想用直接插入排序完成电商网站商品列表按价格排序，10个商品的价格分别为：30,69,59,27,34,49,53,99,89,28初始状态：将第一个元素视为已排序序列，即30。已排序：30未排序：69,59,27,34,49,53,99,89,28第1趟排序：将69与已排序的30比较，69大于30，故将69插入到30之后。已排序：30,69第2趟排序：将59与已排序的69和30依次比较，发现59应插入到30之后69之前。已排序：30,59,69第3趟排序：将27与已排序的69,59,30依次比较，发现27应插入到最前面。已排序：27,30,59,69第4趟排序：将34与已排序的69,59,30,27依次比较，发现34应插入到27之后59之前。已排序：27,30,34,59,69未排序：49,53,99,89,28第5趟排序：将49与已排序的69,59,34,30,27依次比较，发现49应插入到34之后59之前。已排序：27,30,34,49,59,69第6趟排序：将53与已排序的69,59,49,34,30,27依次比较，发现53应插入到49之后59之前。已排序：27,30,34,49,53,59,69第7趟排序：将99与已排序的69,59,53,49,34,30,27依次比较，发现99应插入到最后。已排序：27,30,34,49,53,59,69,99第8趟排序：将89与已排序的99,69,59,53,49,34,30,27依次比较，发现89应插入到69之后99之前。已排序：27,30,34,49,53,59,69,89,99未排序：28第9趟排序：将28与已排序的99,89,69,59,53,49,34,30,27依次比较，发现28应插入到27之后。至此，所有元素都已排序完成，得到的价格列表为：27,28,30,34,49,53,59,69,89,99。算法实现对存储Product对象的数组r进行直接插入排序，代码按对象的属性price值对Product对象进行升序排序。比较与移动：内层逻辑首先检查当前元素r[i]（无序区的第一个元素）是否小于其前一个元素r[i-1]（有序区的最后一个元素）。如果是，这意味着r[i]需要被插入到有序区的某个更前面的位置。临时存储与移动元素：将r[i]存储在临时变量tmp中，然后通过一个内层循环（j从i-1开始，向下遍历直到j为0或tmp.price不小于r[j].price），将有序区的元素向后移动一个位置，以为tmp腾出空间。插入元素：将tmp（即原来的r[i]）插入到它应该在的位置，这个位置由j+1给出，因为j是最后一个小于tmp.price的元素的索引，所以tmp应该被插入到j+1的位置。继续排序：继续外层循环，直到所有元素都被正确地插入到有序区的适当位置。public

void

insertSort(){

for(int

i=1;i<r.length;i++){

//判断无序区的第一个元素是否小于有序区的最后一个元素

if(r[i].price<r[i-1].price){

//将待插入元素存储在临时变量tmp中

Producttmp=r[i];

int

j=0;

//将有序区的元素向后移动，为待插入元素留出位置

for(j=i-1;j>=0&&tmp.price<r[j].price;j--){

r[j+1]=r[j];}

//将r[i]插入到有序区的位置上

r[j+1]=tmp;}}}算法应用public

classTestProductSort{

public

static

voidmain(String[]args){Product[]plist={newProduct("inphic","PB1P",20,30),

newProduct("logitech","M220",100,69),

newProduct("rapoo","M300G",20,59),

newProduct("inphic","PW1h",50,27),

newProduct("mi","Lite2",200,34),

newProduct("logitech","M187P",1,49),

newProduct("inphic","DR01",2,53),

newProduct("logitech","M330",100,99),

newProduct("dareu","EM915",50,89),

newProduct("inphic","PM6",100,28)};System.out.println("排序前的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}ProductSortpsort=newProductSort(plist);

psort.insertSort();System.out.println("排序后的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}}}创建一个类TestProductSort，调用ProductSort类的直接插入排序法insertSort实现商品列表按价格排序。创建商品列表：首先，创建了一个Product对象的数组plist，并初始化了10个商品对象，每个对象都被赋予了品牌名、型号、评论数和价格。打印排序前的商品列表：然后，通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示（Product类重写了toString()方法以返回包含品牌名、型号、评数论和价格的字符串）。这样，用户可以看到排序前商品列表的顺序。排序商品列表：接着，创建了一个ProductSort类的实例psort，并将plist数组作为参数传递给它的构造函数。然后，调用psort的insertSort()方法来对商品列表进行排序。打印排序后的商品列表：最后，再次通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示。此时，由于已经调用了insertSort()方法对商品列表进行了排序，所以打印出的商品列表将按照价格从低到高的顺序排列。直接插入排序，小巧而强大，适用于小数据集。它如同手工整理卡片，一张接一张地插入到正确的位置，保持整体的整洁有序。这种排序方式逻辑简单，实现容易，让数据在不知不觉中变得井井有条。步骤二：用希尔排序实现商品

按价格排序任务实施希尔排序（ShellSort）是插入排序的一种。因D.L.Shell于1959年提出而得名。是对待排数据元素序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是“跳跃式”的插入排序。将数据元素序列r[0…n-1]分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的数据元素构成的。假设增量为d，将n个数据元素分成d子序列，每个子序列有k个元素，则这d个子序列分别为：基本思想{r[0]，r[0+d]，r[0+2d]，…，r[0+(k-1)d]}{r[1]，r[1+d]，r[1+2d]，…，r[1+(k-1)d]}…{r[d-1]，r[d-1+d]，r[d-1+2d]，…，r[d-1+(k-1)d]}d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。基本思想用希尔排序完成电商网站商品列表按价格排序，10个商品的价格分别为：30,69,59,27,34,49,53,99,89,28第1趟排序：d=3，将数字列表分成了3个子序列{30，27，53，28}、{69，34，99}、{59，49，89}子序列排序：{27，28，30，53}、{34，69，99}、{49，59，89}总排序结果：{27,34,49,28,69,59,30,99,89,53}第2趟排序：d=2，将数字列表分成了2个子序列{27，49，69，30，89}、{34，28，59，99，53}子序列排序：{27，30，49，69，89}、{28，34，53，59，99}总排序结果：{27,28,30,34,49,53,69,59,89,99}第3趟排序：d=1,对第2趟排序的总排序结果进行了微调，交换了69与59总排序结果：[27,34,49,28,59,69,30,99,89,53]至此，所有元素都已排序完成，得到的价格列表为：27,28,30,34,49,53,59,69,89,99。算法实现对存储Product对象的数组r进行希尔排序，代码按对象的属性price值对Product对象进行升序排序。初始化增量：通过intincrement=r.length/3来初始化增量，在每次迭代中减1。排序过程：在内部循环中，通过if(r[i].price<r[i-d].price)来判断是否需要移动元素。这里r是一个包含Product类型对象的数组，且Product类型有一个price属性用于比较。如果需要移动元素，代码使用一个do-while循环来查找插入位置，并通过后移元素来腾出空间。当j-d<0时，循环会立即退出，确保在插入元素之前j的值是有效的（即不会超出数组边界）。插入元素：在找到正确的插入位置后，代码将tmp（即要插入的元素）赋值给r[j]。public

voidshellSort(){

int

i,j,d;Producttmp;

//增量的起始值取数字序列总长度的1/3

int

increment=r.length/3;

for(int

m=increment;m>=1;m--){

d=m;

for(i=d;i<r.length;i++)

//将r[d+1．．n]分别插入各组当前的有序区

if(r[i].price<r[i-d].price){

tmp=r[i];

j=i;

do{//查找r[i]的插入位置r[j]=r[j-d];//后移数据元素

j=j-d;//查找前一数据元素

if(j-d<0)

break;}while(j>0&&tmp.price<r[j-d].price);

r[j]=tmp;//插入r[i]到正确的位置上

}

}}算法应用public

classTestProductSort{

public

static

voidmain(String[]args){Product[]plist={newProduct("inphic","PB1P",20,30),

newProduct("logitech","M220",100,69),

newProduct("rapoo","M300G",20,59),

newProduct("inphic","PW1h",50,27),

newProduct("mi","Lite2",200,34),

newProduct("logitech","M187P",1,49),

newProduct("inphic","DR01",2,53),

newProduct("logitech","M330",100,99),

newProduct("dareu","EM915",50,89),

newProduct("inphic","PM6",100,28)};System.out.println("排序前的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}ProductSortpsort=newProductSort(plist);psort.shellSort();System.out.println("排序后的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}}}创建一个类TestProductSort，调用ProductSort类的希尔排序法shellSort实现商品列表按价格排序。创建商品列表：首先，创建了一个Product对象的数组plist，并初始化了10个商品对象，每个对象都被赋予了品牌名、型号、评论数和价格。打印排序前的商品列表：然后，通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示（Product类重写了toString()方法以返回包含品牌名、型号、评数论和价格的字符串）。这样，用户可以看到排序前商品列表的顺序。排序商品列表：接着，创建了一个ProductSort类的实例psort，并将plist数组作为参数传递给它的构造函数。然后，调用psort的shellSort()方法来对商品列表进行排序。打印排序后的商品列表：最后，再次通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示。此时，由于已经调用了shellSort()方法对商品列表进行了排序，所以打印出的商品列表将按照价格从低到高的顺序排列。步骤三：分析插入排序的时间复杂度任务实施直接插入排序的时间复杂度直接插入排序算法的时间复杂度分为最好、最坏和随机三种情况。

（1）最好的情况是关键字在序列中顺序有序。这时外层循环的比较次数为n-1，if条件的比较次数为n-1,内层循环的次数为0。这样，外层循环中每次记录的比较次数为2，整个序列的排序所需的记录关键字的比较次数为2(n-1)，移动次数为0，所以直接插入排序算法在最好情况下的时间复杂度为O(n)。

（2）最坏情况是关键字在记录序列中逆序有序。这时内层循环的循环系数每次均为i。这样，整个外层循环的比较次数为：

移动的次数为

因此，直接插入排序算法在最坏情况下的时间复杂度为O(n2)。

（3）如果顺序表中的记录的排列是随机的，则记录的期望比较次数为n2/4。因此，直接插入排序算法在一般情况下的时间复杂度为O(n2)。可以证明，顺序表中的记录越接近于有序，直接插入排序算法的时间效率越高，其时间效率在O(n)到O(n2)之间。

希尔排序的时间复杂度希尔排序的时间复杂度分析是一个复杂的问题，它实际所需要的时间取决于各次排序时增量的取法，即增量的个数和它们的取值。大量研究证明，若增量序列的取值比较合理，希尔排序时关键字比较次数和记录移动次数接近于O(n(log2n)2)。由于该分析涉及一些复杂的数字问题，超出了本书的范围，这里不做详细的推导。希尔排序的时间复杂度分析是一个复杂的问题，它实际所需要的时间取决于各次排序时增量的取法，即增量的个数和它们的取值。由于希尔排序法是按增量分组进行的排序，所以希尔排序是不稳定的排序。希尔排序法适用于中等规模记录序列的排序。

希尔排序，以渐进之姿，巧妙地将复杂数据化繁为简。它通过分组跳跃，逐步缩小间隔，使元素有序排列。每一次迭代，都为最终的完美排序铺路，正如人生中的每一个小小努力，终将汇聚成巨大的成就。任务三

用直接选择排序实现商品按价格排序学习目标理解直接选择排序和堆排序的思想能用Java语言实现直接选择排序和堆排序12

选择排序（SelectionSort）的基本思想是将排序序列分为有序区和无序区，每一趟排序从无序区中选出最小（或最大）的元素放在有序区的最后，从而扩大有序区，直到全部元素有序为止。常用的选择排序方法有直接选择排序和堆排序。本任务使用选择排序方法完成电商网站商品列表按价格排序。任务描述步骤一：用直接选择排序实现商品按价格排序任务实施直接选择排序从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。在直接选择排序中，每次排序完成一个记录的排序，也就是找到了当前剩余记录中关键字最小的记录的位置，n-1次排序就对n-1个记录进行了排序，此时剩下的一个记录必定是原始序列中关键码最大的，应排在所有记录的后面，因此具有n个记录的序列要做n-1次排序。r[i-1]……r[1]r[0]r[n-1]……r[i+1]r[i]有序区无序区基本思想基本思想用直接选择排序完成电商网站商品列表按价格排序，10个商品的价格分别为：30,69,59,27,34,49,53,99,89,28第1趟排序：在未排序序列中找到最小元素27，将其与未排序序列的第一个元素30交换。排序后：已排序序列：27未排序序列：69,59,30,34,49,53,99,89,28第2趟排序：在未排序序列（27之后的部分）中找到最小元素28，与未排序序列的第一个元素69交换。排序后：已排序序列：27,28未排序序列：59,30,34,49,53,99,89,69第3趟排序：在未排序序列（28之后的部分）中找到最小元素30，与未排序序列的第一个元素59交换。排序后：已排序序列：27,28,30未排序序列：59,34,49,53,99,89,69继续排序……第9趟排序：在未排序序列（89之后的部分）中找到最小元素89，为未排序序列的第一个元素，无须交换，排序完毕。经过几轮排序后，每次从未排序序列中找到最小元素，并与未排序序列的第一个元素交换。最终状态：排序后序列：27,28,30,34,49,53,59,69,89,99此时，未排序序列为空，所有元素都已排序完毕。算法实现对存储Product对象的数组r进行直接选技排序，代码按对象的属性price值对Product对象进行升序排序。初始化：定义一个整型变量k，用于记录在当前遍历过程中找到的最小元素的下标。定义一个Product类型的临时变量tmp，用于在交换元素时作为中间变量。外层循环：外层循环控制排序的趟数，从数组的第一个元素开始，直到倒数第二个元素（因为最后一个元素在前面的趟数中已经被排好序了，所以不需要再比较）。对于每一趟排序，i是当前趟数要确定其位置的元素的下标（或者说是已排序部分的末尾的下标）。内层循环：内层循环从i+1开始，遍历i之后的所有元素，以找到这些元素中的最小元素的下标k。如果在遍历过程中发现某个元素的price小于当前记录的最小元素的price（即r[j].price<r[k].price），则更新k为这个较小元素的下标。交换：如果k不等于i，说明在i之后的元素中找到了一个更小的元素，需要将这个更小的元素与当前i位置的元素交换。使用临时变量tmp来交换r[i]和r[k]。排序结果：经过r.length-1趟排序后，数组r将根据Product对象的price属性从小到大排序。public

voidselectSort(){

int

k;//k记下目前找到的最小关键字所在的位置

Producttmp;

for(int

i=0;i<r.length-1;i++){

k=i;

for(int

j=i+1;j<r.length;j++)

if(r[j].price<r[k].price)

k=j;

if(k!=i){

tmp=r[i];

r[i]=r[k];

r[k]=tmp; }}}算法应用public

classTestProductSort{

public

static

voidmain(String[]args){Product[]plist={newProduct("inphic","PB1P",20,30),

newProduct("logitech","M220",100,69),

newProduct("rapoo","M300G",20,59),

newProduct("inphic","PW1h",50,27),

newProduct("mi","Lite2",200,34),

newProduct("logitech","M187P",1,49),

newProduct("inphic","DR01",2,53),

newProduct("logitech","M330",100,99),

newProduct("dareu","EM915",50,89),

newProduct("inphic","PM6",100,28)};System.out.println("排序前的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}ProductSortpsort=newProductSort(plist);

psort.selectSort();System.out.println("排序后的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}}}创建一个类TestProductSort，调用ProductSort类的直接选择排序法selectSort实现商品列表按价格排序。创建商品列表：首先，创建了一个Product对象的数组plist，并初始化了10个商品对象，每个对象都被赋予了品牌名、型号、评论数和价格。打印排序前的商品列表：然后，通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示（Product类重写了toString()方法以返回包含品牌名、型号、评数论和价格的字符串）。这样，用户可以看到排序前商品列表的顺序。排序商品列表：接着，创建了一个ProductSort类的实例psort，并将plist数组作为参数传递给它的构造函数。然后，调用psort的selectSort()方法来对商品列表进行排序。打印排序后的商品列表：最后，再次通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示。此时，由于已经调用了selectSort()方法对商品列表进行了排序，所以打印出的商品列表将按照价格从低到高的顺序排列。在数据结构的世界里，直接选择排序如同一位勇敢的探险家，逐个寻找并确定最小（或最大）的元素，将其放置在正确的位置。每一步都充满决心和智慧，最终将无序的在数组转化为有序的宝藏，展现出算法的奇妙与力量。步骤二：用堆排序实现商品按价格排序任务实施堆排序是在直接选择排序的基础上借助于完全二叉树而形成的一种排序方法。将待排序的数据元素建成一个堆，并借助于堆的性质进行排序的方法叫作堆排序。设有n个数据元素，首先将这n个数据元素按关键码建成堆，将堆顶数据元素输出，得到n个数据元素中关键码最大（或最小）的数据元素；调整剩余的n-1个数据元素，使之成为一个新堆，再输出堆顶数据元素；如此反复，当堆中只有一个数据元素时，整个序列排序结束，得到的序列便是原始序列的非递减或非递增序列。基本思想设有n个元素组成的序列r[0…n-1]，若满足下面的条件：（1）这些元素是一棵完全二叉树的结点，且对于i=0，1，…，n-1，r[i]是该完全二叉树编号为i的结点；（2）满足下列不等式：满足不等式(a)的为最大堆，满足不等式(b)的为最小堆。堆有如下两个性质：（1）最大堆的根结点是堆中关键码最大的结点，最小堆的根结点是堆中关键码最小的结点，称堆的根结点数据元素为堆顶数据元素。（2）对于最大堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递减有序的；对于最小堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递增有序的。基本思想用堆排序完成电商网站商品列表按价格排序，10个商品的价格分别为：30,69,59,27,34,49,53,99,89,28（1）i=(n-1)/2=(10-1)/2=4对应的关键码为34，2i+1=9对应的关键码值为28，2i+2=10超出顺序表的最大下标9，不需要调整。如图(a)所示。

（2）i=(n-1)/2-1=(10-1)/2-1=3对应的关键码值为27，2i+1=7对应的关键码值为99，2i+2=8对应的关键码值为89，交换关键码27和99的位置，如图(b)所示。（3）i=(n-1)/2-2=(10-1)/2-2=2对应的关键码为59，2i+1=5对应的关键码为49，2i+2=6对应的关键码为53，不需要调整，如图(c)所示。（4）i=(n-1)/2-3=(10-1)/2-3=1对应的关键码为69，2i+1=3对应的关键码为99，2i+2=4对应的关键码为34，交换关键码69和99的位置，这导致i=3所对应的关键码69小于i=8所对应的关键码89，交换关键码69和89的位置，如图(d)所示。（5）i=(n-1)/2-4=(10-1)/2-4=0对应的关键码为30，2i+1=1对应的关键码为99，2i+2=2对应的关键码为59，交换关键码30和99的位置，这导致i=1所对应的关键码30小于i=3时所对应的关键码89，交换关键码30和89的位置，又导致i=3时所对应的关键码30小于i=8时所对应的关键码69，交换关键码30和69的位置，如图(e)所示。经过这个过程建立了以关键码99为根结点的完全二叉树，它是一个最大堆，如图(f)所示。算法实现对存储Product对象的数组r进行堆排序，代码按对象的属性price值对Product对象进行升序排序方法createHeap（）创建堆参数检查：首先，它检查low是否小于high且high是否小于r.length，以确保子区间[low,high]在数组r的有效范围内。初始化变量：然后，它声明了j和k两个变量，但立即将它们都初始化为0，这在循环中会被覆盖。构建最大堆：接下来，使用一个从high/2开始递减到low的循环来遍历子区间的每个元素（注意，从high/2开始是因为这是最后一个非叶子节点的索引）。对于每个元素r[i]，它执行以下操作：（1）将当前元素r[i]存储在临时变量tmp中。（2）将k设置为当前元素的索引i。（3）将j设置为k的左子节点的索引2*k+1。（4）进入一个内部循环，只要j在子区间[low,high]内，就执行以下操作：如果j不是最后一个子节点，并且右子节点的值大于左子节点的值，则将j递增以指向较大的子节点。如果tmp（即原始r[i]）的值小于r[j]的值，则将r[j]上移到r[k]的位置，并更新k和j以继续向下遍历子树。如果tmp的值不小于r[j]的值，则退出内部循环。最后，将tmp（即原始r[i]）放回其最终位置r[k]。结果：循环结束后，子区间[low,high]内的数组r将被构建成一个最大堆。方法heapSort()进行堆排序首先，它调用createHeap方法将整个数组r构建成一个最大堆。这一步完成后，数组的最大元素就是堆顶元素（即r[0]）。然后，它进入一个循环，每次循环都将堆顶元素（即当前最大元素）与数组的最后一个元素交换，这样当前最大元素就被放到了正确的位置上。然后，它将数组的大小减一（因为最后一个元素已经排好序，不需要再参与后续的排序），并调用createHeap方法对剩余的元素重新构建最大堆。这个过程一直重复，直到数组被完全排序public

voidcreateHeap(int

low,int

high){

if((low<high)&&(high<r.length)){

int

j=0;

int

k=0;Producttmp;

for(int

i=high/2;i>=low;--i){

tmp=r[i];

k=i;

j=2*k+1;

while(j<=high){

if((j<high)&&(j+1<=high)&&(r[j].price<r[j+1].price)){ ++j; }

if(tmp.price<r[j].price){

r[k]=r[j]; k=j; j=2*k+1; }else{

break; } }

r[k]=tmp; } } }

public

voidheapSort(){Producttmp;createHeap(0,r.length-1);for(int

i=r.length-1;i>0;--i){tmp=r[0];r[0]=r[i];r[i]=tmp;createHeap(0,i-1);}}算法应用public

classTestProductSort{

public

static

voidmain(String[]args){Product[]plist={newProduct("inphic","PB1P",20,30),

newProduct("logitech","M220",100,69),

newProduct("rapoo","M300G",20,59),

newProduct("inphic","PW1h",50,27),

newProduct("mi","Lite2",200,34),

newProduct("logitech","M187P",1,49),

newProduct("inphic","DR01",2,53),

newProduct("logitech","M330",100,99),

newProduct("dareu","EM915",50,89),

newProduct("inphic","PM6",100,28)};System.out.println("排序前的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}ProductSortpsort=newProductSort(plist);psort.heapSort();System.out.println("排序后的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}}}创建一个类TestProductSort，调用ProductSort类的堆排序法heapSort（）实现商品列表按价格排序。创建商品列表：首先，创建了一个Product对象的数组plist，并初始化了10个商品对象，每个对象都被赋予了品牌名、型号、评论数和价格。打印排序前的商品列表：然后，通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示（Product类重写了toString()方法以返回包含品牌名、型号、评数论和价格的字符串）。这样，用户可以看到排序前商品列表的顺序。排序商品列表：接着，创建了一个ProductSort类的实例psort，并将plist数组作为参数传递给它的构造函数。然后，调用psort的heapSort（）方法来对商品列表进行排序。打印排序后的商品列表：最后，再次通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示。此时，由于已经调用了heapSort（）方法对商品列表进行了排序，所以打印出的商品列表将按照价格从低到高的顺序排列。步骤三：分析选择排序时间复杂度任务实施直接选择排序的时间复杂度

在直接选择排序中，第一次排序要进行n-1次比较，第二次排序要进行n-2次比较，第n-1次排序要进行1次比较，所以总的比较次数为：

在各次排序时，记录的移动次数最好0次，最坏为3次。所以，如果data[0…n-1]原来的顺序是从小到大排序的，总的移动次数最好为0次；如果每次选择都要进行交换，则移动次数达到最大值，最坏为3（n-1）次。因此，直接选择排序算法的时间复杂度为O(n2)。

直接选择排序算法只需要一个辅助空间用于交换记录，所以直接选择排序算法是一种稳定的排序方法。堆排序的时间复杂度

对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);对n个关键字，建成深度为h=log2n+1的堆，所需进行的关键字比较的次数至多为4n;调整“堆顶”n-1次，总共进行的关键字比较的次数不超过：2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)堆排序在最坏的情况下，时间复杂度为

O(nlog2n)，这是堆的最大优点。堆排序方法在记录较少的情况下并不适用，但对于记录较多的数据列表还是很有效的。其运行时间主要耗费在建初始堆和调整新建堆时进行的反复筛选。堆排序，如同攀登高峰，将数据有序排列，每一步都稳健而坚定。通过构建最大堆或最小堆，我们巧妙地调整元素位置，最终达到高效排序的目的。它不仅展示了算法的智慧，更体现了对细节的极致追求。任务六

用基数排序实现商品按品牌排序学习目标理解基数排序的思想能用Java语言实现基数排序12

前面介绍的排序方法主要是通过关键码的比较和数据元素的移动两种操作来实现排序，都属于“比较性”的排序法，也就是每次排序时，都比较整个键值的大小来进行排序。基数排序则是属于“分配式排序”，排序过程无须比较关键字值，而是通过“分配”和“收集”过程来实现排序。本任务按商品的品牌的英文升序排序，当商品的名牌相同时，按评论数降序排序，当评论数相同时，按价格升序排序。任务描述步骤一：用基数排序实现商品按价格升序排序任务实施基本思想用基数排序完成电商网站商品列表按价格排序，10个商品的价格分别为：30,69,59,27,34,49,53,99,89,28如图所示，基数排序过程如下：第1次排序：按个位数字提取个位数字：0，9，9，7，4，9，3，9，9，8按照个位数字进行桶排序个位为0的桶：[30]个位为3的桶：[53]个位为4的桶：[34]个位为7的桶：[27]个位为8的桶：[28]个位为9的桶：[69,59,49,99,89]第1次收集：[30,53,34,27,28,69,59,49,99,89]第2次排序：按十位数字提取十位数字：3，5，3，2，2，6，5，4，9，8按照十位数字进行桶排序：十位为2的桶：[27,28]十位为3的桶：[30,34]十位为4的桶：[49]十位为5的桶：[53,59]十位为6的桶：[69]十位为8的桶：[89]十位为9的桶：[99]第2次收集：[27,28,30,34,49,53,59,69,89,99]至此，元素排序完成。基数排序无须比较关键字，而是通过“分配”和“收集”过程来实现排序。将待比较的数据元素拆分成一个个数字或字符，其中每个数字或字符可能的取值个数称为基数。如数位为数字，可将所有待比较数据统一为同样的数位长度，数位较短的数前面补零，按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。如果元素类型是字符串的话，在计数排序过程中，可以直接使用该位字符对应ASCII码值进行计数，对于长度不足的字符串，可直接在其后面补0实现长度对齐。即在计数排序过程中，如果发现某位字符是为对齐所填充的“0”的话，则可认为其对应的ASCII码值为0进行计数，因为字符’A’所对应的ASCII码值是65，字符’0’所对应的ASCII码值是48，均比0大。这样即可保证基数排序的结果是符合字典顺序的。按待排序数据元素关键字的组成成份进行排序的一种方法，即依次比较各个数据元素关键字相应“位”的值，进行排序，直到比较完所有的“位”，得到一个有序的序列。算法实现对存储Product对象的数组r进行基数排序，算法依据对象的price属性值对Product对象进行升序排列。定义RadixNode类：这是一个简单的链表节点类，包含两个成员：data（存储一个商品对象）和next（指向下一个RadixNode的指针）。定义radixSort()方法初始化：-创建了一个RadixNode类型的数组head，大小为10，用于在基数排序的每一轮中存储0到9这10个数字对应的链表头部。计算r数组中price的最大值，并确定price的位数d，以便知道需要进行多少轮排序。排序过程：对于价格的每一位（从最低位到最高位），执行以下步骤：调整power变量的值的，这个变量在基数排序中用于确定当前正在处理的数字的哪一位。当i==0时，正在处理最低位（个位）时，将power设置为1。当i>0时，正在处理更高位（十位、百位等）时，将power乘以10。为每个可能的数字（0-9）创建一个链表的头节点head[j]（j从0到9）。static

classRadixNode{

publicProductdata;//数据域

publicRadixNodenext;//引用域

}

//基数排序

public

voidradixSort(){

int

k,l,power;RadixNodep,q;RadixNode[]head=newRadixNode[10];

power=1;

int

max=r[0].price;

for(int

i=1;i<r.length;i++){

if(r[i].price>max){

max=r[i].price;}}

int

d=0;//关键码的位数

while(max>0){

d