数据结构-排序(第十章)的整理笔记，若有错误，欢迎指正。
交换排序
- 所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，这里主要介绍冒泡排序和快速排序。
冒泡排序(bubble sort)
- 冒泡排序的基本思想是：从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i-1]>A[i])，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素(或最大元素)放到了序列的最终位置…这样最多做n-1趟冒泡就能把所有元素排好序。
代码实现
void BubbleSort(int a[], int num) //冒泡排序
{
int temp, i, j, flag;
for (i = 0; i < num-1; i++)
{
flag = false; //表示本趟冒泡是否发生交换的标志
for (j = num-1; j >i; j--) //一趟冒泡过程
if (a[j-1] > a[j]) //若为逆序
{
temp = a[j-1]; //交换
a[j-1] = a[j];
a[j] = temp;
flag = true;
}
if (flag == false) return;
//本趟遍历后没有发生交换，说明表已经有序
}
}
运行结果
程序分析
- 冒泡排序的性能分析如下：
- 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
- 时间效率：当初始序列有序时，显然第一趟冒泡后flag依然为false(本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为 O ( n ) O(n) O(n)；当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动元素3次来交换元素位置。这种情况下，比较次数= ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) 2 \sum_{i=1}^{n-1}(n-i)=\frac {n(n-1)}2 ∑i=1n−1(n−i)=2n(n−1)，移动次数= ∑ i = 1 n − 1 3 ( n − i ) = 3 n ( n − 1 ) 2 \sum_{i=1}^{n-1}3(n-i)=\frac {3n(n-1)}2 ∑i=1n−13(n−i)=23n(n−1)。从而，最坏情况下的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，其平均时间复杂度也为 O ( n 2 ) O(n^2) O(n2)。
稳定性：由于i>j且A[i]=A[j]时，不会发生交换，因此冒泡排序是一种稳定的排序方法。
！注意：冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序)，也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。
快速排序(quick sort)
- 快速排序是由冒泡排序改进而得的，它的基本思想是在待排序的n个元中任取一个元素(通常取第一个元素)作为基准，把该元素放入适当位置后，数据序列被此元素划分成两部分。所有关键字比该元素关键字小的元素放置在前一部分，所有比它大的元素放置在后一部分，并把该元素排在这两部分的中间(称为该元素归位)，这个过程称为一趟快速排序，即一趟划分。
- 之后对产生的两个部分分别重复上述过程，直至每部分内只有一个元素或空为止。简而言之，每趟使表的第一个元素放入适当位置，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表的长为1或0。
- 一趟快速排序的划分过程partition(R,s,t)是采用从两头向中间扫描的办法，同时交换与基准元素逆序的元素。具体方法是设两指示器i和j，它们的初值分别为指向无序区中的第一个和最后一个元素。假设无序区中的元素为 R [ s ] ， R [ s + 1 ] ， … ， R [ t ] R[s]，R[s+1]，…，R[t] R[s]，R[s+1]，…，R[t]，则i的初值为s，j的初值为t，首先将R[s]移至变量tmp中作为基准，令j自位置t起向前扫描直至R[j].key<tmp.key时将R[j]移至位置i，然后让i向后扫描直至R[i].key>tmp.key时将R[i]移至位置j，依此重复直至i=j，此时所有 R [ k ] ( k = s ， s + 1 ， … ， i − 1 ) R[k](k=s，s+1，…，i-1) R[k](k=s，s+1，…，i−1)的关键字都小于tmp.key，而所有 R [ k ] ( k = i + 1 ， i + 2 ， … ， t ) R[k](k=i+1，i+2，…，t) R[k](k=i+1，i+2，…，t)的关键字必大于tmp.key，此时再将tmp中的元素移至位置，它将无序区中的元素分割成R[s…i-1]和R[i+1…t]，以便分别进行排序。
- 说明：快速排序每趟仅将一个元素归位。显然，快速排序是一个递归过程，其递归模型如下：
f(R,s,t)≡不做任何事情 当R[s…t]中没有元素或者只有一个元素时
f(R,s,t)≡i=partition(R,s,t)； 其他情况
f(R,s,i-1);
f(R,i+1,t);
代码实现
int Partition(int a[], int low, int high) //一趟划分
{
int pivot = a[low]; //将当前表中第一个元素设为枢轴，对表进行划分
while (low < high) //循环跳出条件
{
while (low<high && a[high]>=pivot) high--;
a[low] = a[high]; //比枢轴小的元素移动到左端
while (low < high && a[low] <= pivot) low++;
a[high] = a[low]; //比枢轴大的元素移动到左端
}
a[low] = pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴的最终位置
}
void QuickSort(int a[], int low,int high) //快速排序
{
if (low < high) //递归跳出的条件
{
int pivotpos = Partition(a, low, high); //划分
QuickSort(a, low, pivotpos - 1); //依次对两个子表进行递归排序
QuickSort(a, pivotpos + 1, high);
}
}
运行结果
程序分析
- 快速排序算法的性能分析如下：
- 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。在快速排序算法中一趟使用辅助变量的个数为常数级，若每一趟排序都将元素序列均匀地分割成两个长度接近的子区间，递归树的高度为 O ( l o g 2 n ) O(log_2^n) O(log2n)，所需栈空间为 O ( l o g 2 n ) O(log_2^n) O(log2n)。但是在最坏情况下递归树的高度为 O ( n ) O(n) O(n)、所需栈空间为 O ( n ) O(n) O(n)，平均情况下所需栈空间为 O ( l o g 2 n ) O(log_2^n) O(log2n)，所以快速排序的空间复杂度为 O ( l o g 2 n ) O(log_2^n) O(log2n)。
-
时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
- 有很多方法可以提高算法的效率：一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。
- 在最理想的状态下，即partition( )可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 n 2 \frac n2 2n，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 O ( l o g 2 n ) O(log_2^n) O(log2n)。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。
- 稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。
- ！注意：在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴(基准)元素放到其最终的位置上。
选择排序
- 选择排序的基本思想是每一趟从待排序的元素中选出关健字最小的元素，顺序放在已排好序的子表的最后，直到全部元素排序完毕。由于选择排序方法每一趟总是从无序区中选出全局最小(或最大)的关键字，所以适合于从大量的元素中选择一部分排序元素。这里介绍两种选择排序方法，即简单选择排序(或称直接选择排序)和堆排序。
简单选择排序(simple selection sort)
- 简单选择排序算法的思想：假设排序表为L[1…N]，第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。
代码实现(顺序表)
void SelectSort(ElemType a[], int num) //简单选择排序
{
int i, j, index;
for (i = 0; i < num - 1; i++) //一共进行n-1趟
{
index = i; //记录最小元素位置
for (j = i + 1; j < num; j++) //在a[i...n-1]中选择最小的元素
if (a[j] < a[index]) index = j; //更新最小元素位置
if (index != i) Swap(a[i], a[index]); //swap函数共移动元素三次
}
}
运行结果
代码实现(带头结点单链表)
void SelectSort(LinkList& L)
{
LNode * r = L, * pre=L, * minpre=L, *p , * q;
int min;
while (r->next != NULL)
{
p = r->next; //从已排序的后一个元素开始遍历
min = p->data; //初始时，将未排序的第一个结点设为最小
pre = r; //初始时，最小元素的前驱结点指向已排序的最后一个元素
q = p; //初始时，q指向未排序的第一个元素
while (p != NULL) //当前处理的结点不为空
{
if (p->data < min) //当前结点的数据域比最小值还小
{
min = p->data; //更新最小值
minpre = pre; //移动最小值的前驱指针minpre
q = p; //q记录最小值的位置
}
else //当前结点的数据域比最小值大
{
pre = pre->next; //前驱指针与当前指针同步后移
p = p->next;
}
}
if (q == r->next) r = r->next;
//如果遍历一趟后发现最小值是未排序中的第一个元素，直接修改已排序好的最后一个元素的指针r
else //如果最小值不是未排序元素中的第一个位置
{
minpre->next = q->next; //将最小值的前驱指针指向最小值的后继
q->next = r->next; //将最小值插入到已排好序元素的最后一个
r->next = q; //修改已排好序元素的最后一个元素的指针r
r = q; //修改指针的指向
}
}
}
运行结果
程序分析
- 时间复杂度：无论初始数据序列的状态如何(顺序、逆序或乱序)，在第i趟排序中选出最小关键字的元素，内for循环需做 n − 1 − ( i + 1 ) + 1 = n − i − 1 n-1-(i+1)+1=n-i-1 n−1−(i+1)+1=n−i−1次比较，因此总的比较次数为 ∑ i = 0 n − 2 n − i − 1 = n ( n − 1 ) 2 = O ( n 2 ) \sum_{i=0}^{n-2}n-i-1=\frac{n(n-1)}2=O(n^2) ∑i=0n−2n−i−1=2n(n−1)=O(n2)。至于元素的移动次数，当初始表为正序时，移动次数为0；当表初态为反序时，每趟排序均要执行交换操作，所以总的移动次数为最大值3(n-1)。然而，无论元素的初始序列如何排列，所需进行的关键字比较相同，因此总的平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
- 空间复杂度：只使用常数级的辅助变量个数，与问题规模n无关，故辅助空间复杂度为O(1)，也就是说它是一个就地排序。
- 稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。因此，简单选择排序是一种不稳定的排序方法。
堆排序
- 堆的定义如下：n个关键字序列L[1…n]称为堆，当且仅当该序列满足：
① L ( i ) ≥ L ( 2 i ) L(i)≥L(2i) L(i)≥L(2i)且 L ( i ) ≥ L ( 2 i + 1 ) L(i)≥L(2i+1) L(i)≥L(2i+1)或
② L ( i ) ≤ L ( 2 i ) L(i)≤L(2i) L(i)≤L(2i)且 L ( i ) ≤ L ( 2 i + 1 ) ( 1 ≤ i ≤ ⌊ n 2 ⌋ ) L(i)≤L(2i+1)(1≤i≤⌊\frac n2⌋) L(i)≤L(2i+1)(1≤i≤⌊2n⌋)
可以将该一维数组视为一棵完全二叉树，满足条件①的堆称为大根堆(大顶堆)，大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。满足条件②的堆称为小根堆(小顶堆)，小根堆的定义刚好相反，根结点是最小元素。 - 堆排序的思路很简单：首先将存放在：[1…n]中的n个元素建成初始堆，由于堆本身的特点(以顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。
- 堆排序的关键是构造初始堆。n个结点的完全二叉树，最后一个结点是第
⌊
n
2
⌋
⌊\frac n2⌋
⌊2n⌋个结点的孩子。对第
⌊
n
2
⌋
⌊\frac n2⌋
⌊2n⌋个结点为根的子树筛选(对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换)，使该子树成为堆。之后向前依次对各结点
(
⌊
n
2
⌋
−
1
(⌊\frac n2⌋-1
(⌊2n⌋−1~
1
)
1)
1)为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。
代码实现
void Swap(ElemType & a, ElemType & b) //元素交换
{
ElemType temp = a;
a = b;
b = temp;
}
void HeadAdjust(ElemType a[],int k, int num)
{
int i, temp;
temp = a[k]; //暂存子树的根结点
{
for (i = 2 * k; i <= num; i = i * 2) //沿关键字较大的子结点向下筛选
{
if (i < num && a[i] < a[i+1]) i++; //取关键字较大的子结点的下标
if (temp >= a[i]) break;//较大子结点与双亲结点进行对比
else
{
a[k] = a[i]; //将左右孩子中较大的值调整到双亲结点上
k = i; //记录该元素的下标
}
}
a[k] = temp; //被筛选结点的值放入最终位置
}
}
void BuildMaxHeap(ElemType a[], int num)
{
for (int i = num / 2; i > 0; i--) HeadAdjust(a, i, num);//从i=[n/2]-1，反复调整堆
}
void HeapSort(ElemType a[], int num) //堆排序
{
BuildMaxHeap(a, num);
for (int i = num; i >1; i--) //n-1趟的建堆和交换过程
{
Swap(a[1], a[i]); //堆顶元素与堆底元素交换
HeadAdjust(a, 1, i - 1); //调整，把剩余的i-1个元素调整成堆
}
}
运行结果
程序分析
- 堆排序算法的性能分析如下：
- 空间效率：仅使用了常数个辅助单元，所以空间复杂度为O(1)。
-
时间效率：堆排序的时间主要由建立初始堆和反复重建堆这两部分的时间构成，它们是通过调用BuildMaxHeap( )和HeadAdjust( )实现的。
对于高度为k的完全二叉树/子树，调用BuildMaxHeap( )算法时，循环最多执行k-1次，所以最多进行2(k-1)次关键字比较，最多进行k+1次元素移动，因此主要以关键字比较来分析时间性能。
n个结点的完全二叉树的高度 h = ⌊ l o g 2 n ⌋ + 1 h=⌊log_2^n⌋+1 h=⌊log2n⌋+1。在建立初始堆时，需要筛选调整的层为h-1~1层，以第i层中某个结点为根的子树的高度为 h − i + 1 h-i+1 h−i+1，并且第i层中最多有 2 i − 1 2^{i-1} 2i−1个结点。设建立初始堆所需要的关键字比较次数最多为C1(n)，有：
C 1 ( n ) = ∑ i = h − 1 1 2 i − 1 × 2 ( h − i + 1 − 1 ) = ∑ i = h − 1 1 2 i × ( h − i ) C_{1(n)}=\sum_{i=h-1}^1 2^{i-1}×2(h-i+1-1)=\sum_{i=h-1}^1 2^i×(h-i) C1(n)=∑i=h−112i−1×2(h−i+1−1)=∑i=h−112i×(h−i)
令 j = h − i j=h-i j=h−i，当 i = h − 1 i=h-1 i=h−1时， j = 1 j=1 j=1；当 i = 1 i=1 i=1时， j = h − 1 j=h-1 j=h−1，所以
C 1 ( n ) = ∑ i = h − 1 1 2 i × ( h − i ) = ∑ j = 1 h − 1 2 h − j × j = 2 h − 1 × 1 + 2 h − 2 × 2 + . . . + 2 1 × ( h − 1 ) = 2 h + 1 − 2 h − 2 < 2 ⌊ l o g 2 n ⌋ + 2 < 4 × 2 l o g 2 n = 4 n C_{1(n)}=\sum_{i=h-1}^1 2^i×(h-i)=\sum_{j=1}^{h-1} 2^{h-j}×j=2^{h-1}×1+2^{h-2}×2+...+2^1×(h-1)=2^{h+1}-2h-2<2^{⌊log_2^n⌋+2}<4×2^{log_2^n}=4n C1(n)=∑i=h−112i×(h−i)=∑j=1h−12h−j×j=2h−1×1+2h−2×2+...+21×(h−1)=2h+1−2h−2<2⌊log2n⌋+2<4×2log2n=4n
因此，建立初始堆总共进行的关键字比较次数不超过4n。类似地，设重建堆中对HeadAdjust( )的n-1次调用所需的比较总次数 C 2 ( n ) C_{2(n)} C2(n)。其中i从n到2，每次对R[1…i-1]的i-1个结点的完全二叉树进行筛选调整，该树的高度为 ⌊ l o g 2 ( i − 1 ) ⌋ + 1 ⌊log_2^{(i-1)}⌋+1 ⌊log2(i−1)⌋+1，所以有 C 2 ( n ) = ∑ i = 2 n 2 × ⌊ l o g 2 i − 1 ⌋ + 1 − 1 = ∑ i = 2 n ⌊ l o g 2 i − 1 ⌋ < 2 n l o g 2 n C_{2(n)}=\sum_{i=2}^n 2×⌊log_2^{i-1}⌋+1-1=\sum_{i=2}^n⌊log_2^{i-1}⌋<2nlog_2^n C2(n)=∑i=2n2×⌊log2i−1⌋+1−1=∑i=2n⌊log2i−1⌋<2nlog2n.这样，堆排序所需的关键字比较的总次数最多 C 1 ( n ) + C 2 ( n ) = 4 n + 2 n l o g 2 n = O ( n l o g 2 n ) C_{1(n)}+C_{2(n)}=4n+2nlog_2^n=O(nlog_2^n) C1(n)+C2(n)=4n+2nlog2n=O(nlog2n)。
综上所述，堆排序的最坏时间复杂度为 O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)。堆排序的平均性能分析较难，但实验研究表明，它较接近最坏性能。实际上，堆排序和简单选择排序算法一样，其时间性能与初始序列的顺序无关，也就是说，堆排序算法的最好、最坏和平均时间复杂度都是 O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)。 - 稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。
- 堆排序适合关键字较多的情况！
堆的插入和删除
- 堆的插入：对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样⼀路“上升”，直到无法继续上升为止。
- 堆的删除：被删除的元素用堆底元素替代，然后让该
元素不断“下坠”，直到无法下坠为止。
代码实现
void Insert(ElemType a[], int &num, ElemType x) //堆的插入
{
int i;
num++; //元素个数+1
a[num] = x; //新元素放到表尾
for (i = num; i > 1; i = i / 2) //与父节点对比
if (a[i] > a[i / 2]) Swap(a[i], a[i / 2]); //若新元素比父节点更小，则将二者互换
}
bool Delete(ElemType a[], int &num, ElemType x) //堆的删除
{
int i, temp;
for (i = 1; i <= num && a[i] != x; i++);
if (i > num) return false; //不存在值为x的元素
else a[i] = a[num]; //被删除的元素用堆底元素替代
num--; //元素个数-1
temp = a[i];
for (int j = 2 * i; j <= num; j *= 2) //让该
元素不断“下坠”
{
if (j < num && a[j] < a[j + 1]) j++;
if (temp >= a[j]) break;
else
{
a[i] = a[j];
i = j;
}
a[i] = temp;
}
return true;
}
运行结果
程序分析
- 向具有n个结点的堆中插入一个新元素的时间复杂度为 O ( l o g 2 n ) O(log_2^n) O(log2n)，删除一个元素的时间复杂度为 O ( l o g 2 n ) O(log_2^n) O(log2n)。