你们好,最近小元发现有诸多的小伙伴们对于中国农历年份排序方法,排序方法这个问题都颇为感兴趣的,今天小活为大家梳理了下,一起往下看看吧。
1、 插入排序
2、 插入排序是最简单、最直观的排序算法。它的工作原理是建立一个有序序列,在排序后的序列中从后向前扫描无序数据,找到对应的位置并插入。
3、 算法步骤:
4、 1)将待排序第一序列的第一个元素视为有序序列,将第二个元素至最后一个元素视为未排序序列。
5、 2)从头到尾扫描无序序列,将每个扫描的元素插入有序序列的适当位置。(如果要插入的元素等于有序序列中的一个元素,则要插入的元素被插入到等于的元素之后。)
6、 谢尔分类
7、 Hill排序,也称为递减增量排序算法,是插入排序的一个更高效的改进版本。但是Hill排序是一种不稳定的排序算法。
8、 Hill排序的开始是基于插入排序的以下两个性质,并提出了一种改进的方法:
9、 在对几乎排序的数据进行操作时,插入排序是高效的,即可以达到线性排序的效率。
10、 但是插入排序通常效率很低,因为插入排序一次只能移动一位数据。
11、 Hill排序的基本思想是:首先将待排序的整个记录序列分成若干子序列进行直接插入排序,当整个序列中的记录“基本有序”时,再直接依次插入排序所有记录。
12、 算法步骤:
13、 1)选择一个增量序列t1,t2,tk,其中titj,tk=1;
14、 2)按照增量序列的数量k对序列进行k次排序;
15、 3)每遍排序:根据对应的增量ti,将待排序的列分成若干个长度为m的子序列,直接插入每个子表进行排序。只有当增量因子为1时,才把整个序列当作一个表,表的长度就是整个序列的长度。
16、 选择排序法
17、 选择排序也是一种简单直观的排序算法。
18、 算法步骤:
19、 1)首先,在无序序列中找到最小(最大)的元素,并将其存储在有序序列的开头。
20、 2)继续从剩余的未排序元素中寻找最小(最大)的元素,然后放在排序后序列的末尾。
21、 3)重复第二步,直到所有元素都排序完毕。
22、 冒泡排序
23、 冒泡排序也是一种简单直观的排序算法。它反复访问要排序的系列,一次比较两个元素,如果它们的顺序错了,就交换它们。访问系列的工作重复进行,直到不需要交换为止。
24、 换句话说,该系列已被排序。这种算法的名字来源于较小的元素会通过交换慢慢“浮”到序列的顶端。
25、 算法步骤:
26、 1)比较相邻元素。如果第一个比第二个大,就把它们换了。
27、 2)对每对相邻的元素做同样的工作,从开头的第一对到结尾的最后一对。这一步完成后,最后一个元素将是最大的数字。
28、 3)对除最后一个元素之外的所有元素重复上述步骤。
29、 4)每次对越来越少的元素继续重复上述步骤,直到没有要比较的数字对。
30、 合并分类
31、 归并排序是一种基于归并操作的有效排序算法。这个算法是分而治之的一个非常典型的应用。
32、 算法步骤:
33、 申请一个空间,该空间是两个排序序列的和,该空间用于存储合并后的序列。
34、 设定两个指针,最初位置分别为两个已经排序序列的起始位置
35、 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
36、 重复步骤3直到某一指针达到序列尾
37、 将另一序列剩下的所有元素直接复制到合并序列尾
38、 快速排序
39、 快速排序是由东尼霍尔所发展的一种排序算法。在平均状况下,排序n 个项目要(n log n)次比较。在最坏状况下则需要(n2)次比较,但这种状况并不常见。事实上,
40、 快速排序通常明显比其他(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
41、 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
42、 算法步骤:
43、 1 从数列中挑出一个元素,称为“基准”(pivot),
44、 2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。
45、 这个称为分区(partition)操作。
46、 3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
47、 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
48、 堆排序
49、 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
50、 堆排序的平均时间复杂度为(nlogn) 。
51、 算法步骤:
52、 1)创建一个堆H[0.n-1]
53、 2)把堆首(最大值)和堆尾互换
54、 3)把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
55、 4) 重复步骤2,直到堆的尺寸为1
56、 基数排序
57、 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
58、 说基数排序之前,我们简单介绍桶排序:
59、 算法思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,
60、 桶排序使用线性时间((n))。但桶排序并不是比较排序,他不受到O(n log n) 下限的影响。简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。
61、 例如要对大小为[1.1000]范围内的n个整数A[1.n]排序
62、 首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1.10]的整数,集合B[2]存储(10.20]的整数,……集合B[i]存储( (i-1)*10, i*10]的整数,
63、 i=1,2,100。总共有100个桶。
64、 然后,对A[1.n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任何排序法都可以。
65、 最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这样就得到所有数字排好序的一个序列了。
66、 假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果
67、 对每个桶中的数字采用快速排序,那么整个算法的复杂度是
68、 O(n + m * n/m*log(n/m))=O(n + nlogn nlogm)
69、 从上式看出,当m接近n的时候,桶排序复杂度接近O(n)
70、 当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。
71、 前面说的几大排序算法,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:
72、 1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。
73、 2)其次待排序的元素都要在一定的范围内等等。
74、 各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结如下图所示:
75、 关于时间复杂度:
76、 (1)平方阶(O(n^2))排序各类简单排序:直接插入、直接选择和冒泡排序;
77、 (2)线性对数阶(O(nlog2n))排序快速排序、堆排序和归并排序;(3)O(n^(1+))排序,是介于0和1之间的常数。希尔排序(4)线性阶(O(n))排序基数排序,此外还有桶、箱排序。
78、 关于稳定性:
79、 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序
80、 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序
以上就是排序方法这篇文章的一些介绍,希望对大家有所帮助。
115文库 » 中国农历年份排序方法(排序方法)
免责声明:本文由网友提供互联网分享,不代表本网的观点和立场;专业问题请咨询专业人士,如有侵权请联系客服删除。