入排序思路因是个按关键字有序的序列，可用折半查找实现“在中的定位”，如此实现的插入排序为折半插入排序。插入位置与中间元素比,若中间元素大则,使得右侧均比待插入元素大,且定位区间缩小半否则使得左侧均比待插入元素小或相等,区间小半,至不成立。此时,右侧是第个比待插入元素大的元素，插入位置为实际等于。稳定上页下页节末页结束后移填入稳定，但基本有序时不如直接插入排序与中间元素比,若中间元素大则,使得右侧均比待插入元素大否则使得左侧均比待插入元素小或相等,至不成立。此时,右侧是第个比待插入元素大的元素，插入为实际等于。上页下页节末页结束希尔排序设增量序列,子序列直接用插入排序方法每趟希尔排序将记录序列分成个子序列，分别对各子序列进行直接插入排序。最后趟时对全部记录进行直接插入排序。又称缩小增量排序第趟希尔排序，设增量第二趟希尔排序，设增量不稳定第三趟希尔排序，设增量,插入排至,左侧均小于枢轴,右侧均大于枢轴,将枢轴记录填入,完成分块二趟快速排序不稳定！上页下页节末页结束快速排序中次划分的算法,返回划分位置保存枢轴从右侧找第个小于枢轴的记录将比枢轴小的记录移动到低端从左侧找第个大于枢轴的记录将比枢轴大的记录移动到高端枢轴记录到位返回枢轴最后所在位置上页下页节末页结束首先对无序的大序列进行“次划分”，之后分别对分割所得两个小子序列“递归”进行快速排序。待快长为时自然有序无序的记录序列无序记录子序列无序子序列枢轴次划分分别进行快速排序三快速排序上页下页节末页结束对顺序表的子序列作快速排序块长大于对进行划分,是枢轴最终位置对小块递归排序对大块递归排序结论快速排序的平均时间复杂度为平均性能在各排序算法中最优但递归过程中需要个栈,原本有序时枢轴均位于端栈最长为,空间复杂度最坏,此时退化为冒泡排序,最坏时间复杂度。平均情况下空间复杂度，不稳定上页下页节末页结束小结直接插入排序正序时最好时间复杂度,逆序最坏,平均，空间复杂度稳定折半插入排序,原本无序能比直接插入好，但均稳定希尔排序缩小增量排序平均时间复杂度不稳定冒泡排序改进正序时时间复杂度最好,逆序最坏,平均稳定快速排序枢轴平均时间复杂度,最优,正序或逆序时最坏时间复杂度,有辅助栈,空间复杂度最坏,平均不稳定推荐习题上页下页节末页结束选择类排序简单选择排序•树形选择排序堆排序上页下页节末页结束思路每趟都选择当前最小的元素交换到“无序块”的最前，共趟则完成排序!输出元素选择排序第趟选择第趟选择第趟选择原始状态第趟选择图选择排序全过程加底纹者为被交换的数据，方框内为尚待排序数据选择排序趟数或无序块首位置当前最小记录下标比较始终次移动至多次,最少上页下页节末页结束第十章内部排序上页下页节末页结束第十章内部排序排序的定义和相关术语插入类排序交换类排序选择类排序归并类排序基数类排序排序方法比较上页下页节末页结束概述排序若干记录对其关键字进行比较，按关键字由小到大或由大到小的顺序对记录序列重新排列,默认非递减序张三李四王五冯六陈七排序方法的稳定性依据时与两者间是否保持原次序不变内部排序与外部排序根据排序开始时所有待排记录的存放位置或者说根据排序过程中是否需要访问外存分上页下页节末页结束待排顺序表最大长度关键字类型为整数类型关键字项其它数据项记录类型闲置留作它用记录个数顺序表存储,因记录元素个数固定排序的数据类型与存储结构定义上页下页节末页结束插入排序直接插入排序表插入排序折半插入排序希尔排序上页下页节末页结束直接插入排序思路首记录自身有序,从第二个记录到最末个,每次都将当前记录插入其前有序表中使得仍然有序实现将待插入记录与其前有序段中记录从后向前逐个比较若则不需移动否则先后移对其前的元素只要大于待插入记录就后移，为保证终止，设置哨。最后将待插入记录填入即可哨兵,后移填入上页下页节末页结束直接插入排序的性能分析,比较哨初始化,也算作移动移动,比较移动填入,也算作移动最好情况待排序列按关键字非递减有序正序最坏情况待排序列按关键字非递增有序逆序“比较”的次数“移动”的次数含哨赋值和填入时间复杂度平均操作次数空间复杂度稳定！上页下页节末页结束有序序列无序序列插入类排序的基本思想有序序列无序序列插入类将无序子序列中的记录插入到有序序列适当位置中,从而增加有序子序列的长度至最后上页下页节末页结束折半插入排序思路因是个按关键字有序的序列，可用折半查找实现“在中的定位”，如此实现的插入排序为折半插入排序。插入位置与中间元素比,若中间元素大则,使得右侧均比待插入元素大,且定位区间缩小半否则,