选择排序的多种实现

实验6选择排序的多种实现

1回顾：数组数组是同种类型的有限个元素组成的有序的集合，其特点是：有限，同类，有序我们可以通过数组的下标来直接访问数组中的任一元素。数组元素与数据类型是数组基类型的普通变量一样，既可以作为左值，又可以作为右值一维数组是只需一个下标即可确定一个数组元素的数组在C++中，一维数组的存储形式是顺序连续存储2回顾：结构结构用于将不同数据类型的元素（数据项）聚合为一个整体。每个数据项称为该结构的一个成员。结构成员与相应数据类型的普通变量一样，既可以作为左值，又可以作为右值用户可以利用已定义的数据类型的数据项和系统规定的规则定义出自己所需的数据类型3回顾：结构结构定义示例：structRECORD{ intorderID; charcompanyName[100]; charcity[50]; charcountry[50]; charproductName[100]; doubleunitPrice; intquantity; doublediscount; charshippedDate[11];};4回顾：结构结构可作为一个整体进行赋值、取地址、sizeof等操作，或作为函数调用的实际参数、返回值例如：RECORDf1(RECORDr);RECORDr1,r2,*p;…………r1=r2;r2=f1(r1);结构也可以通过对象成员访问运算符（.）或指针成员访问运算符（->）和成员名来访问某个成员例如：cin>>r1.orderID;cin>>p->orderID;r1.quantity+=10;p->quantity+=10;5交换排序排序：排序是把一个无序的数据元素序列整理成有规律的、按排序关键字递增（减）排列的有序序列的过程关键字(Key)：数据对象中作为排序依据的的数据项（成员）正序与逆序：按关键字从小到大排列称为正序；按关键字从大到小排列称为逆序6交换排序交换排序：是一类常用的排序算法，其基本思想是：两两比较待排序记录的关键字（即排序码），如果不合排序要求，则交换之，直到所有对象都排好为止我们学习过的冒泡排序就是一种典型的交换排序

冒泡排序示例7交换排序交换排序的基本操作比较操作交换操作

8选择排序选择排序(SelectionSort)：也是一种交换排序其基本思想为：每一趟从待排序的记录中选出关键字最小的记录，同待排序的第一个记录交换，直到全部记录排序完毕

选择排序示例9选择排序vs.冒泡排序冒泡排序：不断比较并交换相邻记录，因此第i小的记录是一步步地越过前面比它大的那些记录，最后到达正确位置选择排序：直接找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，一步到位选择排序过程最多需要n-1次交换，而冒泡排序平均交换次数为O(n×n)，相比之下，选择排序的交换次数少多了

10本次实验的要求本次实验要求使用选择排序算法实现一个程序，将一组合同记录按不同的关键字进行排序，并尽量减少排序所需时间11如何减少排序所需时间？交换排序中基本的操作是比较操作与交换操作。如果能减少比较操作/交换操作的执行次数，或减少每次比较操作/交换操作的执行时间，就可以提高排序程序的运行速度12如何减少排序所需时间？三种方法：改进算法，减少比较操作/交换操作的执行次数改进代码，减少每次比较操作/交换操作的执行时间改进数据结构，如将排序关键字的数据类型改为比较操作速度更快的类型13改进算法的例子冒泡排序中的交换标志冒泡排序－>选择排序14改进代码的例子由于结构对象的赋值和传值调用时需要对结构内部所有成员的值进行复制，需要较多的CPU运行时间，因此很多时候，我们可以通过对结构对象的引用/指针/数组下标进行操作等间接方式来代替直接对结构对象进行赋值和传值调用，以减少运行时间开销例如,对如下定义的函数：

//RECORD为一个已经定义的结构类型voidfun(RECORDx);

进行调用时，编译程序会安排将实际参数的值复制到形式参数变量中，需要较多的运行时间。如果将其改变为如下形式：

voidfun(RECORD*px);则只需要复制实际参数的值（一个指针，VC++6中一般为32位）到形式参数变量中，可节省一些运行时间开销15改进代码的例子对于交换操作也可以进行类似的改进。此时我们一般不直接对记录数组进行排序，而是对一个与记录数组相对应的下标数组进行排序。排序完毕后要对记录数组进行顺序操作（如按排好的顺序输出）时，即可通过下标数组来完成。这种方式称为间接排序。16改进代码的例子例如，对如下记录数组进行排序待排数组17改进代码的例子我们设置一个下标数组待排数组0123456789101112131415161718192021下标数组18改进代码的例子排序时的交换操作不直接交换记录数组元素，只对相应的下标数组元素进行交换待排数组0123456789101112131415161718192021下标数组19改进代码的例子排序完毕后也可以使用指针来代替数组下标实现间接排序，其效率与使用数组下标差不多，但程序可更简洁

记录数组1720321101918141651324111501271898下标数组20改进数据结构的例子示例程序中，合同记录的发货日期字段使用字符串来表示日期（如”12/06/1996”）字符串的比较需要对串中字符逐个比较，耗时较多如果将其改为用8位数字的整数来表示（如：），由于整数比较操作速度较快，可减少排序所需时间21如何测量运行时间？秒表？太粗糙通常的做法是在程序（段）运行前记录计算机的系统时间（不一定是以通常的时/分/秒为单位，更多时候是以系统内的某个计数器的一次变化为单位），在程序（段）运行后再次记录系统时间，二者的差值即为运行时间只要各次测量使用的是相同的时间单位，即可对比相应的运行时间22计时函数startClock()/stopClock()单位为毫秒（ms）startSysCircleClock()

/stopSysCi