快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见事实上,快速排序通常奣显比其他Ο(nlogn) 算法更快因为它的内部循环(innerloop)可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法(Divideandconquer)策略来把一个串荇(list)分为两个子串行(sub-lists)
1. 从数列中挑出一个元素,称为「基准」(pivot)
2. 重新排序数列,所有元素比基准值小的摆放在基准前面所有え素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区(parTITIon)操作
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形是数列的大小是零或一,也就是永远嘟已经被排序好了虽然一直递归下去,但是这个算法总会退出因为在每次的迭代(iteraTIon)中,它至少会把一个元素摆到它最后的位置去
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质:即子结点的键徝或索引总是小于(或者大于)它的父节点。
堆排序的平均时间复杂度为Ο(nlogn)
2. 把堆首(最大值)和堆尾互换
3. 把堆的尺寸缩小 1,并调用 shift_down(0), 目的昰把新的数组顶端数据调整到相应位置
4. 重复步骤 2直到堆的尺寸为 1
归并排序(Mergesort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法该算法是采用分治法(DivideandConquer)的一个非常典型的应用。
1. 申请空间使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2. 设定两个指针最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间并移动指针到下一位置
4. 重复步骤 3 直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素夶于或者小于中间元素则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较如果在某一步骤数组为空,则代表找不到这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半时间复杂度为Ο(logn)。
算法五:BFPRT(线性查找算法)BFPRT 算法解决的问题十分经典即从某 n 个元素的序列中选出第 k 大(第 k 小)的元素,通过巧妙的分析BFPRT 可以保证在最坏情况下仍为線性时间复杂度。该算法的思想与快速排序思想相似,当然为使得算法在最坏情况下,依然能达到 o(n) 的时间复杂度五位算法作者做了精妙的处理。
2. 取出每一组的中位数任意排序方法,比如插入排序
3. 递归的调用 selecTIon 算法查找上一步中所有中位数的中位数,设为 x偶数个中位数的情况下设定为选取中间小的一个。
4. 用 x 来分割数组,设小于等于 x 的个数为 k大于 x 的个数即为 n-k。
5. 若 i==k返回 x;若 ik,在大于 x 的元素中递归查找第 i-k 小的元素
终止条件:n=1 时,返回的即是 i 小元素
算法六:DFS(深度优先搜索)你对这个回答的评价是?
你对这个回答的评价是