0%
9．内部排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
RedType r[MAXSIZE + 1];
int length;
}SqList;
|
插入排序
直接插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void InsertSort(SqList &L)
{
for(i = 2; i <= L,length; ++i)
{
if(LT(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; LT(L.r[0].key, L.r[j].key); --j)
L.r[j + 1] = L.r[j];
L.r[j + 1] = L.r[0];
}
}
}
|
折半插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
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(LT(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];
}
}
|
- 性能分析
- 空间复杂度：\(O(1)\)
- 时间复杂度：\(O(n)\)
希尔排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void ShellInsert(SqList &L, int dk)
{
for(i = dk + 1; i <= L.length; ++i)
{
if(LT(L.r[i],key, L.r[i - dk],key))
{
L.r[0] = L.r[i];
for(j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
L.r[j + dk] = L.r[j];
L.r[j+dk] = L.r[0];
}
}
}
|
1
2
3
4
5
6
7
8
9
10
|
void ShellSort(SqList &L. int dlta[], int t)
{
for(k = 0; k < t; ++k)
{
ShellInsert(L, dlta[k]);
}
}
|
交换排序
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void BubbleSort(ElemType A[], int n)
{
for(i = 0; i < n - 1; i++)
{
flag = false;
for(j = n - 1; j > i; j--)
{
if(A[j-1].key > A[j].key)
{
swap(A[j-1], A[j]);
flag = true;
}
if(flag = false)
return ;
}
}
}
|
快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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.r[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;
}
|
1
2
3
4
5
6
7
8
9
| void QSort(SqList &L, int low, int high)
{
if(low < high)
{
pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);
QSort(L, pivotloc + 1, high);
}
}
|
选择排序
简单选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void SelectSort(SqList &L)
{
for(i = 1; i < L.length; ++i)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(L.r[j].key < L.r[min].key)
min = j;
}
if(min != i)
swap(L[i], L[min]);
}
}
|
堆排序
1
| typedef SqList HeapType;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void HeapAdjust(HeapType &H, int s, int m)
{
rc = H.r[s];
for(j = 2 * s; j <= m; j *= 2)
{
if(j < m && LT(H.r[j].key, H[j+1].key))
++j;
if(! LT(rc.key, H.r[j].key))
break;
H.r[s] = H.r[j];
s = j;
}
H.r[s] = rc;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void HeapSort(HeapType &H)
{
for(i = H.length / 2; i > 0; --i)
{
HeapAdjust(H, i, H.length);
}
for(i = H.length; i > 1; --i)
{
swap(H.r[1], H.r[i]);
}
HeapAdjust(H, 1, i - 1);
}
|
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void Merge(RcdType SR[], RcdType &TR[], int i, int m, int n)
{
for(j = m + 1, k = i; i <= m && j <= n; ++k)
{
if(LQ(SR[i].key, SR[j].key))
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if(i <= m) TR[k..n] = SR[i..m];
if(j <= n) TR[k..n] = SR[j..n];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void MSort(RcdType SR[], RcdType &TR1[], int s, int t)
{
if(s == t)
TR1[s] = SR[s];
else
{
m = (s + t) / 2;
MSort(SR, TR2, s, m);
MSort(SR, TR2, m + 1, t);
Merge(TR2, TR1, s, m, t);
}
}
|
基数排序
内部排序算法的比较和应用
| 直接插入 |
\(O(n)\)（待排序序列为正序） |
\(O(n^2)\) |
\(O(n^2)\)（待排序序列为逆序） |
\(O(1)\) |
是 |
| 冒泡 |
\(O(n)\)（待排序序列为正序） |
\(O(n^2)\) |
\(O(n^2)\)（待排序序列为逆序） |
\(O(1)\) |
是 |
| 简单选择 |
\(O(n^2)\) |
\(O(n^2)\) |
\(O(n^2)\) |
\(O(1)\) |
否 |
| 希尔 |
|
|
|
\(O(1)\) |
否 |
| 快排 |
\(O(nlog_2n)\)（每次的枢轴划分把表等分为长度相近的两个子表） |
\(O(nlog_2n)\) |
\(O(n^2)\)（待排序序列有序或基本有序） |
\(O(log_2n)\) |
否 |
| 堆排序 |
\(O(nlog_2n)\) |
\(O(nlog_2n)\) |
\(O(nlog_2n)\) |
\(O(1)\) |
否 |
| 2 路归并 |
\(O(nlog_2n)\) |
\(O(nlog_2n)\) |
\(O(nlog_2n)\) |
\(O(n)\) |
是 |
| 基数 |
\(O(d(n+r))\) |
\(O(d(n+r))\) |
\(O(d(n+r))\) |
\(O(r)\) |
是 |
部分算法手算小结
插入排序
直接插入
- 把这个过程想象成抓牌，对牌排序的过程
- 抓牌
- 比较：和当前最后一个牌比较
- 若大于，则插在当前有序表最后（算法流程中，此步不做）
- 若小于，则进入下一步
- 查找插入位置，并插入：有序表中从后往前顺序查找新抓到的牌在有序表中合适的位置，在此过程中融入了移动元素。找到位置后，元素也移动完了，可以直接插入。
折半插入
- 和直接插入不同，折半插入将比较查找和移动元素分离。
- 整个流程概括如下：
- 在当前有序表中折半查找新元素待插入的的位置（请关注一下算法中的插入位置）。
- 以此插入位置，确定需要移动元素的范围，将元素移动到位。
- 插入新元素
希尔排序
- 以间隔将待排序列分组，组内直接插入排序
- 缩小间隔，重复上述操作，直至间隔为 1。
交换排序
冒泡排序
快速排序
选择排序
简单选择
- 在未有序序列部分，选择最小【从小到大排列】（或最大【从大到小】），依次与当前未有序的头部元素交换，完成一趟简单选择排序
堆排序（★★★★★★★★）
堆的建立（利用堆的向下调整）
- 从堆的最后一个结点（即完全二叉树的最后一个叶子结点）开始循环，依次进行如下操作：
- 找到其父亲结点（设为 P ）
- 比较 P
和其两个孩子结点的大小关系（下述流程和向下调整（父和子比较，父向下调整）类似）
- 如果满足堆的定义，则进行下一轮迭代（在向下调整中，此步直接
break，即对结点 P 的调整结束）
- 如果不满足
- 小根堆情况：选择 key 值较小的孩子（设为 C
），与父亲P 交换
- 大根堆情况：选择 key 值较大的孩子（设为 C
），与父亲P 交换
- （！！！）注意事项：经过此次交换，可能引起交换后父亲结点所在的那个结点（也就是交换前的孩子结点，即为
C ）所在子树不满足堆的定义。此时，要进一步检查 P
和其左右子树的关系，依据条件进行交换操作，直至检查到叶子结点。
堆的插入（利用堆的向上调整）
- 将新结点插入到堆的末端，利用向上调整，使满足堆的定义。
- 向上调整（子和父比较，子向上调整）流程简述
- 从新插入的结点开始循环，依次比较其与其父结点的大小关系
- 若不满足，则交换位置
- 否则，结束循环，当前位置即为新插入结点的满足堆定义的位置。
堆的删除（利用堆的向下调整）
- 交换堆顶元素（即是完全二叉树的根）和堆的最后一个元素（及完全二叉树的最后一个叶子结点）（或者是删除堆顶的元素，用堆的最后一个元素补位）
- 对当前堆（除最后一个元素）进行向下调整（类似堆的建立，但是开始结点和调整范围不同，这里的向下调整的结点范围是从
1 到 n -
1，即是从头向后，进行调整），使满足堆的定义
利用堆的建立、删除理解堆排序
- 初始建堆
- 依次对堆顶元素进行删除操作（选择交换元素，而非删除元素）
- 最终对堆的完全二叉树进行层序遍历，即可得到有序序列。
归并排序
- 仅讨论二路归并
- 首先，将待排序序列分为两两一组，然后使得组内有序；
- 接着，将上述有序组，两两一组，有序合并；
- 重复第二步，直至所有序列合并成一组
解题技巧及重要结论
- 已知希尔排序某一趟排序后的序列，如何确定本次使用的增量？
- 抓住组内有序（从小到大或者从大到小）这个关键点，从间隔为
1
开始依次验证，直至找到满足的最小间隔，即为本趟希尔排序使用的增量。
- 快排的重要性质
- 第 i 趟排序完成时，会有 i
个以上的数出现在它最终将要出现的位置（这个位置就是排序最终结果的位置），即它左边的数都比它小，它右边的数都比它大。（可用于判定某一序列是否是某趟快排后的序列）
- 在含有 n
个关键字的小根堆中，关键字最大的记录可能存储在什么位置？
- 小根堆 +
关键字最大的条件意味着，该记录在堆的叶子节点。
- 而堆是一棵完全二叉树，其叶子结点位置范围为 \([\lfloor\frac{n}{2}\rfloor+1, n]\)
- 在叶子结点位置范围中的点都可能
- 向一个具有 n 个结点的堆中插入一个新元素的时间复杂度为 \(O(log_2n)\) ，删除一个元素的时间复杂度为
\(O(log_2n)\)
- 构建 n 个记录的初始堆，时间复杂度为 \(O(n)\) （对比上条）；对
n 个记录进行堆排序，最坏情况下其时间复杂度为 \(O(nlog_2n)\)
- 初始序列基本有序时，插入排序比较次数较少。
参考资料
- 数据结构（C语言版）.严蔚敏等
- 2020年数据结构考研复习指导.王道论坛