首页 excel排序教程

excel排序教程

excel排序教程nullnull概述插入排序交换排序选择排序归并排序基数排序外排序小结概述概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist): 它是待排序数据对象的有限集合。关键码(key): 通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键码。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键码。null主关键码: 如果在数据表中各个对象的关键码互不相同...

nullnull概述插入排序交换排序选择排序归并排序基数排序外排序小结概述概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表 (datalist): 它是待排序数据对象的有限集合。关键码(key): 通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键码。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键码。null主关键码: 如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排序，排序的结果是唯一的。次关键码: 数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j]，它们的关键码 k[i] == k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。null内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。null静态排序: 排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。动态排序: 给每个对象增加一个链接指针，在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。算法执行时所需的附加存储: 评价算法好坏的另一标准。静态排序过程中所用到的数据表类定义，体现了抽象数据类型的思想。null待排序数据表的类定义 #ifndef DATALIST_H #define DATALIST_H #include const int DefaultSize = 100; template class datalist { template class Element { private: Type key; //关键码 field otherdata; //其它数据成员 public: Element ( ) : key(0), otherdata(NULL) { } null Type getKey ( ) { return key; } //提取关键码 void setKey ( const Type x ) { key = x; } //修改 Element & operator = //赋值 ( Element & x ) { this = x; } int operator == ( Type & x ) //判this == x { return ! ( this < x || x < this ); } int operator != ( Type & x ) //判this != x { return this < x || x < this; } int operator <= ( Type & x ) //判this  x { return ! ( this > x ); } int operator >= ( Type & x ) //判this  x { return ! ( this < x ); } int operator < ( Type & x ) //判this < x { return this > x; } null} template class datalist { public: datalist ( int MaxSz = DefaultSize ) : //构造函数 MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } void swap ( Element & x, //对换 Element & y ) { Element temp = x; x = y; y = temp; } private: Element * Vector; //存储向量 int MaxSize, CurrentSize; //最大与当前个数 }插入排序 (Insert Sorting)插入排序 (Insert Sorting)直接插入排序的基本思想是：当插入第i (i  1) 个对象时，前面的V[0], V[1], …, v[i-1]已经排好序。这时，用v[i]的关键码与v[i-1], v[i-2], …的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。插入排序的基本方法是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。直接插入排序 (Insert Sort)null各趟排序结果21254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*160825i = 10 1 2 3 4 5 temp21254925*160849i = 2null21254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*1608i = 40 1 2 3 4 5 temp21254925*1608i = 5i = 325*1608null1649161621254925*16080 1 2 3 4 50 1 2 3 4 5 temp21254925*08i = 4 时的排序过程0 1 2 3 4 5 temp21254925*完成160816i = 4 j = 3i = 4 j = 2null2525*161621254925*080 1 2 3 4 50 1 2 3 4 5 temp214925*080 1 2 3 4 5 temp21254925*160816162521i = 4 j = 1i = 4 j = 0i = 4 j = -116null直接插入排序的算法 template void InsertionSort ( datalist & list ) { //按关键码 Key 非递减顺序对表进行排序 for ( int i = 1; i < list.CurrentSize; i++ ) Insert ( list, i ); } template viod Insert ( datalist & list, int i ) { Element temp = list.Vector[i]; int j = i; //从后向前顺序比较算法分析算法分析若设待排序的对象个数为curremtsize = n，则该算法的主程序执行n-1趟。关键码比较次数和对象移动次数与对象关键码的初始排列有关。while ( j > 0 && temp.getKey ( ) < list.Vector[j-1].getKey ( ) ) { list.Vector[j] = list.Vector[j-1]; j--; } list.Vector[j] = temp; }null最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较 1 次，移动 2 次对象，总的关键码比较次数为 n-1，对象移动次数为 2(n-1)。最坏情况下，第 i 趟时第 i 个对象必须与前面 i 个对象都做关键码比较，并且每做 1 次比较就要做 1 次数据移动。则总的关键码比较次数KCN和对象移动次数RMN分别为null若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。直接插入排序是一种稳定的排序方法。折半插入排序 (Binary Insertsort)折半插入排序 (Binary Insertsort)折半插入排序基本思想是：设在顺序表中有一个对象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已经排好序的对象。在插入 v[i] 时，利用折半搜索法寻找 v[i] 的插入位置。折半插入排序的算法 template void BinaryInsertSort ( datalist & list ) { for ( int i = 1; i < list.CurrentSize; i++) BinaryInsert ( list, i ); }nulltemplate void BinaryInsert ( datalist & list, int i ) { int left = 0, Right = i-1; Element temp = list.Vector[i]; while ( left <= Right ) { int middle = ( left + Right )/2; if ( temp.getKey ( ) < list.Vector[middle].getKey ( ) ) Right = middle - 1; else left = middle + 1; } for ( int k = i-1; k >= left; k-- ) list.Vector[k+1] = list.Vector[k]; 算法分析算法分析对分查找比顺序查找快，所以对分插入排序就平均性能来说比直接插入排序要快。它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。因此，将 n 个对象（为推导方便，设为 n=2k )用对分插入排序所进行的关键码比较次数为： list.Vector[left] = temp; }nullnull当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比对分插入排序执行的关键码比较次数要少。对分插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。对分插入排序是一个稳定的排序方法。链表插入排序链表插入排序链表插入排序的基本思想是：在每个对象的结点中增加一个链接指针数据成员 link。对于存放于数组中的一组对象V[1], V[2], …, v[n]，若v[1], V[2], …, v[i-1]已经通过指针link，按其关键码的大小，从小到大链接起来，现在要插入v[i], i = 2, 3, …, n，则必须在前面i-1个链接起来的对象当中，循链顺序检测比较，找到v[i]应插入(或链入)的位置，把v[i]插入，并修改相应的链接指针。这样就可得到v[1], V[2], …, v[i]的一个通过链接指针排列好的链表。如此重复执行，直到把v[n]也插入到链表中排好序为止。null254925*16080 1 2 3 4 5 6i = 2i = 321初始current pre icurrent pre i pre current ii = 4null254925*16080 1 2 3 4 5 6i = 5i = 621 pre current i结果pre current inull链表插入排序示例null用于链表排序的静态链表的类定义 template class staticlinklist; template class Element { private: Type key; //结点的关键码 int link; //结点的链接指针 public: Element ( ) : key(0), link (NULL) { } Type getKey ( ) { return key; } //提取关键码 void setKey ( const Type x ) { key = x; } //修改 int getLink ( ) { return link; } //提取链指针 void setLink ( const int l ) { link = l; } //设置指针null} template class staticlinklist { public: dstaticlinklist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) //构造函数 { Vector = new Element [MaxSz]; } private: Element * Vector; //存储向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 }null链表插入排序的算法 template int LinkInsertSort ( staticlinklis & list ) { list.Vector[0].setKey ( MaxNum ); list.Vector[0].setLink ( 1 ); list.Vector[1].setLink ( 0 ); //形成循环链表 for ( int i = 2; i <= list.CurrentSize; i++ ) { int int current = list.Vector[0].getLink ( ); int pre = 0; //前驱指针 while ( list.Vector[current].getKey ( ) <= list.Vector[i].getKey ( ) ) { //找插入位置 pre = current; //pre跟上, current向前走 current = list.Vector[current].getLink ( ); } 算法分析算法分析使用链表插入排序，每插入一个对象，最大关键码比较次数等于链表中已排好序的对象个数，最小关键码比较次数为1。故总的关键码比较次数最小为 n-1，最大为 list.Vector[i].setLink ( current ); list.Vector[pre].setLink ( i ); //在pre与current之间链入 } }null用链表插入排序时，对象移动次数为0。但为了实现链表插入，在每个对象中增加了一个链域 link，并使用了vector[0]作为链表的表头结点，总共用了 n 个附加域和一个附加对象。算法从 i = 2 开始，从前向后插入。并且在vector[current].Key == vector[i].Key时，current还要向前走一步，pre跟到current原来的位置，此时， vector[pre].Key == vector[i].Key。将vector[i]插在vector[pre]的后面，所以，链表插入排序方法是稳定的。希尔排序 (Shell Sort)希尔排序 (Shell Sort)希尔排序方法又称为缩小增量排序。该方法的基本思想是：设待排序对象序列有 n 个对象，首先取一个整数 gap < n 作为间隔，将全部对象分为 gap 个子序列，所有距离为 gap 的对象放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap，例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 1，将所有对象放在同一个序列中排序为止。null21254925*16080 1 2 3 4 52125*i = 10849Gap = 32516492516084925*0821252125*16null21254925*16080 1 2 3 4 521i = 20849Gap = 22516491625*0821254925*08162125*25null开始时 gap 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。21254925*16080 1 2 3 4 521i = 308Gap = 125164925*null希尔排序的算法 template void Shellsort ( datalist & list ) { int gap = list.CurrentSize / 2; // gap 是子序列间隔 while ( gap ) { //循环,直到gap为零 ShellInsert ( list, gap ); //一趟直接插入排序 gep = gep == 2 ? 1 : ( int ) ( gap/2.2 ); //修改 } }nulltemplate void shellInsert ( datalist & list; const int gep ) { //一趟希尔排序,按间隔gap划分子序列 for ( int i = gap; i < list.CurrentSize; i++) { Element temp = list.Vector[i]; int j = i; while ( j >= gap && temp.getKey ( ) < list.Vector[j-gap].getKey ( ) ) { list.Vector[j] = list.Vector[j-gap]; j -= gap; } list.Vector[j] = temp; } }算法分析算法分析Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。后来knuth 提出取gap = gap/3 +1。还有人提出都取奇数为好，也有人提出各gap互质为好。对特定的待排序对象序列，可以准确地估算关键码的比较次数和对象移动次数。但想要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。nullKnuth利用大量的实验统计资料得出，当 n 很大时，关键码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。交换排序 ( Exchange Sort )交换排序 ( Exchange Sort )起泡排序的基本方法是：设待排序对象序列中的对象个数为 n。最多作 n-1 趟，i = 1, 2, , n-2 。在第 i 趟中顺次两两比较v[n-j-1].Key和v[n-j].Key，j = n-1, n-2, , i。如果发生逆序，则交换v[n -j-1]和v[n-j]。交换排序的基本思想是两两比较待排序对象的关键码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有对象都排好序为止。起泡排序 (Bubble Sort)null21254925*16080 1 2 3 4 52125*i = 149251625160849Exchang=10825*4921Exchang=1i = 2i = 30816Exchang=125*2521null25*0 1 2 3 4 5i = 44916Exchang=0082521起泡排序的算法 template void BubbleSort (datalist & list ) { int pass = 1; int exchange = 1; while ( pass < list.CurrentSize && exchange ){ BubbleExchange ( list, pass, exchange ); pass++; } }nulltemplate void BubbleExchange ( datalist & list , const int i, int & exchange ) { exchange = 0; //交换标志置为0,假定未交换 for ( int j = list.CurrentSize-1; j >= i; j-- ) if ( list.Vector[j-1].getKey ( ) > list.Vector[j].getKey ( ) ) { //逆序 Swap ( list.Vector[j-1], list.Vector[j] );//交换 exchange = 1; //交换标志置为1,有交换 } } 算法分析算法分析第 i 趟对待排序对象序列v[i-1], v[i], , v[n-1]进行排序，结果将该序列中关键码最小的对象交换到序列的第一个位置(i-1)，其它对象也都向排序的最终位置移动。当然在个别情形下，对象有可能在排序中途向相反的方向移动。这样最多做n-1趟起泡就能把所有对象排好序。在对象的初始排列已经按关键码从小到大排好序时，此算法只执行一趟起泡，做 n-1 次关键码比较，不移动对象。这是最好的情形。最坏的情形是算法执行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次关键码比较，执行了n-i 次对象交换。这样在最坏情形下总的关键码比较次数KCN和对象移动次数RMN为：起泡排序需要一个附加对象以实现对象值的对换。起泡排序是一个稳定的排序方法。快速排序 (Quick Sort)快速排序 (Quick Sort)快速排序方法的基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的关键码都小于或等于基准对象的关键码右侧子序列中所有对象的关键码都大于基准对象的关键码基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。算法描述QuickSort ( List ) { if ( List的长度大于1) { 将序列List划分为两个子序列 LeftList 和 Right List; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList 合并为一个序列List; } }null21254925*16080 1 2 3 4 52125*i = 149251625160849pivot0825*4921i = 2i = 3081625*2521pivotpivotpivotnull21254925*16080 1 2 3 4 525*i = 1 划分251625160849pivotpos0825*49081625*2521pivotpos21比较4次交换25,16iipivotpos21比较1次交换49,0849low pivotpos交换21,08null快速排序的算法 template void QuickSort ( datalist &list, const int left, const int right ) { //在待排序区间 leftright 中递归地进行快速排序 if ( left < right) { int pivotpos = Partition ( list, left, right ); //划分 QuickSort ( list, left, pivotpos-1); //在左子区间递归进行快速排序 QuickSort ( list, pivotpos+1, right ); //在左子区间递归进行快速排序 } }nulltemplate int Partition ( datalist &list, const int low, const int high ) { int pivotpos = low; //基准位置 Element pivot = list.Vector[low]; for ( int i = low+1; i <= high; i++ ) if ( list.Vector[i].getKey ( ) < pivot.getKey( ) && ++pivotpos != i ) Swap ( list.Vector[pivotpos], list.Vector[i] ); //小于基准对象的交换到区间的左侧去 Swap ( list.Vector[low], list.Vector[pivotpos] ); return pivotpos; } 算法quicksort是一个递归的算法，其递归树如图所示。算法partition利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环，只要是关键码小于基准对象关键码的对象都移到序列左侧，最后基准对象安放到位，函数返回其位置。2125*25490816算法分析算法分析从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。在n个元素的序列中，对一个对象定位所需时间为 O(n)。若设 t(n) 是对 n 个元素的序列进行排序所需的时间，而且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：null T(n)  cn + 2 t(n/2 ) // c是一个常数  Cn + 2 ( cn/2 + 2t(n/4) ) = 2cn + 4t(n/4)  2cn + 4 ( cn/4 +2t(n/8) ) = 3cn + 8t(n/8) ………  Cn log2n + nt(1) = o(n log2n ) 可以证明，函数quicksort的平均计算时间也是o(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。 null快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为 o(log2n)。在最坏的情况，即待排序对象序列已经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过 n-1 趟才能把所有对象定位，而且第 i 趟需要经过 n-i 次关键码比较才能找到第 i 个对象的安放位置，总的关键码比较次数将达到null其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存储(即栈)将达到o(n)。若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度，但是由于对象的初始排列次序是随机的，这个要求很难办到。有一种改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3个对象，取其关键码居中者作为基准对象。null用第一个对象作为基准对象快速排序退化的例子 08 16 21 25 25* 49080 1 2 3 4 5 pivot初始 16 21 25 25* 49 0816 21 25 25* 4921 08 1625 25 25* 49 08 16 21 25* 4925* 08 16 21 2549 08 16 21 25 25*i = 1i = 2i = 3i = 4i = 5null用居中关键码对象作为基准对象快速排序是一种不稳定的排序方法。对于 n 较大的平均情况而言，快速排序是“快速”的，但是当 n 很小时，这种排序方法往往比其它简单排序方法还要慢。 08 16 21 25 25* 490 1 2 3 4 5 pivot21初始 08 16 21 25 25* 490825* 08 16 21 25 25*49i = 1i = 2选择排序选择排序直接选择排序是一种简单的排序方法，它的基本步骤是：在一组对象v[i]～v[n-1]中选择具有最小关键码的对象；选择排序的基本思想是：每一趟 (例如第 i 趟，i = 0, 1, …, n-2) 在后面 n-i 个待排序对象中选出关键码最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-2 趟作完，待排序对象只剩下1个，就不用再选了。直接选择排序 (Select Sort)null 若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调；在这组对象中剔除这个具有最小关键码的对象，在剩下的对象v[i+1]～v[n-1]中重复执行第、步，直到剩余对象只有一个为止。直接选择排序的算法 template void SelectSort ( datalist & list ) { for ( int i = 0; i < list.CurrentSize-1; i++ ) SelectExchange ( list, i ); }nulltemplate void SelectExchange ( datalist & list, const int i ) { int k = i; for ( int j = i+1; j < list.CurrentSize; j++) if ( list.Vector[j].getKey ( ) < list.Vector[k].getKey ( ) ) k = j; //当前具最小关键码的对象 if ( k != i ) //对换到第 i 个位置 Swap ( list.Vector[i], list.Vector[k] ); }null21254925*16080 1 2 3 4 52125*i = 0492516251608490825*4921i = 1i = 2081625*2521初始最小者 08 交换21,08最小者 16 交换25,16最小者 21 交换49,21null4925*0 1 2 3 4 525*i = 42516084925*4921结果i = 308162521最小者 25* 无交换最小者 25 无交换25211608各趟排序后的结果null0 1 2 3 4 549160825*49210825*2521i =1时选择排序的过程i k j 49250825*1621i k j 49  2525*  251625i k j 16 < 25算法分析 49250825*16210 1 2 3 4 5i k j 21  16k 指示当前序列中最小者算法分析直接选择排序的关键码比较次数KCN与对象的初始排列无关。第 i 趟选择具有最小关键码对象所需的比较次数总是 n-i-1 次，此处假定整个待排序对象序列有 n 个对象。因此，总的关键码比较次数为null对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键码从小到大有序的时候，对象的移动次数RMN = 0，达到最少。最坏情况是每一趟都要进行交换，总的对象移动次数为RMN = 3(n-1)。直接选择排序是一种不稳定的排序方法。锦标赛排序 (Tournament Tree Sort)锦标赛排序 (Tournament Tree Sort)它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键码，进行两两比较，得到 n/2 个比较的优胜者(关键码小者)，作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键码的两两比较，…，如此重复，直到选出一个关键码最小的对象为止。在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键码。null如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 < n  2k 的2k个。叶结点上面一层的非叶结点是叶结点关键码两两比较的结果。最顶层是树的根。08Winner 2108086325*2121254925*160863tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]胜者树的概念胜者树的概念每次两两比较的结果是把关键码小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放对象的关键码 data 外，还存放了此对象是否要参选的标志 Active 和此对象在满二叉树中的序号index。胜者树最顶层是树的根，表示最后选择出来的具有最小关键码的对象。 null08Winner (胜者)2108086325*2121254925*160863tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 形成初始胜者树（最小关键码上升到根）a[0]关键码比较次数 : 6 null16Winner (胜者)2116166325*2121254925*1663tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]输出冠军并调整胜者树后树的状态a[1]关键码比较次数 : 2 null21Winner (胜者)21636325*2121254925*63tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]输出亚军并调整胜者树后树的状态a[2]关键码比较次数 : 2 null25Winner (胜者)25636325*25254925*63tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]输出第三名并调整胜者树后树的状态a[3]关键码比较次数 : 2 null25*Winner (胜者)25*636325*4925*63tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]输出第四名并调整胜者树后树的状态a[4]关键码比较次数 : 2 null63Winner (胜者)636363tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14]全部比赛结果输出时树的状态a[6]关键码比较次数 : 2 null胜者树数据结点类的定义 template class DataNode { public: Type data; //数据值 int index; //结点在满二叉树中顺序号 int active; //参选标志：=1, 参选, =0, 不参选 } 锦标赛排序的算法 template void TournamentSort ( Type a[ ], int n ) { DataNode *tree; DataNode item; null int bottomRowSize = PowerOfTwo ( n ); //乘幂值 int TreeSize = 2*bottomRowSize-1; //总结点个数 int loadindex = bottomRowSize-1; //内结点个数 tree = new DataNode[TreeSize]; int j = 0; //从 a 向胜者树外结点复制数据 for ( int i = loadindex; i < TreeSize; i++) { tree[i].index = i; if ( j < n ) { tree[i].active = 1; tree[i].data = a[j++]; } else tree[i].active = 0; } i = loadindex; //进行初始比较选择最小的项 while ( i ) {null j = i; while ( j < 2*i ) { if ( !tree[j+1].active|| //胜者送入双亲 tree[j].data <= tree[j+1].data ) tree[(j-1)/2] = tree[j]; else tree[(j-1)/2] = tree[j+1]; j += 2; } i = (i-1)/2; // i 退到双亲, 直到 i==0为止 } for ( i = 0; i < n-1; i++) { //处理其它n-1个数据 a[i] = tree[0].data; //送出最小数据 tree[tree[0].index].active = 0; //失去参选资格 null UpdateTree ( tree, tree[0].index ); //调整 } a[n-1] = tree[0].data; } 锦标赛排序中的调整算法 template void UpdateTree ( DataNode *tree, int i ) { if ( i % 2 == 0 ) tree[(i-1)/2] = tree[i-1]; //i偶数, 对手左结点 else tree[(i-1)/2] = tree[i+1]; //i奇数, 对手右结点 i = (i-1) / 2; //向上调整 null while ( i ) { //直到 i==0 if ( i %2 == 0) j = i-1; else j = i+1; if ( !tree[i].active || !tree[j].active ) if ( tree[i].active ) tree[(i-1)/2] = tree[i]; //i可参选, i上 else tree[(i-1)/2] = tree[j]; //否则, j上 else //两方都可参选 if ( tree[i].data < tree[j].data ) tree[(i-1)/2] = tree[i]; //关键码小者上 else tree[(i-1)/2] = tree[j]

                    本文档为【excel排序教程】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

excel排序教程

你可能还喜欢