美文网首页简书首页
大话数据结构——排序

大话数据结构——排序

作者: 强子ly | 来源:发表于2019-05-02 14:27 被阅读2次
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时,交换完 21,此时序列已经有序,后面大量的比较还是大大多余了。为此,增加一个标记变量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²)

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

相关文章

  • 大话数据结构——排序

    准备:排序用到的结构和函数 先提供一个用于排序用的顺序表结构,此结构也将用于后面要讲的所有排序算法 由于排序最常用...

  • JS数据结构学习之排序

    在看<<大话数据结构>>这本书中关于排序这一章的时候,我试着用javascript语言来重写里面几个经典的排序方法...

  • 浅谈排序的终结者-快速排序算法

    真正的才智是刚毅的志向。 序言 快速排序算法是大话数据结构的算法模块最后的一块,也是排序算法中最重要的算法,没有之...

  • 3月24-4月7

    大话数据结构 大话设计模式 epoll select poll

  • 要看的书籍或视频——Java后端

    书单: 算法与数据结构: 数据结构(严蔚敏)/大话数据结构 //如果觉得教材无聊就可以看大话系列,印象...

  • 《大话数据结构》笔记二(排序)

    1 冒泡排序(优化)2 选择排序3 直接插入排序4 希尔排序5 堆排序6 归并排序(优化)7 快速排序(优化) 1...

  • 排序算法-堆排序

    参考: Java排序算法(五):堆排序 【算法与数据结构】图说堆排序 【数据结构】排序算法:希尔、归并、快速、堆排...

  • 2019-02-23 普林斯顿大学 数据结构课程笔记

    一、 数据结构:基本数据结构:栈、队列、背包、优先队列 排序:排序、归并排序、堆排序、基数排序 查找:二叉查找树、...

  • (转)排序算法

    排序算法点这里 数据结构与算法——计数排序、桶排序、基数排序

  • [记录]我的数据结构学习路径

    书单 《学习JavaScript数据结构与算法》《大话数据结构》《算法图解》《剑指offer》 代码

网友评论

    本文标题:大话数据结构——排序

    本文链接:https://www.haomeiwen.com/subject/odgjgqtx.html