社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
排序算法的目标:将所有元素的主键,按某种方式排列。
一般排序,声明一个比较方法,和一个交换方法。将数据操作限制,增强可读性和可移植性。
算法性能:各个排序算法在不同的随机输入下的基本操作次数(比较,交换,读写数组次数)。
额外的内存使用:排序算法的额外内存开销和运行时间是同等重要的。
排序算法可根据额外内存分为两类,1.除去函数调用需要的栈,和固定的实例变量。不需要额外提供内存, 的原地排序算法。 2.需要额外内存空间存储另一份数组副本。的其他排序算法。
对于比较,如果v和w无法比较,或者有一个为null,则抛异常。还需要实现一个完整的比较排序规则。
1.自反性,对于所有的v,v=v
2.反对称性,对于所有的v<w都有v>w,当v=w时w=v
3.传递性,对于所以的v、w、x,如果v<=w且w<=x 则v<=x
1.先找到数组中最小的那个元素。将它和数组第一个元素交换位置。(若第一个就是最小,自身交换)
2.在剩下的元素中找到最小的元素,将它和第二个元素交换。反复
此算法不断的选择剩余元素的最小者。
此算法,内循环只是比较当前元素与目标已知的最小元素,交换元素在循环代码之外。每次交换都可以确定一个元素位置。交换总次数是N。所以算法效率取决于比较次数。
运行时间和输入无关。为找出最小元素而去扫描一遍数组,并不能为下次遍历提供信息。使用该排序会发现,一个已经有序的数组或者全部相等的数组,和一个随机的 遍历时间一样长。
数据移动最少。每次交换会改变两个元素的位置,进行N次交换。交换次数和数组大小是线性关系。
插入排序
将一个元素插入到其他,已经有序的牌中的适当位置。为了给插入元素腾空间,需要将其余元素在插入之前整体右移一位。
它所需的时间取决于输入元素的顺序。对于有序的数组要比 随机,或者逆序数组排序快的多。
可以想到,如果数组已经有序。那么插入排序会发现,每个元素都已经在合适的位置,运行时间也是线性的。
当,倒置对数,小于数组大小的某个倍数,就是部分有序。当倒置数量很少时,建议使用插入排序。
插入排序与选择排序的比较
插入排序,不会访问已经排好序的右侧元素。(不会移动比插入元素小的元素) 选择排序,不会访问已经排好序的左侧元素。
希尔排序
基于插入排序的 快速的 排序算法。
对于大规模乱序数组插入排序是很慢的。如果最小的主键元素正好在尽头,将最小的放在最前面,需要将后面的元素全部移动N-1次。 为了解决这一问题,加快排序速度,改进了插入排序。
交换不相邻的元素,对数组的局部进行排序,最终用插入排序 将局部有序的 数组 进行排序。
任意间隔为h元素的,都是有序的。实现方法1.每个子数组,进行独立的排序 2.子数组中,将每个元素交换到比它大的元素之前。
高效在于,各个子数组都很短,排序后,子数组都是部分有序。
会比插入排序和选择快很多,数组越大优势越大。
有经验的程序员,一般选择希尔排序,因为对于中等大小的数组它的运行时间可以接受。代码量少,不需要使用额外的内存空间。随后再考虑其他更值得的算法。
归并排序
归并:将两个有序的数组,归并成一个更大的有序数组。
而归并排序,将一个数组排序,先(递归的)将它分成两半分别排序,然后将结果归并起来。
最吸引人的性质:可以保证将任意长度为N的数组排序所需时间 和 NlogN成正比。
缺点就是,需要的额外控件 和 N成正比
1. 将两种不同的有序数组归并到第三个数组中。如果进行多次归并,每次归并创建一个新数组存在问题。我们希望有一种原地归并。复制到一个辅助数组,然后将原来的数组覆盖。
2.自顶向下的归并。采用分治思想。
具体子数组,可以采用不同的排序算法来处理。
并不会将数组元素复制到,辅助数组。节省这部分时间
3.自底向上的归并排序
我们通过把一个大问题分割成小问题分别解决,然后用所有小问题的答案解决大问题。
这里可以,先归并微型数组。之后两两归并,在继续两两归并(四四归并)。这种方法比标准递归需要的代码更少。
归并过程为:
比较a[i]和b[j]的大小,若a[i]≤b[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;
否则将第二个有序表中的元素b[j]复制到r[k]中,并令j和k分别加上1,
如此循环下去,直到其中一个有序表取完,
然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!