java实现八大排序

桃扇骨 2022-04-22 05:30 205阅读 0赞

我们知道排序是指将数据元素按照指定关键字值的大小递增（或递增）次序重新排列，有**插入排序**、**交换排序**、**选择排序**和**并归排序**。

**1.直接插入排序**

现有数组\{23,15,56,14,26,58,99,33,78\}，我们从第一趟开始，将a0（此时的a0是一个已排好的排序子序列\{23\}）**赋值给变量temp**，然后将a0与a1比较，若是a0>a1，则将a0赋值给a1，**再将temp赋值给a0**，此时排序子序列变成了\{15,23\}。（若是a0<a1，则a0还是a0，再进行下一趟排序）如此重复，直至子序列元素个数达到数组元素个数一样。算法实现：

![640_wx_fmt_png][]

**2.二分法插入排序**

直接插入排序的每一趟，将一个元素ai插入到它的前面的一个排序子序列中，其中采用的顺序查找算法寻找ai的插入位置。此时，**子序列是顺序存储且排序的**，这两条正好符合二分法查找要求。因此，用**二分法查找代替**直接插入排序中的**顺序查找**，则构成二分法插入排序。

**3.希尔排序**

希尔排序的算法思想是将一个数组分成若干组，**每组有若干相隔距离**（称为增量）的元素组成，在一组内**采用直接插入排序算法**进行排序，增量初值通常为**数组长度的一半**，以后一次减半，直至为1。算法如下：

![640_wx_fmt_png 1][]

**4.冒泡排序**

冒泡排序的算法：比较相邻两个元素大小，如果反序，则交换。若按升序排序，每趟将数据序列中最大元素交换到最后位置，就像气泡从水里冒出来一样。若现有序列\{32,26,87,72,29,17\}，第一趟，将32与相邻元素比较，结果比26大，则交换，后又碰到87，32比87小，则将87与其相邻元素比较，依次得第一趟后的序列为\{26,32,72,29,17,87\}，如此递归。算法实现如下：

![640_wx_fmt_png 2][]

![640_wx_fmt_png 3][]

**5.快速排序**

快速排序是一种分区交换排序算法，在数据序列中选择一个元素作为基准值，每趟从数据序列的两端开始进行交替，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值得最终位置。同时，序列被划分为两个子序列，再分别对两个子序列进行快速排序，直到子序列长度为1，则完成排序。算法实现如下：

![640_wx_fmt_png 4][]

![640_wx_fmt_png 5][]

**6.直接选择排序**

直接选择排序算法思想：第一趟从n个元素的数据序列中选出关键字最小（大）的，然后将其放到最前（后）的位置，以后一次类推。若现有序列\{38，97，26，19，39，15\}，第一趟就选出15，排序为\{15，38，97，26，19，39\}，依次循环，直至最后一个选取的元素正好是最后那个位置。

![640_wx_fmt_png 6][]

**7.堆排序**

堆排序是利用完全二叉树特性的一种选择排序。

![640_wx_fmt_png 7][]

![640_wx_fmt_png 8][]

**8.归并排序的算法**

关键字序列\{97,82,85,53,17,61,70,12,62,58,26\}的归并排序（升序）的过程如下：

![640_wx_fmt_png 9][]

算法实现如下：

![640_wx_fmt_png 10][]

![640_wx_fmt_png 11][]

[640_wx_fmt_png]: /images/20220422/62fec3e22f0f48afafbf15c3351f6c96.png
[640_wx_fmt_png 1]: /images/20220422/71e722220e304b8db01dd43ce1bd6911.png
[640_wx_fmt_png 2]: /images/20220422/75392cadb36043b7a35d5d8cced11f00.png
[640_wx_fmt_png 3]: /images/20220422/b077f868fec44f45a80334188d5f5b12.png
[640_wx_fmt_png 4]: /images/20220422/132c85996a0d48838d1f7bbf02dfb9f4.png
[640_wx_fmt_png 5]: /images/20220422/167efae5f33b4f72850ddfa5fad95b0d.png
[640_wx_fmt_png 6]: /images/20220422/4ceaf145386c46c29ce9ee6c24537ca2.png
[640_wx_fmt_png 7]: /images/20220422/abd3107b98944e99bcceda144e2c5c6b.png
[640_wx_fmt_png 8]: /images/20220422/cd9062476a044073a505e02bb14dbe67.png
[640_wx_fmt_png 9]: /images/20220422/4afc5efd0ae742b9bb620f7d410e5be4.png
[640_wx_fmt_png 10]: /images/20220422/68019f49f3d9475893819cc65806a305.png
[640_wx_fmt_png 11]: /images/20220422/1ddd9892462c47ccabe0684efd567242.png