微信号:programmer_club

介绍:程序员第一自媒体,与你探讨码农人生路上遇到的各类泛技术话题,定期为你推荐码农人生思考、感悟以及启迪!

程序员必须知道的10大基础实用算法及其讲解

2017-01-30 21:25 小猿很倾城


算法一:快速排序算法


快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。


快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。


算法步骤:


1 从数列中挑出一个元素,称为 “基准”(pivot),


2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。


3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。


递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。




算法二:堆排序算法


堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。


堆排序的平均时间复杂度为Ο(nlogn) 。


算法步骤:


创建一个堆H[0..n-1]

把堆首(最大值)和堆尾互换

3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置


4. 重复步骤2,直到堆的尺寸为1



算法三:归并排序


归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。