排序算法之选择排序

选择排序

选择排序有两种排序方法：简单选择排序和堆排序

简单选择排序

原理

简单选择排序的原理很简单，就是从待排序序列中一步一步选出最小的数（从小到大排）放到前面，例如待排序列[4,3,6,1]，首先我们默认4是最小的，然后往后找，发现3比4小，我们记住3所在的位置，再往后，6不小于3跳过，继续，1比3小，记住1所在位置，将1和4交换，于是序列变为[1,3,6,4]，然后再从3开始重复以上步骤，就这么简单

实现

public static void simpleSelectionSort(int[] num) {
    int minIndex;
    for (int i = 0; i < num.length; i++) {
        minIndex = i;
        for (int j = i + 1; j < num.length - 1; j++) {
            if (num[j] < num[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            num[i] = num[i] + num[minIndex];
            num[minIndex] = num[i] - num[minIndex];
            num[i] = num[i] - num[minIndex];
        }
    }
}

堆排序

原理

堆排序是利用堆这种数据结果的性质进行排序，堆是一个完全二叉树，堆分为大根堆和小根堆，大根堆是指父节点的值不小于它子节点的值的堆。例如同样对于上述序列[4,3,6,1]，用大根堆表示这个序列则为：

如果用数组表示则为[6,4,3,1]，大根堆和数组之间有关系吗？对于6这个数，它的索引为0，那么它的两个子节点的索引为1和2，对于用数组表示的堆，数组中任意一个数的子节点的索引为(2*i)+1和(2*i)+2（可能会超过数组长度），这就是我们要用到的最重要的关系，就是靠这个关系，我们可以将一个普通数组变为一个堆。再来看看图中的大根堆，它的第一个数永远是最大的，所以我们可以一步一步的把堆顶点的数选择出来，再对剩下的数再建堆，再取出堆顶的数，这样我们取出的数就是从大到小的了。所以堆排序的过程为：

1. 建堆
2. 选出最大
3. 对剩下的再建堆
4. 重复二、三步骤

选择数据的步骤很容易，最主要的就是如何建堆了，这就要用到刚才说到的那两个关系了，对于i，(2*i)+1和(2*i)+2（后两个可能不存在）这三个位置的数，我们保证i位置大于后面两个位置的数就可以了，如果不大于我们就交换，这样就可以建立一个大根堆了

实现

public static void heapsort(int[] num) {
    for (int i = num.length / 2; i >= 0; i--)
        buildMaxHeapify(num, num.length, i);
    for (int i = num.length - 1; i > 0; i--) {
        // 把最大的选出来放在最后
        num[0] = num[0] + num[i];
        num[i] = num[0] - num[i];
        num[0] = num[0] - num[i];
        // 对剩下的再建堆
        buildMaxHeapify(num, i, 0);
    }
}


public static void buildMaxHeapify(int[] num, int size, int index) {
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int maxIndex = index;
    if (left < size && num[left] > num[maxIndex]) {
        maxIndex = left;
    }
    if (right < size && num[right] > num[maxIndex]) {
        maxIndex = right;
    }
    if (maxIndex != index) {
        // 交换
        num[maxIndex] = num[maxIndex] + num[index];
        num[index] = num[maxIndex] - num[index];
        num[maxIndex] = num[maxIndex] - num[index];
        // 交换了的位置上可能不满足大根堆的条件了，所以对于交换了的位置要再建堆
        buildMaxHeapify(num, size, maxIndex);
    }
}