数据结构几大排序算法总结（实现、复杂度）_数据结构排序算法时间复杂度总结

---

简介

        排序在数据结构中的内部排序部分，主要介绍了几大常见的排序算法，这里做一下简单的分析总结。

        排序： 按关键字大小顺序排列数据。
        时间复杂度： 简单的排序方法 O($n^2$)，先进的排序方法 O(nlogn)
        排序方法的稳定性： 稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序。

---

冒泡排序，

        规则：“依次比较相邻元素，‘逆序’则交换。
        冒泡排序(52， 49， 80， 36， 14， 58， 61)。

下面是第一趟排序后的结果，确定了最大值80。

        由于两个相同元素比较时如（49,49）由于两值相同，不做交换，故冒泡排序是稳定的。时间复杂度 O($n^2$)

---

快速排序

        快速排序可以看我的另一篇文章讲的很详细快速排序（详解及python实现）
        时间复杂度：平均情况下，时间复杂度 O(nlogn)。 记录本来有序时为最坏情况，时间复杂度为 O(n2)。
        空间复杂度：(考虑递归调用的最大深度)在平均情况下为 O(logn)，在最坏情况下为O(n)。

---

简单选择排序

        规则： 第 i 趟排序过程是在剩余的待排记录中选一个最小（大）的，放在第 i 个位置。即“在待排记录中选取最小的，交换到合适位置，重复n-1 次”
        例： {52 49 80 36 14 58 61}简单选择排序。
        第一趟遍历，找到最小值14，放在第一个位置（与52交换）

        第二趟遍历，固定第一个位置值14不再参与遍历，找到最小值36，放在第一个位置（与49交换）
        第三趟遍历，固定前两个位置值14、36不再参与遍历，找到最小值49，放在第一个位置（与80交换）

        以此类推，直到剩下最后一个元素，排序完成：

        选择排序是不稳定的：
        如（$5_1$ ， $8$， $5_2$， $2$， $9$ ）–> （$2$，$8$， $5_2$， $5_1$ ， $9$）
        时间复杂度 O(n2)，耗费在比较记录上，比较次数始终为 n(n-1)/2，

---

堆排序

        堆： 用数组实现的二叉树（一种非线性结构）,所以它没有使用父指针或者子指针
        小顶堆： 每个结点的值都大于或等于其左右孩子结点的值
        大顶堆： 每个结点的值都小于或等于其左右孩子结点的值

        例：把(24,85,47,53,30,91,12,36)调整成小顶堆。

堆和普通树的区别：
        内存： 普通树要为节点对象以及左/右子节点指针分配额外的内存。堆仅仅使用数组且不使用指针。
        平衡：
        二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(nlog2n)。可以按任意顺序位置插入/删除数据。
        堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(nlog2n) 的性能。
        搜索：
        二叉树中搜索会很快。堆中搜索会很慢，在使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

        规则： 对于一个无序序列如何进行堆排序？

1. 先建立大顶堆
2. 然后交换堆顶与最后一个元素
3. 对剩下的序列继续建立大顶堆，重复以上操作，直到剩下最后一个元素
   

        例： (24,85,47,53,30,91,12,36)进行堆排序。

堆排序是不稳定的。时间复杂度是 O(nlogn)。

---

归并排序

        规则： 两个或多个有序表合并成一个有序表。

        例：对{24, 85, 47, 53, 30, 91}归并排序。

        时间复杂度 O(nlogn)。空间复杂度 O(n)。归并排序是稳定的排序。

---

插入排序

1 直接插入排序

        将待排序记录插入已排好的记录中，不断扩大有序序列，即“将待排序记录插入有序序列，重复n-1 次”。
        以第一个元素不动，对后面的元素一一进行插入。再对后面的序列重复以上操作，直到所有元素插完。

        例： 52， 49， 80， 36， 14， 58， 61 进行直接插入排序。

        算法的时间复杂度 O($n^2$)。直接插入排序是稳定的排序算法。

2 希尔排序（缩小增量排序）

        规则： 先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。

步骤：

1. 分成子序列(按照增量 dk)；
2. 对子序列排序(直接插入排序)；
3. 缩小增量，重复以上步骤，直到增量 dk=1。4.
           增量，即从 gap=length/2 逐步减半，增量序列中最后一个增量一定是 1，如： … 9, 5, 3, 2, 1 和… 13, 4, 1。如没有明确说明增量序列可以选择… 3, 2, 1 或… 5, 3, 2, 1。

        例：希尔排序(52， 49， 80， 36， 14， 58， 61)。

        希尔排序是不稳定的。时间复杂度大约为 O(n3/2)。

3 折半插入排序

        规则： 在直接插入排序中，查找插入位置时采用折半查找的方法。
        时间复杂度 O( $n^2$)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算
法。

总结