准备:排序用到的结构和函数
先提供一个用于排序用的顺序表结构,此结构也将用于后面要讲的所有排序算法
#define MAXSIZE 10 // 用于要排序数组个数的最大值,可根据需要修改
typedef struct {
int r[MAXSIZE + 1]; // 用于存储要排序数组,r[0]用作哨兵或者临时变量
int length; // 用于记录顺序表的长度
}SqList;
由于排序最常用到的操作是数组两元素的交换,将其封装为函数
void swap(SqList *L, int i, int j) { // 变换L中数组r的下标为i和j的值
int temp = L->r[I];
L->r[i]=L->r[j];
L->r[j]=L->r[I];
}
一、冒泡排序
冒泡排序(Bubble Sort)是一种交换排序,基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
- 1.1、对顺序表L做交换排序(冒泡排序初级版)
void BulleSort0(SqList *L) {
int i, j;
for (i = 1; i < L->length; i ++) {
for (j = i + 1; j <= L->length; j ++) {
if (L->r[i] > L->r[j]) {
swap(L, i, j); // 交换 L->r[i]于 L->r[j]的值
}
}
}
}
严格意义上说,这不算标准的冒泡排序算法,应为它不满足“两两比较相邻记录”的冒泡排序思想,它更应该是最简单的交换排序而已,这个算法的效率是非常低的
- 1.2、冒泡排序算法
void BulleSort(SqList *L) {
int i, j;
for (i = 1; i < L->length; i ++) {
for (j = L->length - 1; j >= i; j --) { // 注意j是从后向前循环
if (L->r[j] > L->r[j + 1]) { // 若前者大于后者(注意这里与上一算法差异)
swap(L, j, j + 1); // 交换 L->r[j]于 L->r[j + 1]的值
}
}
}
}
- 1.3、冒泡排序优化
试想一下,如果我们待排序的系列是{2, 1, 3, 4, 5, 6, 7, 8, 9},除了第一和第二的关键字需要交换外,别的都是正常的顺序。当 i = 1时,交换完 2 和 1,此时序列已经有序,后面大量的比较还是大大多余了。为此,增加一个标记变量flag来实现这一算法的改进
void BulleSort2(SqList *L) {
int i, j;
BOOL flag = true; // flag 用来作为标记
for (i = 1; i < L->length && flag; i ++) { // 若flag为true则对出循环
flag = false; // 初始为flase
for (j = L->length - 1; j <= i; j --) {
if (L->r[j] > L->r[j + 1]) {
swap(L, j, j); // 交换 L->r[j]于 L->r[j + 1]的值
flag = true; // 如果有数据交换,则flag为true
}
}
}
}
- 1.4、时间复杂度分析
最好的情况:要排序的表本身就是有序的,进行了n-1次比较,没有数据交换,时间复杂度为O(n);
最坏的情况:待排序表是逆序的情况,此时需要比较n(n - 1)/2次,并作等数量级的记录移动,时间复杂度为O(n²)。
二、简单选择排序
简单选择排序法(Simple Selection Sort)就是通过 n-i 次关键字间的比较,从 n-i+1 个记录中选出关键字较小的记录,并和第 i (1 <= i <= n)个记录交换之
void SelectSort(SqList *L) {
int i, j, min;
for (i = 1; i < L->length; i ++) {
min = i; // 将当前下标定义为最小值下标
for (j = i + 1; j <= L->length; j ++) { // 循环之后的数据
if (L->r[min] > L->length) { // 如果有小于当前最小值的关键字
min = j; // 将此关键字的下标赋值给min
}
}
if (i != min) { // 若min不等于i,说明找到最小值,交换
swap(L, i, min); // 交换 L->r[i]于 L->r[min]的值
}
}
}
- 时间复杂度分析
简单选择排序最大的忒单就是 交换移动数据次数相当少 ,节约相应的时间;
分析时间复杂度发现,无论是最好、最差的情况,其比较次数都是一样多;对于交换次数而言,最好的时候交换次数为0,最差的时候,也就是初始降序,交换次数为 n-1 次,总的时间复杂度依然为O(n²);
尽管与冒泡排序同为O(n²),但简单选择排序的性能还是要优于冒泡排序。
三、直接插入排序
直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序列表中,从而得到一个新的、记录数增1的有序表。
void InsertSort(SqList *L) {
int i, j;
for (i = 2; i < L->length - 1; i ++) {
if (L->r[i] < L->r[i - 1]) {
for (j = i - 1; L->r[j] > L->r[0]; j --) {
L->r[j + 1] = L->r[j];
}
L->r[j + 1] = L->r[0];
}
}
}
从空间上来看,它只需要一个记录的辅助空间,因此关键还是看时间复杂度:
最好的情况,要排序的表本来就是有序的,没有移动记录,时间复杂度为O(n);
最坏的情况,要排序的表是逆序的,记录的移动次数也达到最大值 (n + 4)(n - 1) / 2次,所以,时间复杂度为O(n²)。
从这里我们也可看出,同样的 O(n²) 时间复杂度,性能上看
直接排序 > 简单排序 > 冒泡排序
四、希尔排序
// 对顺序表L作希尔排序
void ShellSort(SqList *L) {
int i, j;
int increment = L->length;
do {
increment = increment / 3 + 1; // 增量序列
for (i = increment + 1; i <= L->length; i ++) { // 需将L->[i]插入有序增量子表
if (L->r[i] < L->r[i - increment]) {
L->r[0] = L->r[i]; // 暂存在L->r[0]
for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment) {
L->r[j + increment] = L->r[j]; // 记录后移,查找插入位置
}
L->r[j + increment] = L->r[0]; // 插入
}
}
} while (increment > 1);
}
希尔排序的关键并不是随便分组后各自排序,而是将相隔某个“增量”的记录组成一个子序列,实现跳跃式的移动,使得排序的效率提高。
五、堆排序
堆是具有下列性质的完全二叉树:
- 每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆
- 或者每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆
堆排序的基本思想:
将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末元素交换,此时末尾元素就是最大值),然后将剩余的 n-1 个序列重新构造成一个堆,这样就会得到n个元素中的次大值。如此反复执行,便能得到一个有序序列了。
// 2、已知L->r[s..m]中记录的关键字除L->r[s..m]意外以外均蛮子堆的定义
// 本函数调整L->r[s]的关键字,使L->r[s..m]称为一个大顶堆
void HeapAdjust(SqList *L, int s, int m) {
int temp, j;
temp = L->r[s];
for (j = 2 * s; j <= m; j *= 2) { // 沿关键字较大的孩子结局向下筛选
if (j < m && L->r[j] < L->r[j + 1]) {
++j; // j为关键字中较大的记录的下标
}
if (temp >= L->r[j]) {
break; // rc应插入在位置 s 上
}
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp; // 插入
}
// 1、对顺序表L进行堆排序
void HeapSort(SqList *L) {
int i;
for (i = L->length/2; i > 0; i--) { // 把L中的r构建成一个大顶堆
HeapAdjust(L, i, L->length);
}
for (i = L->length; i > 1; i ++) {
swap(L, 1, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
HeapAdjust(L, 1, i - 1); // 将 L->r[i..r-1] 重新调整为大顶堆
}
}
总体来说,堆排序的时间复杂度为O(nlogn)。由于堆排序堆原始记录的排序状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过冒泡、简单选择、直接插入的O(n²)的时间复杂度了
六、快速排序
快速排序(Quick Sort)的基本思想是:通过一趟排序将待
排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
// 3、变换顺序表 L 中子表的记录,使枢轴记录到位,并返回其所在位置,
// 此时在它之前(后)的记录均不大(小)于它
int Partition(SqList *L, int low, int high) {
int pivotKey;
pivotKey = L->r[low]; // 用子表的第一个记录作枢轴记录
while (low < high) { // 从表的两端交替向中间扫描
while (low < high && L->r[high] >= pivotKey) {
high--;
}
swap(L, low, high); // 将比枢轴记录小的记录交换到底端
while (low < high && L->r[low] <= pivotKey) {
low++;
}
swap(L, low, high); // 将比枢轴记录大的记录交换到高端
}
return low; // 返回枢轴所在位置
}
// 2、对顺序表 L 中的子序列 L->[low..high]作快速排序
void QSort(SqList *L, int low, int high) {
int pivot;
if (low > high) {
pivot = Partition(L, low, high); // 将 L->r[low..high]一分为二,算出枢轴值 pivot
QSort(L, low, pivot - 1); // 对低子表递归排序
QSort(L, pivot + 1, high); // 对高子表递归排序
}
}
// 1、对顺序表L作快速排序
void QuicSort(SqList *L) {
QSort(L, 1, L->length);
}
最优情况下,快速排序算法的时间复杂度为 O(nlogn),最坏情况下时间复杂度为 O(n²),快速排序是一种不稳定的排序算法。
可优化点:
- 优化选取枢轴(三数取中 / 九数取中)
- 优化不必要的筛选条件
- 优化小数组时的排序方法
- 优化递归操作
总结回顾
内排序算法.jpg-
指标对比
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 稳定 |
直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
希尔排序 | O(nlogn) ~ O(n²) | O(n1.3) | O(n²) | O(1) | 不稳定 |
堆排序 | O(n²) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(n²) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(n²) | O(nlogn) | O(n²) | O(logn) ~ O(n) | 不稳定 |
从算法的简单性来看,我们将7种算法分为两类
- 简单算法:冒泡、简单选择、直接插入
- 改进算法:希尔、堆、归并、快速
以下是3种简单排序算法的移动次数比较
排序方法 | 平均情况 | 最好情况 | 最坏情况 |
---|---|---|---|
冒泡排序 | O(n²) | 0 | O(n²) |
简单选择排序 | O(n) | 0 | O(n) |
直接插入排序 | O(n²) | O(n) | O(n²) |
从综合各项指标来说,经过优化的快速排序是性能最好的排序算法,但是不同的场合我们也应该考虑使用不同的算法来应对。
网友评论