(9.1.1)--ch9-1排序基本概念.pdf

Data Structures and AlgorithmsBasic Concepts of Sorting Data Structures and Algorithms Data Structures and Algorithms29.1 The basic concept of sortingChapter 9 Internal sorting Sorting is the process of adjusting a set of unordered record sequence to an ordered record sequence。For example：adjust the following keyword adjust the following keyword sequence:sequence:52,49,80,36,14,58,61,23,97,7552,49,80,36,14,58,61,23,97,75To:To:14,23,36,49,52,58,61,75,80,9714,23,36,49,52,58,61,75,80,97 Data Structures and Algorithms Data Structures and Algorithms39.1 The basic concept of sortingChapter 9 Internal sorting Definition of sorting：Suppose a sequence of N records is R1,R2,，Rn The corresponding keyword sequence is K1,K2,，Kn These keywords can be compared with each other,that is,there is such a relationship between them：Kp1Kp2KpnAccording to this inherent relationship,the above record sequence is rearranged as Rp1,Rp2,，Rpn is called sorting Data Structures and Algorithms Data Structures and Algorithms49.1 The basic concept of sortingChapter 9 Internal sorting SortingInternal sortingExternal sortingThe whole sorting process can be completed without access to external memoryIf the number of records participating in the sorting is large,the sorting process of the entire sequence cannot be completed in memorystable sortingunstable sortingSortingThe leading relationship of the same keyword does not change during the sorting processThe leading relationship of the same keyword changes during the sorting process Data Structures and Algorithms Data Structures and Algorithms9.1 The basic concept of sortingChapter 9 Internal sorting Basic operationcomparison swappinginsertion classesexchange classesselection classesmerge classesdistribution classesSorting method Data Structures and Algorithms Data Structures and AlgorithmsThank you allThank you all！