第八章 排序
第八章 排序
8.1基本概念 排序：就是把一组记录按照某个域的值的递增 或递减的次序重新排列的过程。 ● 主关键字：能唯一标识某一记录的关键字叫主 关键字 。稳定性：具有相同关键字的记录排序前后保持 它们原来的相对次序不变，则称该排序过程具 有稳定性。 。内部排序：若排序过程都在内存中进行，则称 为内部排序。 。外部排序：若排序过程需要不断地进行内存和 外存之间的数据交换，则称为外部排序
8.1 基本概念 ● 排序:就是把一组记录按照某个域的值的递增 或递减的次序重新排列的过程。 ● 主关键字：能唯一标识某一记录的关键字叫主 关键字 ● 稳定性：具有相同关键字的记录排序前后保持 它们原来的相对次序不变，则称该排序过程具 有稳定性。 ● 内部排序：若排序过程都在内存中进行，则称 为内部排序。 ● 外部排序：若排序过程需要不断地进行内存和 外存之间的数据交换，则称为外部排序
8.2插入排序 8.2.1直接插入排序 。直接插入排序思想： 将一个记录插入到已排好序的有序表中，从尔 得到一个新的、记录数增一的有序表
8.2 插入排序 8.2.1 直接插入排序 ● 直接插入排序思想： 将一个记录插入到已排好序的有序表中，从尔 得到一个新的、记录数增一的有序表
。插入排序的算法 记录类Element的定义： Class Element public: int GetKey()const return key; void SetKey(int k){key=k; private: int key; //其他“辅助信息”域 }；
● 插入排序的算法 记录类Element的定义： Class Element { public： int GetKey( ) const { return key；} void SetKey( int k ){ key=k；} private： int key； … … // 其他“辅助信息”域 }；
void InsertSortA(Element *list,int n 81s丰乐 Element e; list[0].SetKey(Ko); for（intj=2;j-n;jt+) e=list[j]; i=j-1; while e.GetKey()<list[i].GetKey()) list[i+1]list[i]; i--;} 1ist[i+1]=e;})
void InsertSortA( Element *list， int n ) // 将序列 list[1] ， … ， list[n] 排 序 ， K0≤min{ Kj | 1≤j≤n } { Element e; list[0]. SetKey(K0 )； for ( int j=2；j<=n；j++ ) { e = list[j]； i = j–1； while ( e. GetKey( ) < list[i]. GetKey( ) ) { list[i+1] = list[i]； i − −；} list[i+1] = e； } }