数据结构与算法--交换排序与归并排序

---

回顾

• 排序的基本概念，包括稳定排序与不稳定排序。
• 直接插入排序和简单选择排序方法。
• 通过待排序和排序后的关键字序列，判断使用的排序方法（例如冒泡排序）。

提要

• 交换排序：冒泡排序、快速排序。
• 归并排序：二路归并排序。
• 各种内排序算法的讨论。

冒泡排序

• 通过相邻记录的比较和交换，将无序区关键字最小的记录逐步交换到无序区的第一位，加入到有序区。
• 如果一趟排序没有发生交换，则排序结束。
• 

冒泡排序的过程

• 通过示例展示冒泡排序的初始状态和每一趟排序后的结果。
• 

冒泡排序的实现

void BubbleSort(ElemType L[], int n) {int i, j;bool exchange;ElemType tmp;for (i = 0; i < n - 1; i++) {exchange = false;for (j = n - 1; j > i; j--) {if (L[j] < L[j - 1]) {tmp = L[j];L[j] = L[j-1];L[j-1] = tmp;exchange = true;}}if (exchange == false) return;}
}

冒泡排序算法评价

• 时间复杂度：O(n²)。
• 空间复杂度：O(1)。
• 是稳定的排序算法。
• 

快速排序

• 通过选择枢轴元素，将序列分为两个子序列，递归地对子序列进行排序。
• 

快速排序的划分方法

• 选择序列第一个元素作为枢轴，通过low和high指针移动，将序列分为两部分。
• 每趟排序，使一个元素放入其最终位置，这个元素称为枢轴(pivot)，通常选序列的第一个元素。
• 枢轴把整个序列划分为两个子序列。利用递归，分别对子序列重复相同过程，直至子序列长度为0或1为止。
• 

快速排序的过程

• 通过示例展示快速排序的初始状态和划分过程。
• 
• 

快速排序的实现

void QuickSort(ElemType L[], int s, int e) {int low = s, high = e;ElemType x = L[s];while (low < high) {while (low < high && L[high] >= x) high--;L[low] = L[high];while (low < high && L[low] < x) low++;L[high] = L[low];}L[low] = x;if (s < low - 1) QuickSort(L, s, low-1);if (high + 1 < e) QuickSort(L, high+1, e);
}

快速排序算法性能分析

• 时间复杂度：最好情况O(nlog2n)，最坏情况O(n²)。
• 空间复杂度：最坏情况O(n)，一般情况O(log2n)。

快速排序的改进

• 选择两个轴把序列划分为三个子序列，以避免最坏情况。
• 

归并排序

• 将两个或多个有序序列合并为一个新的有序序列的过程。
• 最简单的归并排序是
  将两个有序序列合并为一个有序序列的过程，称为二路归并排序。

二路归并排序

• 将长度为n的无序序列分成n个长度为1的有序子序列，逐步归并。
  

合并两个有序表

• 描述了如何将两个有序序列合并为一个新的有序序列。
• 

归并排序示例

• 通过具体序列展示二路归并排序的每一趟结果。
  

归并排序算法性能分析

• 时间复杂度：O(nlog2n)。
• 空间复杂度：O(n)。

各种内排序方法的比较

• 将排序方法按平均时间分为三类：平方阶排序、线性对数阶排序、线性阶排序。
• 平方阶O(n2)排序：一般称为简单排序，如直接插入、简单选择和冒泡排序；
• 线性对数阶O(nlog2n)排序：如快速、堆和归并排序；
• 线性阶O(n)排序：如基数排序。

各种内排序算法的特点

• 对比不同排序方法的时间复杂度、空间复杂度、稳定性。
  

总结

• 介绍了直接插入排序、简单选择排序、快速排序、二路归并排序的思想和排序过程。
• 展示了快速排序的一次划分过程。
• 提供了前三种排序的算法实现。

---