希尔排序与堆排序

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;//下一次继续从分组里的前一个位置开始
                }
            }

        }
    }
}

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]放到该放的位置
    }
}