常见的排序算法有哪些？

野性酷女 2023-10-12 21:14 41阅读 0赞

### 常见的排序算法 ###

*  1. 基本概念
 *  2. 冒泡排序（Bubble sort）
 *   *  改进方案
     *   *  改进1：双向扫描
         *  改进2：结束条件
     *  效率分析
 *  3. 快速排序（Quick Sort）
 *  4. 直接插入排序（straight insertion sort）
 *  5. 希尔排序（Shell sort）
 *  6. 简单选择排序
 *  7. 归并排序
 *  8. 基数排序
 *  9. 排序算法的评价指标
 *  10. 常见排序算法的复杂度对比

# 1. 基本概念 #

**排序**：是指将一个无序序列整理成按值递增（或递减）的有序序列。

**排序法分类**：  
**交换类**：借助数据元素之间**交换位置**进行排序。（冒泡排序、**快速**排序）  
**插入类**：将待排序序列的数据元素依次**插入到已排序序列**的适当位置。（直接插入排序、**希尔**排序）  
**选择类**：从无序表中**选出最小的元素**，把它交换到表的最前面；然后对剩下的子表采用相同的方法，直到子表为空为止。（简单选择排序）  
**其他方法：归并排序、基数排序**

# 2. 冒泡排序（Bubble sort） #

**基本思想**：逐个**交换**次序不当的相邻表项，多趟扫描后得到有序表。  
**特点**：冒泡排序也可称为简单交换排序，原理简单。

## 改进方案 ##

### 改进1：双向扫描 ###

鸡尾酒搅拌排序，先从左往右扫描，把最大值移到右边，然后再从右往左扫描，把最小值移到左边。

### 改进2：结束条件 ###

如果一次扫描中没有发生交换，即可结束。

## 效率分析 ##

假设线性表长度为n，则在**最坏情况下**，冒泡排序需要经过n/2遍从前往后的扫描以及n/2遍从后往前的扫描，需要的比较次数为n（n-1）/2，所以时间复杂度为O(n^2)。

**一般情况下**要小于这个工作量。

对于**基本有序**的序列，效率较高。

# 3. 快速排序（Quick Sort） #

**基本思想**：从表中**任意选取一个元素**（一般取第一个、最后一个或中间一个），**把它放在排序表中它应该在的位置**，**把原表分为两个子表**（子表不一定有序），然后对子表**重复以上操作，直至子表长度为1**。

**特点**：快速排序也**属于交换排序**，通常比其他排序方法都**快**；**属于递归排序**，需要较大内存。  
![在这里插入图片描述][d3d63aa72a954dc6a8b9c348010b4bc7.png]  
**快速排序过程演示**（选取最后一个元素作为支点）

**支点数据对性能影响很大**（**最佳情况**为每次取到中间值，**最差情况**为每次取到最大或最小值，因此**对近乎有序的输入序列效果最差**）。

**平均时间性能最好**，最差时相当于冒泡排序。

# 4. 直接插入排序（straight insertion sort） #

**基本思想**：每步将一个待排序序列的元素按其关键字的大小插入到已经排好序的序列中的适当位置，直到全部记录插入完毕为止。

**改进**：插入时，可用二分查找法寻找合适位置，称为“二分查找排序”。

# 5. 希尔排序（Shell sort） #

**是对直接插入排序算法的改进，因Donald Shell于1959年提出而得名。**

**基本思想**：将整个无序序列**分隔**成若干小的**子序列**，

**分隔方法**：

1.  将相隔某个**增量h**的元素构成一个子序列。
2.  在排序过程中，**逐次减小这个增量**，最后当h减到1时，进行一次插入排序，排序就完成。
3.  **增量序列**一般取hk = \[n/2^k\]，(k=1, 2, …, \[log2n\]) 其中n为待排序序列的长度。
4.  例如，n=12时，hk=6，3，1。
5.  **增量序列的选取没有确定的最佳方法**

例如，n=12时，hk=6，3，1。

一开始步长较大，这样可以让一个元素可以一次性地朝最终位置前进一大步。

算法的最后一步就是普通的插入排序，此时**逆序较少，插入排序较快**。

# 6. 简单选择排序 #

**基本思想**：从无序表中选出最小的元素，把它交换到表的最前面，然后对剩下的子表采用相同的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍。

# 7. 归并排序 #

![在这里插入图片描述][62deb30292e548d19a092eb1ad3f297d.png]

# 8. 基数排序 #

1.  **桶排序（Bucket Sort）**：原理很简单，它是将数组分到有限数量的桶里。
2.  **基数排序（Radix Sort）**：是桶排序的扩展，它的基本思想是将整数**按位数切割成不同的数字**，然后后**按每个位数分别比较**。
3.  **举例**：理顺一副牌的过程  
    1）如果有N（N<=13）张牌，乱序，如何理顺呢？  
    2）假想桌上有13个位置，然后我们将手里的牌一张一张放出去，如果是3，就放在位置3上，如果是J，就放在位置11上，放完了之后从位置1到位置13收集所有的牌（没有牌的位置上不收集）。

# 9. 排序算法的评价指标 #

1.  时间复杂度
2.  空间复杂度
3.  **稳定性**（对**相同键码**元素之间**相对位置**的**维持**）
4.  算法简单
5.  待排序记录个数n的大小
6.  记录本身信息量的大小
7.  键码（Key Value）的分布情况

# 10. 常见排序算法的复杂度对比 #

![在这里插入图片描述][6285735dab1d48e79338a20786155b79.png]  
**快堆希不稳定**，快速排序是比较好的，冒泡排序是比较容易编程的。

**参考资料**：[常见的排序算法有哪些？][Link 1]

[d3d63aa72a954dc6a8b9c348010b4bc7.png]: https://img-blog.csdnimg.cn/d3d63aa72a954dc6a8b9c348010b4bc7.png
[62deb30292e548d19a092eb1ad3f297d.png]: https://img-blog.csdnimg.cn/62deb30292e548d19a092eb1ad3f297d.png
[6285735dab1d48e79338a20786155b79.png]: https://img-blog.csdnimg.cn/6285735dab1d48e79338a20786155b79.png
[Link 1]: https://www.bilibili.com/video/BV1X7411K739/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb