希尔排序
待排序区间划分成若干个有跨度的子区间，然后进行插入排序，当最后跨度缩小到1的时候来一次完整的插入排序。
代码语言：javascript复制第一次排序：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]放到该放的位置
}
}
