插入排序
直接插入排序
算法描述
将一条记录插入到有序表中，得到新的有序表。
将需要调整位置的元素暂存在r[0]处，然后再进行插入。
算法实现
void InsertSort(SqList &L) {
for(i = 2; i <= L.length; i++)
if(L.r[i].key < L.r[i - 1].key) {
L.r[0] = L.r[i]; L.r[i] = L.r[i - 1];
for(j = i - 2; L.r[0].key < L.r[j].key; j--)
L.r[j + 1] = L.r[j]; // 逐个后移 找到插入位置
L.r[j + 1] = L.r[0];
}
}
算法分析
- 时间复杂度
关键字比较次数KCN + 记录移动次数RMN = O(n²) - 空间复杂度
只需要一个辅助空间r[0]，空间复杂度是O(1)
算法特点
- 稳定排序。
- 也适用于链式存储。
- 适用于初始记录基本有序的情况。
折半插入排序
算法描述
将直接插入排序的查找方式改为折半排序，提高平均性能。
算法实现
void BInsertSort(SqList &L) {
for(i = 2; i <= L.length; i++) {
L.r[0] = L.r[i];
low = 1; high = i - 1;
while(low <= high) {
m = (low + high) / 2;
if(L.r[0].key < L.r[m].key) high = m - 1;
else low = m + 1;
}
for(j = i - 1; j >= high + 1; j--)
L.r[j + 1] = L.r[j];
L.r[high + 1] = L.r[0];
}
}
算法分析
- 时间复杂度
折半插入的查找比直接插入快，但无法减少移动次数。
插入第i个记录时需要经过floor(log2(i) + 1)次比较。
关键字比较次数KCN + 记录移动次数RMN = O(n²) - 空间复杂度
只需要一个辅助空间r[0]，空间复杂度是O(1)
算法特点
- 稳定排序。
- 不适用于链式存储。
- 适用于初始记录无序、n较大的情况。
希尔排序
算法描述
本质上是一种分组插入。
事先确定一个增量数组，每次取出一个增量d，把所有间隔为d的元素分成一组，全部元素共分成d组，在每个组中分别进行直接插入排序。
直接插入排序是一种增量为1的希尔排序。
算法实现
void ShellInsert(SqList &L, int dk) {
for(i = dk + 1; i <= L.length; i++)
if(L.r[i].key < L.r[i - dk].key) {
L.r[0] = L.r[i];
for(j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
L.r[j + dk] = L.r[j]; // 找到插入位置
L.r[j + dk] = L.r[0];
}
}
void ShellSort(SqList &L, int dt[], int t) {
for(k = 0; k < t; k++)
ShellInsert(L, dt[k]); // 增量为dt[t]
}
算法分析
- 时间复杂度
低于直接插入排序，具体难以计算，但n取向无穷时，时间复杂度为n(log2(n))² - 空间复杂度
只需要一个辅助空间r[0]，空间复杂度是O(1)
算法特点
- 不稳定排序。
- 不适用于链式存储。
- 增量值互质，必须递减，最后一个增量值必须为1.
- 适用于初始记录无序、n较大的情况。
交换排序
冒泡排序
算法描述
每一趟比较过程中，将第一个与第二个、第二个与第三个、……第n-1个与第n个分别比较，逆序就交换。如果某一趟过程中没有发生交换，则排序完毕。
算法实现
void BubbleSort(SqList &L) {
m = L.length - 1; flag = 1;
while((m > 0) && (flag == 1)) {
flag = 0;
for(j = 1; j <= m; j++)
if(L.r[j].key > L.r[j + 1].key) {
flag = 1;
t = L.r[j]; L.r[j] = L.r[j + 1]; L.r[j + 1] = t;
}
m--;
}
}
算法分析
- 时间复杂度
最好（初始正序）：一趟 n-1次关键字比较 不移动
最坏（初始逆序）：n-1趟
平均时间复杂度O(n²) - 空间复杂度
交换过程中需要一个暂存辅助，复杂度为O(1)
算法特点
- 稳定排序。
- 可以用于链式结构。
- 初始无序且元素较多时效率低。
快速排序
算法描述
任意（一般是第一个）取一个元素作为基准（数值大小意义上的基准），设置左右两个指针，初始时指向表的下界和上界。右指针从右往左搜索，找到第一个比基准小的元素，移到左指针指向的位置；然后左指针从左往右搜索，找到第一个比基准大的元素，移到右指针指向的位置；一直重复，直到左右指针指向同一位置。将基准放在该位置，将序列分为左右两个序列。
整体来看就是基准点把待排序序列分成左右两个子表，然后对于任何一个表都有一个基准点和左右子表，所有小于基准点的都放在他左边，大于基准点的都放在他右边。
算法实现
int Partition(SqList &L, int low, int high) {
L.r[0] = L.r[low]; // 基准点移动
pivotkey = L.r[low].key;
while(low < high) {
while(low < high && L.[high].key >= pivotkey) high--;
L.r[low] = L.r[high];
while(low < high && L.r[low].key <= pivotkey) low++;
L.r[high] = L.r[low];
} // 一次排序
L.r[low] = L.r[0]; // 基准点复位
return low;
}
void QSort(SqList &L, int low, int high) {
if(low < high) {
pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);
QSort(L, pivtloc + 1, high); // 左右子表分别递归
}
}
void QuickSort(SqList &L) {
QSort(L, 1, L.length);
}
算法分析
- 时间复杂度
最好（初始正序）：一趟 n-1次关键字比较 不移动
最坏（初始已经排号）：递归树为单支树，需要n-1趟
平均时间复杂度O(nlog2(n))
*避免最坏情况出现的方法“三者取中”：比较表中第一个、中间一个、最后一个关键字，事先把处于中间位置的换到第一个，然后再开始排序。通过这种方式防止递归树成为单支树。 - 空间复杂度
最大递归调用次数等于递归树的深度。
复杂度最好为O(log2(n))，最坏为O(n)
算法特点
- 不稳定排序。
- 不适用于链式结构。
- 平均情况下是内部排序中最快的（以空间换时间），适用于初始记录无序、n较大。
如何判断某个序列（不知原序列情况下）可不可能是第i趟快速排序后的结果？
快排每一趟都会将那一趟的基准放到其最终位置，这个位置满足：前面所有都比基准小，后面所有都比基准大。如果是第i趟，则应该能找到（至少）i个元素已经到达对应位置。
选择排序
简单选择排序
算法描述
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)
算法特点
- 不稳定排序。
- 不适用于链式结构。
- 建初堆成本较大，不适用于元素较少的情况，元素较多时比较高效。
基数排序
链式基数排序
算法描述
采用最低位优先法LSD思想，借助分配和收集两种操作进行排序。
例如需要对一些三位正整数从小到大排序。首先比较个位，个位相同的放在同一队列中（类似桶排），此时队列内部无序，队列间按照个位从小到大排序，相对有序。然后按照十位、百位重复以上操作，比较完百位则完成排序。
算法分析
- 时间复杂度
对于n个记录，每个记录有d个关键字，每个关键字取值为rd：每一趟分配的时间复杂度为O(n)，每一趟收集为O(rd)，共进行d次分配和收集操作，所以时间复杂度为O(d(n+rd)) - 空间复杂度
队列和链表指针域，空间复杂度为O(n+rd)
算法特点
- 稳定排序
- 适用于链式结构
- 需要知道各关键字的主次关系和各关键字取值范围