经典排序算法

概述

• 记忆口诀：

  • 插冒归，你很稳，外加一个基(稳定排序)
  • 插冒归，喜欢选冒插，插完就慌了（时间复杂度n^2）
  • 快归堆，是N老（时间复杂度nlogn）

• 概况图：

  

算法

插入排序

• 原理：和**前面的比**，找到对应位置插入

  • 把所有元素分为两组，已经排序的未排序的

  • 找到未排序的组中第一个元素，想已经排序的组中插入

    选择排序是每次找到最小的元素进行操作，而插入是未排序的第一个

  • 具体步骤：

    • 双重遍历，外层从0到结尾，内层从0到i。

    • 每次插入的时候，前面的内容都是已经排序的好的了

    • 如果有重复元素，重复元素需要插入到重复元素的后面

      （后面的元素更少的移动个数，少移动一个）

• 示例图：

  

希尔排序

• 原理：对每一个**子表**进行直接插入排序

  • 步长：

    • 第一趟步长指定为表长/2，奇数向上取整（如果题目没给就自己这么计算）

    • 第二趟步长为第一趟步长除2

      …

    • 每趟步长除以2,直到步长为1进行排序后，就不再进行下一趟了

  • 子表：

    选择i和i+step这两个元素，直到后面的元素到最后一个

  • 每趟结果：步长的元素顺序是确定的

• 示例图

冒泡排序

• 原理：从后两两对比，更小的往前放

  • 每次比较两个，会比较重复的

  • 每趟排序的结果：

    • 从后面两两对比，每次会把最小的元素冒泡在了最前面
    • 从前面两两对比，每次会把最大的元素冒泡在了最后面

    但是每趟结果的中间元素的顺序是改变不了的

• 示例图：

  

快速排序

• 原理：

  

  • 枢轴：

    每趟都是第一个元素开始当枢轴

  • 每趟排序的结果：

    • 第一趟排序：一个枢轴左右元素的值虽然无序，但是左侧均小于枢轴、右侧均大于枢轴

    • 第二趟排序：此时有两个枢轴，进行排序

• 示例图

  

选择排序

• 原理： 选择合适的元素放在合适的位置，交换位置

  • 每次遍历

    第一次排序：选择从0到结尾最小元素，放在第一个，即第一个互换位置

    第二次排序：选择从1到结尾最小的元素，放在第二个，即第二个元素互换位置

  • 每趟便利结果：

    前面的元素是有序的

• 示例图：

  

堆排序

• 原理

  

  • 通常都是大根堆，小根堆比较少

    • 堆：逻辑树结构

    • 大根堆：根结点，大于左右节点的值
    • 小根堆：

    不同于二叉排序树，二叉排序树是左节点、根结点、右节点

  • 步骤：将题目给的数据结构按照层次存储转换为树型结构，再把该数据结构转换为大根堆

    • 找到每一个有孩子的根节点（好像是后序遍历判断）

    • 判断他和他的直接孩子节点是否满足大根堆

      不满足直接调换孩子和父亲的位置，每趟只调换一个根结点和子元素

    • 得到为大根堆后，每次输出最大的元素，（这个元素就不再大根堆中的，然后剩下的元素重新排序为大根堆）

归并排序

• 原理：两有序并为一有序数组

  • 步骤：

    • 遍历方法：

      • 第一次遍历：

        第一次将每一个元素当作单独的有序表

        然后建立另外的表，进行排序为有序表

      • 第二次遍历：

        第一次遍历的结果得到长度为2的有序表，基于这个继续建表、排序。

    • 排序方法：

      从两个表的头依次对比，每次选择二者中较小的移动另外一个空表中，然后移动了的指针移动

• 示例图

  

基数排序

• 原理：

  • 看个位，把个位相同的数字放在一起
  • 看十位，把十位相同的数字放在一起
  • 输出结果就结束了

• 步骤图：

  • 看个位

    

  • 看十位

    

参考

【数据结构】八大排序算法过程详解

【黑马】数据结构与算法之经典排序算法【配套源码+笔记】