希尔排序
待排序区间划分成若干个有跨度的子区间，然后进行插入排序，当最后跨度缩小到1的时候来一次完整的插入排序。
第一次排序：length = 10; gap = a.length / 2 = 5; 将待排序的区间分成五个相同跨度的子区间。得到{49,13} {38,27} {65,49*} {97,55} {76,4}五个子区间,进行插入排序，得到排序后的区间为：{13,49} {27,38} {49*,65} {97,55} {4,76}
{13,27,49*,55,4,49,38,65,97,76}
第二次排序：gap = gap / 2 = 2; 将区间分为两个子区间。得到{13,49*,4,38,97} {27, 55, 49, 65, 76}两个子区间，插入排序后得到{4,13,38,49*,97} 和 {27,49,55,65,76}
{4,27,13,49,38,55,49*,65,97,76}
第三次排序：gap = gap / 2 = 1; 所以直接对{4,27,13,49,38,55,49*,65,97,76}进插入排序，就可以得到排序后的区间为{4,13,27,38,49,49*,55,65,76,97}
import java.util.Arrays; import java.util.Scanner; public class shellSort { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int[] a = new int[10]; for (int i = 0; i < a.length; i++) { a[i] = scanner.nextInt(); } shell(a); System.out.println(Arrays.toString(a)); } public static void shell(int[] a) { for (int gap = a.length / 2; gap > 0 ; gap /= 2) { //没分一组就直接进行插入排序 for (int i = gap; i < a.length; i++) { int j = i;//存放每一组中当前要处理的那个数据 while (j - gap >= 0 && a[j - gap] >a[j]) { //大的数据往后移动 int temp = a[j]; a[j] = a[j - gap]; a[j - gap] = temp; j -= gap;//下一次继续从分组里的前一个位置开始 } } } } }
堆排序
初始数组为：int[] a = {57, 68, 59, 52, 72, 28, 96, 33, 24};
（1）用数组存储，第i个节点的叶子分别是2i+1和2i+2
（2）根的值小于(或者大于)左右子树，子树也需要满足这个定义
（3）堆看起来是一棵完全二叉树，存储却只需要用到数组即可
（4）开始建堆的时候数组顺序与二叉树层次遍历对应，逐步从非叶子节点到根调整
（5）堆排序以大根堆为例，每次堆顶和最后的那个叶子对调，保证大的放到目前堆的最后，然后把顶部元素调整好，最后就是升序排列
import java.util.Arrays; //堆排序 public class heapSort { public static void main(String[] args) { int[] a = {57, 68, 59, 52, 72, 28, 96, 33, 24};//待排序数组的初始顺序 heap(a); System.out.println(Arrays.toString(a)); } public static void heap(int[] a) { //从倒数第一个非叶子结点开始调整，一直调整到根，让数组满足大根堆的递归定义 for (int i = a.length / 2 - 1; i >= 0 ; i--) {//a.length / 2 - 1 是堆的最后一个非叶子结点 //对数组的第i个元素当做根，调整的范围是目前无序的空间 adjustHeap(a, i, a.length);//a.length 是目前无序的空间 } for (int i = a.length - 1; i > 0 ; i--) { swap(a, 0, i);//交换数组里的根和无序堆中的最后一个数 adjustHeap(a, 0, i);//每一轮都把前i个里最大的数放到最后，这样无序的范围都是0到i } } //swap方法完成数组中根和无序堆中最后一个数的交换 private static void swap(int[] a, int root, int last) {//root为根 last为最后的数 int temp = a[root]; a[root] = a[last]; a[last] = temp; } //左右子树挑大的进行交换，继续对左右子树进行调整，保证整个堆递归满足大根堆的定义 private static void adjustHeap(int[] a, int i, int length) { int bak = a[i];//备份一下要调整的元素 //开始的时候，从待调整的元素i的左子树开始 2 * i + 1，后面每次递归 2 * j + 1 for (int j = 2 * i + 1; j < length; j = 2 * j + 1) { if (j + 1 < length && a[j + 1] > a[j]) { //j + 1为右子树，需要小于length并且让j永远都指向自己左右子树里大的那个 j++; } if (bak < a[j]) { //如果bak的元素小于左右子树中大的那一个 a[i] = a[j];//大的元素拷贝到i这个位置 i = j;//下一次从以i为根的子树开始，让i等于这个j作为根 } else break;//不小于说明位置已经调整好了 } a[i] = bak;//一次性把最原始要调整的a[i]放到该放的位置 } }
