数据结构与算法

Chapter8 排序算法

插入排序类

直接插入：选取确定序列后的一个元素，向前寻找插入位置

希尔排序：按照步长，分为多个小组进行直接插入排序

交换排序类

冒泡排序：从前向后冒，一趟确定一个

快速排序：位置待定法，前后指针比较交换，一趟确定一个

选择排序类

简单选择排序：

    在待查找序列中选择最小的值，放入已确定序列末尾，一趟确定一个

堆排序：

    大顶堆：每个节点的值都 大于 或等于其子节点的值，用于升序排列
    小顶堆：每个节点的值都 小于 或等于其子节点的值，用于降序排列

    1构建二叉树堆
    2按照大/小顶堆规律，从最底层最小子树开始，向上传递子树内最大/小值
    3最底层完成后，最底层子树规模扩大一层，再向上一层传递子树内最大/小值
    4传递后应该再调整小一层规模的子树，确保每个节点大于孩子
    5循环至整个二叉树层全包含，并且向下调整完成

归并排序

分而治之，大序列分小序列排序，排序后小序列间进行排序，组成大序列，循环

基数排序

不需要比较的排序。适合大数据量
排序思想：根据数字的个位进行排序，再根据数字十位排序，百位排序，以此类推

排序算法的时间复杂度，空间复杂度