数据结构课件.pdfVIP

The 7th Course SORTING Requirements  In an external sort, there are so many records to be sorted that they must be kept in external files on disks, tapes, or the like. In an internal sort the records can all be kept internally in high-speed memory. We consider only internal sorting.  We use the notation and classes set up in Chapters 6. Thus we shall sort lists of records into the order determined by keys associated with the records.  If two or more of the entries in a list have the same key, we must exercise special care. Requirements  To analyze sorting algorithms, we consider both the number of comparisons of keys and the number of times entries must be moved inside a list, particularly in a contiguous list.  Both the worst-case and the average performance of a sorting algorithm are of interest. To and the average, we shall consider what would happen if the algorithm were run on all possible orderings of the list (with n entries, there are n! such orderings altogether) and take the average of the results. Requirements To write efficient sorting programs, we must access the private data members of the lists being sorted. Therefore, we shall add sorting functions as methods of our basic List data structures. The augmented list structure forms a new ADT that we shall call a Sortable_list. Requirements a Sortable_list is a List with extra sorting methods. The base list class can be any of the List implementations of Chapter 6. We use a template parameter class called Record to stand for entries of the Sortable_list. Requirements  Every Record has an associated key of type Key. A Record can be implicitly converted to the corresponding Key. The keys (hence also the records) can be compared under the operations ` , ` , ` = , ` = , ` == , and ` != . Ordered In