选择排序
简单选择排序
算法描述
n-1次遍历，每次选出一个未排序区域中的最小元素放入已排序区域中的合适位置。
算法实现
void SelectSort(SqList &L) {
for(i = 1; i < L.length; i++) {
k = i;
for(j = i + 1; j <= L.length; j++)
if(L.r[j].key < L.r[k].key) k = j;
if(k != i) {t = L.r[i]; L.r[i] = L.r[k]; L.r[k] = t;}
}
}
算法分析
- 时间复杂度
最好情况（初始正序）：不移动
最坏情况（初始逆序）：移动3(n-1)次
时间复杂度是O(n²) - 空间复杂度
交换元素时需要一个辅助空间，空间复杂度是O(1)
算法特点
- 稳定排序。
- 适用于链式存储结构。
- 移动次数较少。当每个记录占空间较大时，比直接插入排序快。
树形选择排序
算法描述
用有n个结点的完全二叉树表示，其中每个非终端结点的值是他的左右孩子的最小值，所以根的值是待排序列中的最小值。找到最小值之后，将最小值对应的叶子的值改为∞，对于该叶子到根的路径上的所有值进行过再次比较更新，找出次小值。
算法分析
- 时间复杂度
除了最小值，选择其他关键字时只需要比较log2(n)次，时间复杂度为O(nlog2(n)). - 所需存储空间多，存在与已被选出的叶子节点的多余比较。
堆排序
堆
堆是一种满足所有非终端结点的值均不大于（小根堆）/小于（大根堆）其左右孩子结点的值的完全二叉树。其根必为最小/大值。
堆排序
算法描述
建立在完全二叉树的顺序存储基础上。先将待排序序列建成一个小根堆，交换根和最后一个值，即现在最后一个位置是最小值。然后从1到n-1个元素再次建立小根堆，交换第一个和最后一个值。也就是说每一次堆化再交换一次之后，能确定的就是排在序列后面部分的最大值。不断重复，直到交换了第一个和第二个值为止。
算法实现
- 筛选法调整堆
从根到叶地进行调整，直到整个树再次符合堆的性质。
void HeapAdjust(SqList &L, int s, int m) {
rc = L.r[s];
for(j = 2 * s; j <= m; j *= 2) {
if(j < m && L.r[i].key < L.r[j + 1].key) j++;
if(rc.key >= L.r[j].key) break;
L.r[s] = L.r[j]; s = j;
}
L.r[s] = rc;
}
- 建初堆
只有一个结点的树一定是堆。完全二叉树中所有序号大于floor(n/2)的结点都是叶子，所以他们都是堆。所以只需要从最后一个非叶子节点floor(n/2)开始依次将以其及其前面序号的结点为根的子树调整为堆。
void CreateHeap(SqList &L) {
n = L.length;
for(i = n / 2; i > 0; i--)
HeapAdjust(L, i, n);
}
- 堆排序
建初堆，然后反复进行堆顶堆底的交换和堆调整。
void HeapSort(SqList &L) {
CreateHeap(L);
for(i = L.length; i > 1; i--) {
x = L.r[1]; L.r[1] = L.r[i]; L.r[i] = x;
HeapAdjust(L, 1, i - 1);
}
}
算法分析
- 时间复杂度
平均时间复杂度接近于最坏性能O(nlog2(n)) - 空间复杂度
需要一个交换辅助空间，复杂度为O(1)
算法特点
- 不稳定排序。
- 不适用于链式结构。
- 建初堆成本较大，不适用于元素较少的情况，元素较多时比较高效。