4. 5. /**
6. * 简单选择排序算法 7. * @author jzj 8. * @date 2009-12-5 9. *
10. * @param 11. */
12. public class SelectSort> extends Sort { 13. 14. /**
15. * 排序算法的实现，对数组中指定的元素进行排序 16. * @param array 待排序的数组 17. * @param from 从哪里开始排序 18. * @param end 排到哪里 19. * @param c 比较器 20. */
21. public void sort(E[] array, int from, int end, Comparator c) { 22. int minlIndex;//最小索引 23. /*
24. * 循环整个数组（其实这里的上界为 array.length - 1 即可，因为
当 i= array.length-1
25. * 时，最后一个元素就已是最大的了，如果为array.length时，内
层循环将不再循环），每轮假设
26. * 第一个元素为最小元素，如果从第一元素后能选出比第一个元素
更小元素，则让让最小元素与第一
27. * 个元素交换 28. */
29. for (int i = from; i <= end; i++) {
30. minlIndex = i;//假设每轮第一个元素为最小元素 31. //从假设的最小元素的下一元素开始循环 32. for (int j = i + 1; j <= end; j++) {
33. //如果发现有比当前array[smallIndex]更小元素，则记下该元素的索引于
smallIndex中
34. if (c.compare(array[j], array[minlIndex]) < 0) {
35. minlIndex = j; 36. } 37. } 38.
39. //先前只是记录最小元素索引，当最小元素索引确定后，再与每轮的第一
个元素交换
40. swap(array, i, minlIndex); 41. } 42. } 43. 44. /** 45. * 测试
46. * @param args 47. */
48. public static void main(String[] args) {
49. Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 }; 50. SelectSort insertSort = new SelectSort(); 51. Sort.testSort(insertSort, intgArr); 52. Sort.testSort(insertSort, null); 53. } 54. } 堆排序
堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示：
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。 堆是一种完全二叉树，一般使用数组来实现。堆排序也是一种选择性的排序，每次选择第i大的元素。
另外排序过程中借助了堆结构，堆就是一种完全二叉树，所以这里先要熟悉要用的二叉树几个性质：
N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。
且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。 注，这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。
算法描述：
堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节
第一步实现 ：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放。
第二步实现 ：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。 堆是一种完全二叉树，一般使用数组来实现。堆排序也是一种选择性的排序，每次选择第i大的元素。
另外排序过程中借助了堆结构，堆就是一种完全二叉树，所以这里先要熟悉要用的二叉树几个性质：
N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。
且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。 注，这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。 算法描述：
堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节
第一步实现 ：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放。
第二步实现 ：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。 堆是一种完全二叉树，一般使用数组来实现。堆排序也是一种选择性的排序，每次选择第i大的元素。
另外排序过程中借助了堆结构，堆就是一种完全二叉树，所以这里先要熟悉要用的二叉树几个性质：
N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。
且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。 注，这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。 算法描述：