第10章内部非序 10.1概述 10.2插入排序 10.3交换排序 10.4选择排序 10.5归并排序 10.6基数排序
1 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 第10章 内部排序
10.2插入排序 边插入边排序，保证子序列中随时都是排好序的。 插入排序有多种具体实现算法： 1)直接插入排序 2)折半插入排序 3)2-路插入排序 小改进 4表插入排序 5)希尔排序 大改进 闪
2 10.2 插入排序 插入排序有多种具体实现算法： 1) 直接插入排序 2) 折半插入排序 3）2-路插入排序 4) 表插入排序 5) 希尔排序 边插入边排序，保证子序列中随时都是排好序的。 小改进 大改进
课堂练习： 以关键字序列(256,301,751,129,937,863,742， 694,076,438)为例，分别写出执行以下算法的各趟排 序结束时，关键字序列的状态，并说明这些排序方法中， 哪些易于在链表（包括各种单、双、循环链表）上实现？ ①直接插入排序 ②希尔排序（取dk=5,3,1) 答：显然，直接插入排序方法易于在链表上实现；但希尔排 序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：
3 课堂练习： 以关键字序列（256，301，751，129，937，863，742， 694，076，438）为例，分别写出执行以下算法的各趟排 序结束时，关键字序列的状态，并说明这些排序方法中， 哪些易于在链表（包括各种单、双、循环链表）上实现？ ① 直接插入排序 ② 希尔排序（取dk=5,3,1） 答：显然，直接插入排序方法易于在链表上实现；但希尔排 序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：
原始序列：256,301,751,129,937,863,742,694,076,438 直 第1趟[256,301]，751,129,937,863,742,694,076,438 第2趟 [256,301,751],129,937,863,742,694,076,438 留 第3趟 [129,256,301,751],937,863,742,694,076,438 第4趟 [129,256,301,751,937],863,742,694,076,438 排 第5趟[129,256,301,751,863,937]，742,694,076,438 第6趟[129,256,301,742,751,863,937]，694,076,438 第7趟[129,256,301,694,742,751,863,937]，076,438 第8趟[076,129,256,301,694,742,751,863,937]，438 第9趟[076,129,256,301,438,694,742,751,863,937]
4 原始序列： 256，301，751，129，937，863，742，694，076，438 [256，301]，751，129，937，863，742，694，076，438 [256，301，751]，129，937，863，742，694，076，438 [129，256，301，751]，937，863，742，694，076，438 [129，256，301，751，937]，863，742，694，076，438 [129，256，301，751，863，937]，742，694，076，438 [129，256，301，742，751，863，937]，694，076，438 [129，256，301，694，742，751，863，937]，076，438 [076，129，256，301，694，742，751，863，937]，438 [076，129，256，301，438，694，742，751，863，937] 第1趟 第2趟 第3趟 第4趟 第5趟 第6趟 第7趟 第8趟 第9趟
原始序列：256,301,751,129,937,863,742,694,076,438 希 第1趟256,301,694,076,438,863,742,751,129,937 dk=5 排 第2趟 076,301,129,256,438,694,742,751,863,937 dk=3 第3趟 076,129,256,301,438,694,742,751,863,937 dk=1 (取dk-5,3,1)
5 原始序列： 256，301，751，129，937，863，742，694，076，438 (取dk=5, 3, 1) 第1趟 256，301，751 694，129 076，937 48，863，742，694 751，076 129，438 97 dk=5 第2趟 dk=3 第3趟 dk=1 256 07，301，694 129，076 25，438，863 694，742，751，129 863，937 076，301 129，129 256，256 301，438，694，742，751，863，937