- 浏览: 78123 次
- 性别:
- 来自: 南京
最新评论
-
amy929:
你好!我最近在做学mapreduce,可否发一份这个代码给我学 ...
MapReduce框架中矩阵相乘的算法思路及其实现 -
微笑春天:
楼主 你好 花了一晚上的时间看了下你这个算法的实现 说实话 我 ...
MapReduce框架中矩阵相乘的算法思路及其实现 -
gaycolour:
大大,同求完整代码!634677370@qq.com
MapReduce框架中矩阵相乘的算法思路及其实现 -
zarchary-10:
你好,同求完整代码,可否发份zzy07053437@163.c ...
MapReduce框架中矩阵相乘的算法思路及其实现 -
developerinit:
你好,最近也在研究mapreduce矩阵乘法,想看下你这个例子 ...
MapReduce框架中矩阵相乘的算法思路及其实现
一、快速排序的基本思想
完整的代码如下:
设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
①分解:
在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
注意:
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解:
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
希尔排序(Shell Sort)又称为缩小增量排序,输入插入排序算法,是对直接排序算法的一种改进。本文介绍希尔排序算法。
对于插入排序算法来说,如果原来的数据就是有序的,那么数据就不需要移动,而插入排序算法的效率主要消耗在数据的移动中。因此可知:如果数据的本身就是有序的或者本身基本有序,那么效率就会得到提高。
希尔排序的基本思想是:将需要排序的序列划分成为若干个较小的子序列,对子序列进行插入排序,通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率。
在希尔排序中首先解决的是子序列的选择问题。对于子序列的构成不是简单的分段,而是采取相隔某个增量的数据组成一个序列。
增量一般的选择原则是:取上一个增量的一半作为此次序列的划分增量。首次选择序列长度的一半
为增量。
先假如:数组的长度为10,数组元素为:25、19、6、58、34、10、7、98、160、0
整个希尔排序的算法过程如下如所示:
上图是原始数据和第一次选择的增量 d = 5。本次排序的结果如下图:
上图是第一次排序的结果,本次选择增量为 d=2。 本次排序的结果如下图:
当d=1 是进行最后一次排序,本次排序相当于冒泡排序的某一次循环。最终结果如下:
在实际使用过程中,带排序的数据肯定不是只有十个,但是上述是希尔排序的思想。其实希尔排序只是插入排序的一种优化。
C++实现希尔排序的代码如下所示:
直接插入排序(direct Insert Sort)的基本思想是:顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1开始逐渐增大,当子序列的记录个数与顺序表中的记录个数相同时排序完毕。
插入排序虽然在最坏情况下复杂性为O(n2),但是对于小规模输入来说,插入排序法是一个快速的排序法。从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换O(1)。
(2)稳定性:
插入排序是稳定的;因为具有同一值的元素必然插在具有同一值得前一个元素的后面,即相对次序不变。
四、简单选择排序
简单选择排序的基本思想:第i趟简单选择排序是指通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。共需进行i-1趟比较,直到所有记录排序完成为止。例如:进行第i趟选择时,从当前候选记录中选出关键字最小的k号记录,并和第i个记录进行交换。
实现代码如下:
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为:
n(n-1)/2=0(n2)
(2)记录的移动次数
当初始文件为正序时,移动次数为0
文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
直接选择排序的平均时间复杂度为O(n2)。
(3)直接选择排序是一个就地排序
(4)稳定性分析
直接选择排序是不稳定的。
【例】反例[2,2
,1]
五、归并排序
六、堆排序
发表评论
-
不借助其它变量交换两变量值的三种算法
2012-10-16 10:27 1085在学习程序语言和进行程序设计的时候,交换两个变量的值是经常要使 ... -
编程珠玑开篇--磁盘文件排序问题
2012-10-16 10:07 1178转载。。。。 编程珠玑开篇--磁盘文件排序问题 ... -
各种排序算法的稳定性和时间复杂度小结
2012-10-16 09:22 1117各种排序算法的稳定性和时间复杂度小结 冒泡 ... -
求连通图中任意两个顶点的之间的所有路径
2012-03-15 22:08 0问题如图所示: 但是可能存在两种图,一种是DAG图,即深度遍 ... -
最大网络流的算法
2012-03-15 20:11 0网络最大流问题: ... -
HDFS的缺点以及相应的改进策略
2012-03-09 20:24 1284HDFS是一个不错的分布式 ... -
链表逆序输出---关于这一类型的问题
2012-03-08 22:02 0题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链 ... -
求一个数列的最长非递增(递减)子序列
2012-03-09 16:22 8413问题描述: 给出 ... -
BFS与DFS
2012-03-04 18:10 0图深度遍历与广度遍历 ... -
字典树
2012-03-04 14:00 0trie树,即是我们所说的字典树。 典型应用是用于统计和排序 ... -
数列的排列与组合问题
2012-03-03 19:25 2677关于数列的全排列已经另外一篇文章中提到过了, 下面来介 ... -
字符串模式匹配--KMP算法
2012-03-03 09:43 0这个字符串模式匹配的算法在数据结构中可谓是非常的重要,也非常的 ... -
n-皇后以及全排列的问题--递归以及非递归的解法
2012-03-01 09:19 2324首先说下全排序的问题 这个问题可以说是最经典的问题, ... -
外排序学习(1)
2012-02-28 20:52 0首先对应到具体问题, 在网上见到的一个题目, 一个最多含有 ... -
关于链表追赶--链表中环的问题
2012-02-28 15:19 1646关于环的问题, 介绍 ... -
最大连续子数列的和问题
2012-02-28 10:57 0对应最常见的问题: 输入一个整形数组,数组里有正数也有 ... -
亲和数问题--伴随数组的简单应用
2012-02-27 22:30 0原题是求50000以内的所有亲和数;; 亲和数的定义如 ... -
在集合中寻找满足条件的两个或者多个数
2012-02-23 12:27 0对于这个类型的具体问题常见的有如下: 1.输入一个数组和一个 ... -
选取K个最小的数--学习报告
2012-02-22 19:27 0问题描述: 查找最小的k个元素 题目:输入n个整数 ... -
计数排序--小计
2012-02-21 13:48 0void CountingSort(const char *A ...
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
选择排序、插入排序、冒泡排序、希尔排序、快速排序、箱子排序、基数排序、归并排序、堆排序 : 小总结
冒泡排序、选择排序、快速排序、堆排序、插入排序、希尔排序、归并排序 冒泡排序、选择排序、快速排序、堆排序、插入排序、希尔排序、归并排序 冒泡排序、选择排序、快速排序、堆排序、插入排序、希尔排序、归并排序...
printf("\t1: 插入排序\n"); printf("\t2: 冒泡法排序\n"); printf("\t3: 快速排序\n"); printf("\t4: 直接选择排序\n"); printf("\t5: 堆排序\n"); printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); ...
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
10种排序算法代码+综合比较代码(直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序),其中不仅有各种排序算法的代码,还包含10种代码在关键字...
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
用java语言实现冒泡排序、插入排序、堆排序、快速排序、归并排序、希尔排序、桶排序,并且对各种排序算法进行性能的比较。
c++实现的线性表排序算法 插入排序,希尔排序,冒泡排序,快速排序,堆排序,归并排序等