anyuan2002.com - vwin网

查找: 您的方位主页 > 网络频道 > 阅览资讯:排序-架构总览

排序-架构总览

2019-04-09 08:11:09 来历:www.anyuan2002.com 【


1.Comparison-based Sorting Algorithms:
BUB - Bubble Sort,
SEL - Selection Sort,
INS - Insertion Sort,
MER - Merge Sort (recursive implementation),
QUI - Quick Sort (recursive implementation),
R-Q - Random Quick Sort (recursive implementation).
2.Not Comparison-based Sorting Algorithms:
COU - Counting Sort,
RAD - Radix Sort


【D&C - Divide and Conquer】
-------------------------------------------

根本的结构——

一. ·比较 与 ·非比较 战略,
二. 迭代与递归完成,
三. 分而治之范式(
四. 最佳/最差/均匀状况时刻复杂性剖析,
五. ·随机算法

----------- 详列

一、
· 运用比较战略
1.冒泡排序
2.挑选排序
3.插入排序
(他们被称为根据比较的比较,由于)

· 运用非比较战略
1.计数排序
2.基数排序
(这些排序算法能够经过不比较数组的项目来比时刻复杂度为Ω(N log N))的根据比较的排序算法的下限更快。)(原文:These sorting algorithms can be faster than the lower bound of comparison-based sorting algorithm of Ω(N log N) by not comparing the items of the array.)


三、
①归并排序(MER)是分而治之(D&C)的排序算法
(归并过程很简略:将当时数组分红两半(假如N是偶数,则将其彻底相等,假如N是奇数,则一遍稍大于一个元素),然后递归地对这两半进行排序。)

②快速排序(QUI)是分而治之(D&C) 的算法
(区分过程:挑选一个项目 p(称为枢轴点)然后将 a[i..j] 的项目分为三部分:a [i..m-1],a [m] 和 a[m + 1..j]。 a [i..m-1](可能为空)包括小于 p 的项目。 a [m] 是枢轴点 p,例如:指数 m 是已排序数组 a 的排序次序中 p 的正确方位。a [m + 1..j](可能为空)包括大于或等于 p 的项目。 然后,递归地对这两部分进行排序。
处理过程:不要惊奇......咱们什么都不做!
假如您将其与归并排序进行比较,您会发现快速排序的 D&C 过程与归并排序彻底相反。)


五、
·随机快速排序(R-Q)归于随机算法
除了履行分区算法之外,它与快速排序相同,它随机挑选 a[i..j] 之间的枢轴,而不是一直挑选 a[i](或 a[i..j]之间的任何其他固定索引)。

 
 

本文地址:http://www.anyuan2002.com/a/question/100326.html
Tags: 排序 架构 总览
修改:vwin网
  • 上一篇:运维-Linux简介
  • 下一篇:没有了
  • 关于咱们 | 联络咱们 | 友情链接 | 网站地图 | Sitemap | App | 回来顶部