排序

本文讲数组的排序，排序复杂度分为O(n²)和O(nlogn)。
其中：O(n²)的算法有：
插入排序：维护已经排好序的部分，插入需要重新维护（交换内部位置）
选择排序：内部循环标记出位置，进行交换，只交换一次。
O(nlogn)的算法有：
归并排序：维护左右两部分分别有序，然后使用merge函数合并为整体有序，需要借助辅助数组空间。
快排：挑选一个元素作为标点，把数组划分为小于和大于的区域；需注意标点的选取（如果取第0个，在有序情况下会退化，栈溢出）；相等元素处理（如果全部相等，算法退化，栈溢出，二路快排，三路快排）

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容