算法快学笔记（十七）：史上最全排序算法总结

曾经终败给现在 2023-06-13 09:20 21阅读 0赞

# 1. 简介 #

本文对常见排序算法进行总结

# 2. 排序算法 #

## 2.1 冒泡排序 ##

该算法比较简单，几乎所有语言涉及到算法时，都会涉及到冒泡算法。

算法思路：

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。  
    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

### 2.2 选择排序 ###

每次选择一个最大(小)的，直到所有元素都被输出。

可参考：https://blog.csdn.net/sun7545526/article/details/85165618

### 2.3 直接插入排序 ###

插入排序的基本方法是：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止

算法思路：

当插入第i(i >= 1)时，前面的V\[0\]，V\[1\]，……，V\[i-1\]已经排好序。这时，用V\[I\]的排序码与V\[i-1\]，V\[i-2\]，…的排序码顺序进行比较，找到插入位置即将V\[i\]插入，原来位置上的元素向后顺移。

以\[21,25,49,25,16,08\]为例，排序过程如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]

在小规模数据集或是基本有序时，该算法效率较高。

### 2.4 希尔排序 ###

先对数据进行预处理，使其基本有序，然后再用直接插入排序算法排序。

详细过程可参考：https://blog.csdn.net/eric\_sunah/article/details/103080731

### 2.5 快速排序 ###

利用“分而治之”的思想对集合进行排序  
可参考：https://blog.csdn.net/sun7545526/article/details/85165742

### 2.6 堆排序 ###

说堆排序前，先说下啥是堆。

堆：堆是满足下列性质的完全二叉树：

*  每个节点都大于或是等于其左右孩子节点的值，称为大顶堆
 *  每个节点都小于或是等于其左右孩子节点的值，称为小顶堆

接下来说下堆是如何做排序的，思路如下（以大顶堆为例）：

1.  根节点是整个堆的最大值，将他移走。
2.  将剩余n-1个节点重新构造成一个堆，再将根节点移走
3.  重复执行1,2。直到没有节点可移动，就生成了有序序列。

该算法有两个需要解决问题：

1.  如何将一个无序序列构建一个堆。
2.  移除根节点后，如何用剩余的节点重建堆。

详细介绍参见：https://blog.csdn.net/eric\_sunah/article/details/103081878

### 2.7 归并排序 ###

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

详细介绍参见：https://blog.csdn.net/eric\_sunah/article/details/103082607

# 3. 总结 #

分类总结：

![在这里插入图片描述][20191115114656361.jpg]

时间复杂度总结：  
![在这里插入图片描述][20191115114638677.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019111511471131.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70
[20191115114656361.jpg]: https://img-blog.csdnimg.cn/20191115114656361.jpg
[20191115114638677.jpg]: https://img-blog.csdnimg.cn/20191115114638677.jpg