文章目录 回顾 提要 排序基本概念 排序的分类 排序算法的稳定性 排序算法的性能指标 内排序 排序方法 直接插入排序 直接插入排序的要点 直接插入排序的实现 直接插入排序性能分析 直接插入排序的适用情景 简单选择排序 简单选择排序的要点 简单选择排序的执行过程 简单选择排序的实现 简单选择排序性能分析 简单选择排序的适用情景 总结
哈希存储结构通过哈希函数确定关键字的存储地址。 哈希表设计重点包括哈希函数构造和冲突解决方法。 哈希函数构造方法：直接定址法、除留余数法、数字分析法等。 解决冲突的方法：开放定址法、线性探查法、平方探查法等。 将无序记录序列调整为有序记录序列的操作。 例如，将下列记录序列： 调整为递增序列： 通常指定记录的某个数据项作为关键字进行排序。 排序关键字可以重复。 按待排序记录所在位置：内部排序和外部排序。 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则：插入排序、交换排序、选择排序、归并排序。 插入排序：直接插入排序、折半插入排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 稳定的排序算法保持具有相同关键字记录的相对次序。 如原序列中，ki = kj 且 ki 在 kj 之前，排序后 ki 仍在 kj 之前，即为稳定。 排序前：{ 8, 3, 5, 2, 4, 9, 5, 6 } 排序后：{ 2, 3, 4, 5, 5, 6, 8, 9 } 稳定 排序后：{ 2, 3, 4, 5, 5, 6, 8, 9 } 不稳定 时间开销：比较次数和移动次数。 比较：关键字之间的比较； 移动：将记录从一个位置移动到另一个位置。 空间开销：辅助存储空间。 算法的稳定性。 待排记录存放在内存中进行排序。 排序对象 针对关键字（排序码）的序列 排序算法默认以顺序表为存储结构 非递减有序 后面讲述的插入排序、交换排序、选择排序、归并排序等都是指的内排序。 学习排序方法的思想、实现、时间性能、空间性能、稳定性和适用情景。 序列分为有序区和无序区，每次将无序区的第一个元素插入到有序区的适当位置。 初始时，第一个元素构成有序区，其余为无序区。 每趟排序，待插入元素为无序区的第一个元素。 从后向前比较，插入元素大于当前元素则后移。 无序区为空时，排序结束。 基本操作：比较和移动的次数，决定了排序的时间性能。 待排序列为“正序”时，比较和移动的次数最少； 待排序列为“逆序”时，比较和移动的次数最多。 算法评价 时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1)。只使用i、j和tmp共3个辅助变量，与问题规模n无关。 void InsertSort ( ElemType L[ ] , int len) { int i, j; ElemType tmp; for ( i = 1 ; i < len; i++ ) { tmp = L[ i] ; for ( j = i - 1 ; j >= 0 ; j-- ) { if ( tmp < L[ j] ) L[ j + 1 ] = L[ j] ; else break ; } L[ j + 1 ] = tmp; }
}
时间复杂度：( T(n) = O(n^2) ) 空间复杂度：( S(n) = O(1) ) 稳定排序算法，适用于基本有序或记录较少的情况。 移动操作总是发生在相邻的元素之间，因而是一种稳定的排序算法。 算法简单、容易实现，适用于待排序记录基本有序或待排序记录较少时。 当待排序的记录个数较多时，大量的比较和移动操作使算法的效率降低。 序列分为有序区和无序区，每次选择无序区关键字最小的元素与第一个元素交换。 初始时，有序区为空，全部元素处于无序区。 每趟选择无序区最小关键字元素与第一个元素交换。 无序区剩下最后一个元素时，排序结束。 通过多趟选择，逐步构建有序区。 void SelectSort ( ElemType L[ ] , int len) { int i, j, min; ElemType tmp; for ( i = 0 ; i < len - 1 ; i++ ) { min = i; for ( j = i + 1 ; j < len; j++ ) if ( L[ j] < L[ min] ) min = j; if ( min != i) { tmp = L[ i] ; L[ i] = L[ min] ; L[ min] = tmp; } }
}
时间复杂度：( T(n) = O(n^2) ) 空间复杂度：( S(n) = O(1) ) 不稳定排序算法，适用于记录个数较多时，移动操作次数较少。 介绍了排序算法的概念、分类以及直接插入排序和简单选择排序的排序过程、实现和性能分析。 
