排序算法相当重要，它和查找算法一起作为整个算法体系的基石
对用例来说，处理一组有序数据总要比处理一组无序数据容易得多。
比如要在数组中查找特定元素，如果数组是整体有序的，查找会非常轻松(经典的二分查找算法就要求数据集的是整体有序的，其运行的平均时间复杂度仅为 O(log n))，不然用例恐怕只得遍历一遍数组了！
自人类步入信息时代， 近几十年来，生产的信息已超过过去5000年的总和。而信息通过数据存储和传输。如此巨量的数据如果不经过有序性的组织，而全以杂乱无章存在，那必然会大大增加人类社会的复杂性，让处理很多问题变得不可能。有了之前聊到的诸多排序算法存在，才得以让人类社会以更加简单的方式运行。
有强迫症的同学会非常乐于将物品按照某种顺序组织好，以便后续取用；字典中将文字按照字母顺序印刷，再结合编撰好的索引，我们就能快速从中找到待查文字；搜索引擎返回的结果将网页按照与关键词的相关程度排序；Windows 系统的资源管理器、各种花名册，甚至于我们参加集体活动时需要列队都是按照身高排列……
排序的应用是如此广泛，结合计算机，排序算法又是如此的重要！有序性总会使待解决的问题更容易解决，所以排序经常作为待解决问题的一个子问题存在。想象一下，对比杂乱无序的一组数据，你是不是更乐于处理整洁有序的一组数据？
前面七篇文章我们依次聊了——冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序和快速排序这几种主要的排序算法，来列张表对比总结下：
| 排序算法 | 稳定性 | 原地排序 | 时间复杂度 | 空间复杂度 | 补充说明 |
|---|---|---|---|---|---|
| 冒泡排序 | Y | Y | 平均 O(n^2) | O(1) | 最简单的排序算法 |
| 选择排序 | N | Y | 平均 O(n^2) | O(1) | 运行时间输入无关 |
| 插入排序 | Y | Y | 平均 O(n^2) | O(1) | 运行时间严重依赖输入，待排序数组如果已经整体有序，则只需线性级别的时间复杂度 |
| 希尔排序 | N | Y | 最坏 О(n log²n)；最佳O(n) | O(1) | 改进版插入排序 |
| 堆排序 | N | Y | 恒为 O(n log n) | O(1) | 依赖于二叉堆这种数据结构 |
| 归并排序 | Y | N | 恒为 O(n log n) | O(n) | 应用广泛，需要额外辅助空间 |
| 快速排序 | N | Y | 平均 O(n log n) | 依赖于具体实现 | 应用最广泛的排序算法，运行效率由概率保证 |
排序算法的稳定性是指算法是否会保持数组中键值相同元素的相对顺序不变。
快速排序是当下最快的通用排序算法。
如上所述，排序算法相当重要，它和查找算法一起作为整个算法体系的基石。OK下篇文章，我们开始聊查找~
完。
网友评论