一些算法的总结

淩亂°似流年 2023-02-10 15:30 187阅读 0赞

**各种排序算法**

**稳定：直二冒归基**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0_size_16_color_FFFFFF_t_70 1][]

**插入排序（直接插入排序）**：左边都是排好序的，右边的依次和左边的比较，插入到左边合适的位置。

![2020052110024444.png][]

它的基本思想是将一个记录插入到已经排好序的有序表中。当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了

最坏的情况是待排序数组是逆序。

**归并排序（二路归并）**：将序列每相邻两个数字进行归并操作。开始2个一组排好序。再把排好序的这两个和另外两个合成一组排序。

这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。归并排序的算法比较简单。

![2020052110030491.png][]

# **希尔排序** #

一般的初次取序列的一半为[增量][Link 1]，以后每次减半，直到增量为1。是将整个有序序列分割成若干小的子序列分别进行[插入排序][Link 2]。

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

![20200521100324834.png][]

**冒泡排序**依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

## **选择排序** ##

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

## **快速排序** ##

![2020052111445111.jpg][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200528175937744.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521100135986.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0,size_16,color_FFFFFF,t_70
[2020052110024444.png]: https://img-blog.csdnimg.cn/2020052110024444.png
[2020052110030491.png]: https://img-blog.csdnimg.cn/2020052110030491.png
[Link 1]: https://baike.baidu.com/item/%E5%A2%9E%E9%87%8F
[Link 2]: https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
[20200521100324834.png]: https://img-blog.csdnimg.cn/20200521100324834.png
[2020052111445111.jpg]: https://img-blog.csdnimg.cn/2020052111445111.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521115923308.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNzY5OTE0,size_16,color_FFFFFF,t_70