登录 / 注册
IT168技术开发频道
IT168首页 > 技术开发 > 技术开发技术 > 正文

Java学习之7种排序算法的完整实例代码

2018-06-28 17:54    爪哇笔记 来源:爪哇笔记  作者: Java爱好者 编辑: 田晓旭

  【IT168 技术】排序

  排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

  概念

  将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。

Java学习之7种排序算法的完整实例代码

  常见排序算法

  快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

  分类

  稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在 用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法 是稳定的。其中冒泡,插入,基数,归并属于稳定排序,选择,快速,希尔,堆属于不稳定排序。

  就地排序:若排序算法所需的辅助空间并不依赖于问题的规模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),该算法是突破这个时间复杂度的第一批算法之一。

  另外 Shellsort 是快速、易于理解和易于实现的。 然而,其复杂度分析有点复杂。

标签: java , 排序
  • IT168企业级IT168企业级
  • IT168文库IT168文库

扫一扫关注

行车视线文章推荐

首页 评论 返回顶部