214°

java基础的几个算法

一般对于排序算法我们通常考虑: 是否稳定(相同值的两个数位置是否会变) 和 时间复杂度(算法执行次数的规模量级)。至于说空间复杂度(算法在运行过程中临时占用存储空间大小的量度)其实对于每种算法具体实现代码风格迥异。

从实现上如何处理稳定

 一般而言:稳定的排序算法有:冒泡排序、插入排序、归并排序和基数排序;不稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
个人感觉在代码实现各种算法时,是否稳定取决于在处理相同值的两个不同数据下标是否swap。
比如说:
           冒泡: 处理等值时,取下标大的就不用swap可以达到稳定,但是取下标小的得swap则不稳定。(取小下标 多做一次swap)
           插入: 处理等值时, 前插处理则不稳定, 跳过则稳定。(前插 多做一轮swap)
           选择: 选择一个最大的值置于队尾。在判定最大值时,如果等值取下标大的可以达到稳定,取小标小的则不稳定。(取大下标 多做一次swap)

等等诸如此类在实现的处理细节决定是否可以做成稳定, 但是同样的带来执行的次数会多。 而对于实际上我们只需要知道排序后的结果数组,当然执行规模越少,效率越快 越好喽

如何区分时间复杂度

冒泡、选择、插入:  平方阶(O(n2))排序

经过实际代码可以发现,这些都是在从前往后的轮询数组,只是边界在慢慢变小,边界每变化一次就轮询一次。 (冒泡与选择相同都在于比较值取大小;不同在于冒泡是每次比较后都swap,而选择只是记录需要的数据下标,最后才将下标与队尾swap)

快速、堆和归并:  线性对数阶(O(nlog2n))排序

经过实际代码可以发现, 都类似于将排序数组切分成2部分递归处理。

基数: 线性阶(O(n))排序

          

 

 

 

本文由【noob_fly】发布于开源中国,原文链接:https://my.oschina.net/u/3434392/blog/3011170

全部评论: 0

    我有话说: