数据结构与算法-七种排序算法

一，排序算法简介

1，排序算法：

    排序算法是一种将一串无规律数据依照特定顺序进行排列的一种方法或思路

2，排序算法的稳定性：

    队列中有相同的元素，排序前后，这两个相同元素的顺序有没有发生变化。

3，常见排序算法：

• 基础：
      冒泡、插入、选择
• 中级：
      快速
• 高级：
      堆、归并
• 其他：
      基数、希尔、桶

二，冒泡排序

1，冒泡排序简介

    冒泡排序是一种简单的排序算法。 相邻的元素两两比较。 经过数次比较循环，最终达到一个从小到大(升序)或者从大到小(降序)的有序序列。由于类似于气泡从水底冒出，所以叫“冒泡”排序。

2，冒泡排序原理

3，冒泡排序实践

4，时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n²)
• 稳定性：稳定

三，选择排序

1，选择排序简介

选择排序（Selection sort）是一种简单直观的排序算法。
简单来说就是从无序队列里面挑选最小的元素，和无序队列头部元素替换(放到有序队列中)，最终全部元素形成一 个有序的队列。

2，选择排序原理

3，最终代码实践

4，时间复杂度

• 最优时间复杂度：O(n²)
• 最坏时间复杂度：O(n²)
• 稳定性：不稳定

四，插入排序

1，插入排序简介

    插入排序也是一种简单的排序算法。
    简单来说，先定义一个有序队列，然后把无序队列中的第一个元素放到有序队列的 合适位置，重复操作，直至形成一个完整的有序队列。
    生活实例： 打扑克

2，插入排序原理

3，最终代码实践

4，时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n²)
• 稳定性：稳定

五，希尔排序

1，希尔排序简介

    希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是插入排序算法的一种高效的改进版本。

2，希尔排序原理：

3，代码实践

4，时间复杂度

• 最优的时间复杂度是 O(nlogn)
• 最坏时间复杂度：O(n2)

我们知道希尔排序的本质就是插入排序，所以最坏也就是插入排序的最坏时间复杂度了，也就是O(n2)

• 稳定性：不稳定

六，快速排序

1，快速排序简介

    快速排序，又称划分交换排序，从无序队列中挑取一个元素，把无序队列分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行， 以此达到整个数据变成有序序列。

2，快速排序原理示意图

    通过上面对快速排序的简介，我们知道了，快速排序主要包括以下两方面：
        挑元素划分组、整体递归分组

1）挑元素划分组示意图：

特点：
1、因为是无序队列，所以位置可以随机挑
2、临时划分一个空间，存放我们挑选出来的中间元素
3、左标签位置空，移动右标签，反之一样
4、重复3，直到左右侧标签指向同一个位置，
5、把临时存放的中间元素，
归位 一句话：左手右手一个慢动作，右手左手慢动作重播

2）整体划分示意图：

特点：
1、递归拆分
2、拆分到最后，所有小组内的元素个数都是1
一句话：递归拆分到不能再拆

3，最终代码实践

4，时间复杂度

• 最优时间复杂度：O(nlogn)

对于每次快排，left和right的标签分别在左右两册数据全部都移动了一遍，相当于遍历了所有数据，那么时 间复杂度是O(n)
因为涉及到了递归分组，所以他的时间复杂度是O(logn) 整体来说：最优的时间复杂度是 O(nlogn)。

• 最坏时间复杂度：O(n²)

因为递归分组分组的条件不一定是二分，有可能每一次mid指定的都是最大或者最小，那么有多少个元素，我们
就可能分多少次组，这种情况时间复杂度就是O(n)了 所以最坏的时间复杂度就是O(n2)，那么最坏也不过如此了。

• 稳定性：不稳定

七，归并排序

1，归并排序简介

归并排序是采用分治法的一个非常典型的应用。 将无序队列拆分成两个小组，组内元素排序，然后组间元素逐个比较，把小元素依次放到新队列中。

2，归并排序原理：

归并排序分为两个阶段：
    分组排序阶段：
        1、将无序队列alist，拆分成两个小组A和B，
        2、分别对两个小组进行同样的冒泡排序
        3、用标签left和right，分别对小组A和B进行管理 合并新队列阶段：
        4、两个标签所在的元素比较大小，
        5、将小的元素放到一个新队列中，然后小元素所在的标签向右移
        6、多次执行4和5，最终肯定有一个小组先为空
        7、把不为空的小组元素，按顺序全部移到新队列的末尾
        8、无序队列中的所有元素就在新队列中形成有序队列了
    特点：
        两个阶段：分组排序+合并
        合并策略：组间比较，新增小，小移标

3，归并排序示意图

4，最终代码实践

5，时间复杂度

• 最优时间复杂度：O(nlogn)

对于每次合并，left和right的标签分别在左右两组数据全部都移动了一遍，相当于遍历了所有数据，那么时
间复杂度是O(n)；对于分组来说，因为他是递归，所以他的时间复杂度是O(logn) 整体来说：最优的时间复杂度是 O(nlogn)

• 最坏时间复杂度：O(nlogn)
  稳定性：稳定

八，堆排序

1，堆简介

    堆是采用顺序表存储的一种完全二叉树的结构。

        父节点和子节点关系：
            父节点位置 i,找子节点：
                左子节点位置：2i + 1 右子节点位置：2i + 2

2，堆分类

• 大顶堆：任一节点都比其孩子节点大
• 小顶堆：任一节点都比其孩子节点小

3，堆排序原理

它是指利用堆这种树结构所设计的一种排序算法。
简单来说，就是将无序列表先构造一个有特点的堆，然后利用列表的特点快速定位最大/小的元素，将其放到一个队列中。
1、根据完全二叉树结构，将无序队列构造成一个大顶堆，
2、将堆顶的根节点移走，与无序列表的末尾元素交换，此时末尾元素就是最大值，相当于进入了一个有序队列。
3、再将剩余的n-1个无序队列重新构造一个同样堆，
4、重复循环1-3步，最终将所有元素都移动到有序队列。
特点：
无序队列构建一个堆，堆顶和堆尾元素替换位置
重新构建堆，堆顶和堆尾元素替换位置，
…
简单来说：头尾替换，恢复堆后再继续

4，堆排序实现步骤

3，成本实践：