vlambda博客
学习文章列表

阅读本文前，请您先点击上面的“蓝色字体”，再点击“关注”，这样您就可以每天学习一点新知识，每天都有进步了。

冒泡排序

一种简单的排序方法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换。

走访数列的工作是重复地进行直到不需要进行交换，也就是说该数列已经排序完成。这个算法的名字由来是因为元素会慢慢“浮”到数列的顶端。

选择排序

选择排序和冒泡类似，可以看作是对冒泡排序的优化。

插入排序

像打麻将一样，把摸到的麻将插入到合适的位置，适合近乎有序的数组。

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素都向后移动一位。

插入排序所需的时间取决于输入元素的初始顺序，例如：对一个很大且元素已经近乎有序的数组经行排序会比随机顺序的数组或是逆序数组进行排序要快得多。

注：插入排序对于部分有序的数组十分高效，也适合小规模数组。

快速排序

快速排序是对冒泡排序的一种改进，也是采用分治法的典型应用。

希尔排序

这是一种基于插入排序的快速排序算法。简单插入对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。

希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是冲破O ( n 2 ) O(n^2)O(n 

2

 )的第一批算法之一。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法；然后缩小增量继续分组，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分为一组，再次排序完成整个数组的排序。这个不断缩小的增量，就构成了一个增量序列。

从理论上说，只要一个数组时递减的，并且最后一个值是1，都可以作为增量序列使用。但目前从数学上来说，无法证明哪个序列是“最好的”，即找不到一组序列使希尔排序时间复杂度最优。

常用的希尔序列：

归并排序

对于给定的一组数据，利用递归与分治技术将数据序列划分为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。

并没有规定只能分为两部分，可以分成多个部分再合并，分为两个部分写起来很简单。

堆排序

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中最大或最小元素，那么就有一种基于二叉堆的数据结果可以提供支持。

所谓二叉堆，是一个完全的二叉树结构，同时满足堆的性质：即子结点的键值或索引总是小于或者大于它的父结点。在一个二叉堆中，根结点总是最大（或最小）结点，这样的堆我们称之为最大（小）堆。

堆排序算法就是抓住了这一特点，每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，最终得到排序的序列。

完全二叉树

计数排序

计数排序是一种排序时不比较元素大小的排序算法。

计数排序对一定范围内的整数排序时速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限定对于整数排序、并且待排序元素值分布比较连续、跨度小的情况。

如果一个数组里所有元素都是整数而且都在0~k以内。那对于数组里每一个元素来说，如果知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

桶排序

桶排序是计数排序的升级版

桶排序的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶在分别排序（可以使用其他的排序算法或者递归调用桶排序）。

基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9的数字组成。基数排序按照从右往左的顺序依次将每一位都当作一次关键字，然后按照该关键字对数组的元素入桶，每一轮入桶都基于上一轮入桶的结果；完成所有位入桶后，整个数组就达到了有序状态。

基数排序也是一种无序比较的算法。

基数排序，计数排序和桶排序都利用了桶的概念，但在桶的使用上有明显的差异

基数排序：根据键值的每位数字来分配桶

计数排序：每个桶只存储单一键值

桶排序：每个桶存储一定范围的数值

总结

--- THE END ---