图解七大排序算法_算法gap值

目录

 一，排序

 二，稳定性

三，冒泡排序

四，选择排序

五，插入排序

六， 希尔排序(缩小增量排序)

七，归并排序

八，堆排序

九，快速排序

十，排序总结

---

---

 一，排序

排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序(in place sort)。

 二，稳定性

两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

1，3(a)，4，2，6，3(b)，7，3(c) -------->1，2，3(a)，3(b)，3(c)，4，6，7

三，冒泡排序

原理：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

分析时间复杂度与空间复杂度：

冒泡排序属于交换排序，是稳定排序，平均时间复杂度为 O(n²)，空间复杂度为 O(1)。

但是我们常看到冒泡排序的最优时间复杂度是 O(n)，那要如何优化呢？

我们可以用一个  参数记录新一轮的排序中元素是否做过交换，如果没有，说明前面参与比较过的元素已经是正序，那就没必要再从头比较了。代码实现如下：

四，选择排序

每一次从无需区间选出最大值（或最小值）的一个元素，存放在无序区间的最后面（或最前面），直到所有元素排序完成。
 

代码实现：

 优化：双向选择排序

每一次从无序区间找出最大值和最小值，将最小值放到无序区间的最开始位置，最大值放到无序区间的最后位置。

分析时间复杂度与空间复杂度

选择排序是不稳定排序，时间复杂度固定为 O(n²)，因此它不适用于数据规模较大的序列。不过它也有优点，空间复杂度为O(1)，就是不占用额外的内存空间。

五，插入排序

原理：将待排序的数组集合分为两部分，已排序的区间和待排序区间；每一次从无序区间的第一个元素插入有序区间的合适位置，直到整个数组有序。 

刚开始排序时有序区间没有元素，整个数组都为无序区间。

 当已经排序的集合最后元素< 当前无序区间的第一个元素，内层循环直接可以退出。大大的降低了时间，如果出现极端情况（待排序的数组就是一个完全升序的数组)，插入排序就会进化为O(n)的时间复杂度

优化：二分插入排序（提升插入时的效率）

分析时间复杂度与空间复杂度：

插入排序是稳定排序，平均时间复杂度为 O(n²)，空间复杂度为 O(1)。

六， 希尔排序(缩小增量排序)

人们发现数组接近有序时插入排序的效率很高，希尔排序就是对 插入排序的优化；

原理：1.先选定一个整数（gap）将待排序的分成gap组，所有距离为gap的为同一组，对每一个小数组进行插入排序。

2.缩小gap值，一般取gap = gao / 2，重复第一步过程，直至gap = 1（此时数组已经近乎有序）。在进行整个数组的插入排序即可

代码实现：

分析时间复杂度与空间复杂度：

希尔排序是不稳定排序，它的分析是一个复杂的问题，因为它的运行时间依赖于增量序列的选择，它的平均时间复杂度为O(n^1.3)，最好情况是 O(n)，最差情况是 O(n²)。空间复杂度为 O(1)。

七，归并排序

建立在归并操作上的一种排序算法。与快速排序都采用了分治思想

原理：不断将原数组一分为二为两个子数组，直到每个子数组只剩下一个元素；不断合并相邻的两个数组为一个大的子数组，直到合并到整个数组。

 

 示例代码：

 

分析时间复杂度与空间复杂度：

希尔排序是不稳定排序，它的分析是一个复杂的问题，因为它的运行时间依赖于增量序列的选择，它的平均时间复杂度为O(n^1.3)，最好情况是 O(n)，最差情况是 O(n²)。空间复杂度为 O(1)。

八，堆排序

原理：将待排序数组构造为一个最大堆，此时数组中最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就是最大值，调整剩余n-1个元素为一个最大堆，再将根节点与调整后的末尾元素进行交换，直至数组有序。

示例：arr={4,6,8,5,9};

第一步：将无序数组创建为完全二叉树，调整为最大堆。

 

 第二步：将堆顶元素与末尾元素交换，重新调整结构为最大堆结构

 

 第三步：重复执行第二步，直至数组完全有序

 

 代码实现：

  分析时间复杂度与空间复杂度：

堆排序是不稳定排序，适合数据量较大的序列，它的平均时间复杂度为 Ο(nlogn)，空间复杂度为 O(1)。 此外，堆排序仅需一个记录大小供交换用的辅助存储空间。

九，快速排序

核心思想：分区

分区值：默认选择最左侧pivot

原理：从无序区间选择一个值作为分界点pivot开始扫描原集合，将数组中所有小于pivot的元素放在分界点的左侧，大于等于的元素放在分界点的右侧。经过本轮交换，pivot放在了最终的位置，pivot的左侧都是小于pivot的元素，右侧都是大于该值的元素，在两个子区间重复上述过程，知道集合有序。

此时arr[l+1~j] <v ;arr[j+1~i) <=v ; arr[i] 时扫描数组元素的指针

1.若arr[i] >= v: 此时只需要i++，继续处理下一个元素。

2.若arr[i] < v : 需要将arr[i] 放在[l+1~j]区间中，将arr[i] 和 arr[j+1]进行交换； j++； 在i++继续处理下一个元素。

当i扫描完整个数组后，数组的划分情况：

这时只需要交换 arr[l]和arr[j]的位置。交换后 j 的左边全都是 < v的元素；j的右边全都是 > v的元素，元素 v 就落在了最终位置 j 。

 代码实现：

 分析时间复杂度与空间复杂度：

 空间复杂度：递归函数的调次数（nlogn）;

时间复杂度：nlogn

n-为每次分区函数的数组扫描

logn-递归函数的调用次数平均情况下就是一个二叉树的高度；

极端情况：数组为近乎完全有序时，按照最左侧元素进行分区的时候，会造成左右两颗递归树严重不平衡，甚至极端情况下退化为链表，时间复杂度退化从O(logn) 为O(n);

 快速排序的优化：合理的分区点的选择可以避免快速排序性能退化的问题；每次随机选择最左侧，最右侧，中间值中的任意一个作为分区点。

十，排序总结