吉林大学：《数据结构》课程电子教案（PPT课件）第八章 排序

第八章 排序

第八章 排序

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； } }

for（intj=2;j=n;jt+) e=list[j];i=j-1; while (e.GetKey()<list[i].GetKey()) {1ist[i+1]=1ist[i];i--;} 1ist[i+1]=e;}) k0] k(1] k2] k[3] k4] K5] j 8 7 2 4 6 2 -0 [8] 7 2 4 6 3 -0 [7 8] 2 4 6 4 -0 [2 7 8] 4 6 5 -00 [2 4 7 8] 6 -0 [2 4 6 7 8]

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； } } k[0] k[1] k[2] k[3] k[4] k[5] j －∞ 8 7 2 4 6 －∞ [2 4 6 7 8] 2 －∞ [8] 7 2 4 6 4 －∞ [2 7 8] 4 6 3 －∞ [7 8] 2 4 6 5 －∞ [2 4 7 8] 6

·直接插入排序算法 ◆优点：是算法的执行过程相当清晰，并 ◆ 且书写容易. ◆缺点：期望复杂性为0(n) ◆稳定性：直接插入排序是稳定的排序方法。 ·最好情况是：当被排序文件初态为正序时， 算法的时间复杂度为0(n) ◆空间复杂度：0(1)

 直接插入排序算法  优点:是算法的执行过程相当清晰，并  且书写容易.  缺点:期望复杂性为O(n2) .  稳定性：直接插入排序是稳定的排序方法。  最好情况是：当被排序文件初态为正序时， 算法的时间复杂度为O(n) .  空间复杂度： O(1)

8.2.2希尔排序 。希尔排序（渐减增量排序法）思想： 把记录按下标的一定增量分组，对每组使用直接 插入排序法，随着增量逐渐减少，所分成的组包 含的关键词越来越多，到增量值减至1时，整个 文件恰好被分成一个组，算法便告终止 。希尔排序增量的取法： d1=Ln/2」=L10/2」=5 d2Ld1/2」=L5/2」=2 d3=Ld2/2」=L2/2」=1

8.2.2 希尔排序 ● 希尔排序（渐减增量排序法）思想： 把记录按下标的一定增量分组，对每组使用直接 插入排序法，随着增量逐渐减少，所分成的组包 含的关键词越来越多，到增量值减至1时，整个 文件恰好被分成一个组，算法便告终止. ● 希尔排序增量的取法： d1= = =5 ∟n/2 ∟ ∟10/2 ∟ d2= = =2 ∟d1/2 ∟ ∟5/2 ∟ d3= = =1 ∟d2/2 ∟ ∟2/2 ∟

[例]将十个数进行希尔排序的示例。 下标 01234 56789 36.25.4812.6525.43…58.7632 d1=5 25 36 43 48 58 2 32 65 一趟 25254812323643587665 排序结果

[例] 将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9 36 25 48 12 65 25 43 58 76 32 下标 d1=5 36 25 25 43 48 58 12 76 65 32 25 36 32 65 一趟 25 25 48 12 32 36 43 58 76 65 排序结果

[例]将十个数进行希尔排序的示例。 下标 01234567 89 25254812323643587665 d2=2 距 32 43 48 76 12 25 36 58 65 二趙 251232254336 48587665 排序结果 三趟 12252532364348586576 排序结果 d=1

[例] 将十个数进行希尔排序的示例。 下标 0 1 2 3 4 5 6 7 8 9 d2=2 25 25 48 12 32 36 43 58 76 65 25 48 32 43 76 25 12 36 58 65 32 43 48 12 25 二趟 25 12 32 25 43 36 48 58 76 65 排序结果 三趟 12 25 25 32 36 43 48 58 65 76 排序结果 d3=1