Nice！第一次见这么全面的Java实现八大排序算法，爱了( 二 ) 它们都属于内部排序

< a[j - h]) {int temp = a[j];a[j] = a[j - h];a[j - h] = temp;}}}}}复杂度分析以下是希尔排序复杂度:
平均时间复杂度最好情况最坏情况空间复杂度O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)
总结与思考希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。
简单选择排序基本思想选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
算法描述

从未排序序列中，找到关键字最小的元素
如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
重复1、2步，直到排序结束。

动图效果如下所示：

文章插图
代码实现

public static void sort(int[] a) {for (int i = 0; i < a.length; i++) {int min = i;//选出之后待排序中值最小的位置for (int j = i + 1; j < a.length; j++) {if (a[j] < a[min]) {min = j;}}//最小值不等于当前值时进行交换if (min != i) {int temp = a[i];a[i] = a[min];a[min] = temp;}}}

复杂度分析以下是选择排序复杂度:

文章插图
总结与思考选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子” ，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n2/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。唯一值得高兴的是，它并不耗费额外的内存空间。
堆排序1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同发明了著名的堆排序算法(Heap Sort).
堆的定义如下：nn个元素的序列{k1,k2,..,kn}当且仅当满足下关系时，称之为堆。

文章插图
把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉树中任何一个非也子节点的值均不大于（或不小于）其左，右孩子节点的值。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。
基本思想此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。
算法描述

先将初始序列K[1..n]K[1..n]建成一个大顶堆, 那么此时第一个元素K1K1最大, 此堆为初始的无序区.
再将关键字最大的记录K1K1 (即堆顶, 第一个元素)和无序区的最后一个记录 KnKn 交换, 由此得到新的无序区K[1..n?1]K[1..n?1]和有序区K[n]K[n], 且满足K[1..n?1].keys?K[n].keyK[1..n?1].keys?K[n].key
交换K1K1 和 KnKn 后, 堆顶可能违反堆性质, 因此需将K[1..n?1]K[1..n?1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止。

动图效果如下所示：

文章插图
代码实现从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。
总结起来就是定义了以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

对于堆节点的访问：