选择排序

Contents

1. 1. 简单选择排序
2. 2. 堆排序
   1. 2.0.1. 堆排序

选择排序分为 简单选择排序 和 堆排序

简单选择排序

public static void selectSort(int[] a) {
    int len = a.length;
    for (int k = 0; k < len; k++) {
        int min = k;
        for (int i = k + 1; i < len; i++) {
            if (a[i] < a[min]) {
                min = i;
            }
        }
        if (k != min) {
            int temp = a[k];
            a[k] = a[min];
            a[min] = temp;
        }
    }
    printSort(a);
}

堆排序

堆 一般指二叉堆，(由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为
堆), 二叉堆是完全二叉树或近似完全二叉树

特性：

• 父节点 总是 大于或等于（小于或等于） 任何一个子节点
• 每个节点的左右子树都是一个二叉堆（大根堆 /小根堆）

存储：一般用数组存储，i节点的父节点的下标为 （i-1）/2

它的左右子节点为 2*i+1 , 2*i+2

操作：
建堆 刚开始的数组,对应的树不是堆，需要将其堆化，依次将父节点的值与子节点中最大（小）的值比较，交换
插入 插入到堆末，这时堆已经乱了次序，需要再次更新 堆化
删除 删除节点总是发生在根节点 a[0]， 删除后将最后一个节点交换上来，再次更新，堆化

堆排序

public static void headSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        createMaxHeap(a, a.length - 1 - i); //堆化 大根堆 
        swap(a, 0, a.length - 1 - i); //大根堆的节点是最大的，将其放到最后
        printSort(a);
    }
}

private static void createMaxHeap(int[] a, int lastIndex) {
    for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
        // 保存当前正在判断的节点
        int k = i;
        // 若当前结点的子节点存在
        while (2 * k + 1 <= lastIndex) {
            // biggerIndex 总是记录较大节点的值，先赋值为 当前判断节点的子节点
            int biggerIndex = 2 * k + 1;
            if (biggerIndex < lastIndex) {
                // 若右子节点存在，否则此时biggerIndex应该等于lastIndex
                if (a[biggerIndex] < a[biggerIndex + 1]) {
                    // 若右子节点值比左节点大，则biggerIndex记录的是右子节点的值
                    biggerIndex++;
                }
            }
            if (a[k] < a[biggerIndex]) {
                // 若当前节点值比子节点最大值小，则交换二者的值，交换后将biggerIndex的值付给k
                swap(a, k, biggerIndex);
                k = biggerIndex;
            } else {
                break;
            }
        }
    }
}