java常用排序算法总结<一>【转】
这篇排序文章从思想理解到实现，然后到整理，花了我几天的时间，现把它记录于此，希望对大家有一定的帮助，写的不好的请不要见笑，写错了的，请指出来我更正。最后如果对你有一定的帮助，请回贴支持一下哦^_^ ！
申明：排序算法思想来自互联网，代码自己实现，仅供参考。
插入排序直接插入排序、希尔排序
简单选择排序、堆排序
冒泡排序、快速排序
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。
堆是一种完全二叉树，一般使用数组来实现。堆排序也是一种选择性的排序，每次选择第i大的元素。
?
另外排序过程中借助了堆结构，堆就是一种完全二叉树，所以这里先要熟悉要用的二叉树几个性质：
N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。
且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。
注，这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。
?
算法描述：
堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节
第一步实现：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放。
第二步实现：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
?
- package?sort;????import?java.util.Comparator;????public?class?HeapSort<E?extends?Comparable<E>>?extends?Sort<E>?{????????/**??????*?排序算法的实现，对数组中指定的元素进行排序??????*?@param?array?待排序的数组??????*?@param?from?从哪里开始排序??????*?@param?end?排到哪里??????*?@param?c?比较器??????*/??????public?void?sort(E[]?array,?int?from,?int?end,?Comparator<E>?c)?{??????????//创建初始堆??????????initialHeap(array,?from,?end,?c);????????????/*??????????*?对初始堆进行循环，且从最后一个节点开始，直接树只有两个节点止??????????*?每轮循环后丢弃最后一个叶子节点，再看作一个新的树??????????*/??????????for?(int?i?=?end?-?from?+?1;?i?>=?2;?i--)?{??????????????//根节点与最后一个叶子节点交换位置，即数组中的第一个元素与最后一个元素互换??????????????swap(array,?from,?i?-?1);??????????????//交换后需要重新调整堆??????????????adjustNote(array,?1,?i?-?1,?c);??????????}????????}????????/**??????*?初始化堆??????*?比如原序列为：7,2,4,3,12,1,9,6,8,5,10,11??????*?则初始堆为：1,2,4,3,5,7,9,6,8,12,10,11??????*?@param?arr?排序数组??????*?@param?from?从哪??????*?@param?end?到哪??????*?@param?c?比较器??????*/??????private?void?initialHeap(E[]?arr,?int?from,?int?end,?Comparator<E>?c)?{??????????int?lastBranchIndex?=?(end?-?from?+?1)?/?2;//最后一个非叶子节点??????????//对所有的非叶子节点进行循环?，且从最一个非叶子节点开始??????????for?(int?i?=?lastBranchIndex;?i?>=?1;?i--)?{??????????????adjustNote(arr,?i,?end?-?from?+?1,?c);??????????}??????}????????/**??????*?调整节点顺序，从父、左右子节点三个节点中选择一个最大节点与父节点转换??????*?@param?arr?待排序数组??????*?@param?parentNodeIndex?要调整的节点，与它的子节点一起进行调整??????*?@param?len?树的节点数??????*?@param?c?比较器??????*/??????private?void?adjustNote(E[]?arr,?int?parentNodeIndex,?int?len,?Comparator<E>?c)?{??????????int?minNodeIndex?=?parentNodeIndex;??????????//如果有左子树，i?*?2为左子节点索引???????????if?(parentNodeIndex?*?2?<=?len)?{??????????????//如果父节点小于左子树时???????????????if?(c.compare(arr[parentNodeIndex?-?1],?arr[parentNodeIndex?*?2?-?1])?<?0)?{??????????????????minNodeIndex?=?parentNodeIndex?*?2;//记录最大索引为左子节点索引???????????????}????????????????//?只有在有或子树的前提下才可能有右子树，再进一步断判是否有右子树???????????????if?(parentNodeIndex?*?2?+?1?<=?len)?{??????????????????//如果右子树比最大节点更大???????????????????if?(c.compare(arr[minNodeIndex?-?1],?arr[(parentNodeIndex?*?2?+?1)?-?1])?<?0)?{??????????????????????minNodeIndex?=?parentNodeIndex?*?2?+?1;//记录最大索引为右子节点索引???????????????????}??????????????}??????????}????????????//如果在父节点、左、右子节点三都中，最大节点不是父节点时需交换，把最大的与父节点交换，创建大顶堆??????????if?(minNodeIndex?!=?parentNodeIndex)?{??????????????swap(arr,?parentNodeIndex?-?1,?minNodeIndex?-?1);??????????????//交换后可能需要重建堆，原父节点可能需要继续下沉??????????????if?(minNodeIndex?*?2?<=?len)?{//是否有子节点，注，只需判断是否有左子树即可知道??????????????????adjustNote(arr,?minNodeIndex,?len,?c);??????????????}??????????}??????}????????/**??????*?测试??????*?@param?args??????*/??????public?static?void?main(String[]?args)?{??????????Integer[]?intgArr?=?{?7,?2,?4,?3,?12,?1,?9,?6,?8,?5,?10,?11?};??????????HeapSort<Integer>?sort?=?new?HeapSort<Integer>();??????????HeapSort.testSort(sort,?intgArr);??????????HeapSort.testSort(sort,?null);??????}????}
?
?