Java中都有哪些排序算法
今天就跟大家聊聊有关Java中都有哪些排序算法,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。
排序
<p _hover-ignore="1" white-space:normal;background-color:#FFFFFF;"> 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
概念
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。
常见排序算法
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
分类
稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在 用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法 是稳定的。其中冒泡,插入,基数,归并属于稳定排序,选择,快速,希尔,堆属于不稳定排序。
就地排序:若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1), 则称为就地排序。
排序算法
冒泡排序
持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 复杂度分析:平均情况与最坏情况均为 O(n^2), 使用了 temp 作为临时交换变量,空间复杂度为 O(1)
堆排序
堆排序的是集合了插入排序的单数组操作,又有归并排序的时间复杂度,完美的结合了2者的优点。
直接插入排序
直接插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入到已排好的有序的表中,从而得到一个新的、记录数增1的有序表。当前元素的前面元素均为有序,要插入时,从当前元素的左边开始往前找(从后往前找),比当前元素大的元素均往右移一个位置,最后把当前元素放在它应该呆的位置就行了。
归并排序
归并排序(Merge Sort)与快速排序思想类似:将待排序数据分成两部分,继续将两个子部分进行递归的归并排序;然后将已经有序的两个子部分进行合并,最终完成排序。
其时间复杂度与快速排序均为O(nlogn),但是归并排序除了递归调用间接使用了辅助空间栈,还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序,但是归并排序是一种稳定的排序算法,快速排序则不然。
所谓稳定排序,表示对于具有相同值的多个元素,其间的先后顺序保持不变。对于基本数据类型而言,一个排序算法是否稳定,影响很小,但是对于结构体数组,稳定排序就十分重要。
快速排序
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
直接选择排序
所谓选择排序,就是每次找到未排序中最小的(最大的也行)元素的位置,找到后与该位置与未排序序列的第一个元素交换值,直到该序列成为有序序列。
初始状态整个序列为无序序列,每次交换都使有序序列的长度加一,无序序列的起始位置后移一位。选择排序的平均时间复杂度为O(n^2),且选择排序相对不稳定。
希尔排序
Shellsort是最古老的排序算法之一,该算法以其发明者Donald L. Shell的名字命名。
在ShellSort排序算法之前的算法时间复杂度基本都是O(n2)O(n2),该算法是突破这个时间复杂度的第一批算法之一。
看完上述内容,你们对Java中都有哪些排序算法有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注行业资讯频道,感谢大家的支持。