cvmachine.com - 申博开户网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:排序-架构总览

排序-架构总览

2019-04-09 08:11:09 来源:www.cvmachine.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.cvmachine.com/a/question/100326.html
Tags: 排序 架构 总览
编辑:申博开户网
  • 上一篇:运维-Linux简介
  • 下一篇:没有了
  • 关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部