java实现八大排序

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

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，再进行下一趟排序）如此重复，直至子序列元素个数达到数组元素个数一样。算法实现：

 

2.二分法插入排序

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

 

3.希尔排序

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

4.冒泡排序

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

 

 

 

5.快速排序

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

 

6.直接选择排序

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

 

7.堆排序

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

8.归并排序的算法

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

算法实现如下：