排序算法的总结
墨初 知识笔记 53阅读
什么是排序算法？
答：我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。 一种是 比较排序 ，时间复杂度O (nlogn) ~ O (n^2)，主要有： 冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
什么是排序算法的稳定性问题？
答：另外在说一下关于排序算法的 稳定性问题 : 排序算法稳定性的简单形式化定义为：如果 arr [i] = arr [j] ，排序前 arr [i] 在 arr [j] 之前，排序后 arr [i] 还在 arr [j] 之前，则称这种排序算法是稳定的。 通俗地讲就是保证排序前后两个相等的数的相对顺序不变。 （ 可以通过自定义比较函数来去除稳定性问题 ） 举例：对于冒泡排序，原本是稳定的排序算法，如果将记录交换的条件改成 arr [i] >= arr [i + 1] ，则两个相等的记录就会交换位置，从而变成不稳定的排序算法。 进行 n-1 次排序。
什么是归并排序？
答：归并排序除了可以对数组进行排序，还可以高效的求出数组小和（即单调和）以及数组中的逆序对，详见这篇 博文 。 堆排序是指利用堆这种数据结构所设计的一种选择排序算法。 堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
什么是计数排序？
答：计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。 网络中很多博文写的桶排序实际上都是计数排序，并非标准的桶排序，要注意辨别。 我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。