大话数据结构——排序

logo.jpeg

准备：排序用到的结构和函数

先提供一个用于排序用的顺序表结构，此结构也将用于后面要讲的所有排序算法

#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²)

从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对。