Java数据结构之常见排序算法（上）

public void insertSort(int[] array) {
    // 外循环控制趟数, 第一张牌默认有序, 所以 i 从 1 开始
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i]; //当前摸到的牌
        // 每次从手中牌的最后一张牌开始比较, 一直比到第一张牌
        int j = i - 1;
        for (; j >= 0; j--) {
            //如果当前位置的牌,大于我摸到的牌,就往后挪
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // 把摸到的牌放到对应位置上
        array[j + 1] = tmp;
    }
}

public void shellSort(int[] array) {
    // gap初始值设置成数组长度的一半
    int gap = array.length >> 1;
    // gap 为 1 的时候直接插入排序
    while (gap >= 1) {
        shell(array, gap);
        gap >>= 1; // 更新 gap 值 等价于 -> gap /= 2;
    }
}
private void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i - gap;
        for (; j >= 0; j -= gap) {
            if (array[j] > tmp) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = tmp;
    }
}

public void selectSort(int[] array) {
    int end = array.length - 1;
    // 剩最后一个元素的时候, 不用比较了, 已经有序了
    // 所以 i < array.length - 1
    for (int i = 0; i < array.length - 1; i++) {
        int max = 0;
        int j = 0;
        while (j <= end) {
            if (array[j] > array[max]) {
                max = j;
            }
            j++;
        }
        //找到了最大值的下标, 把最大值与最后一个值交换
        swap(array, max, end--); // end-- 最后一个元素固定了, 不用参与比较
    }
}

public void selectSort(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int maxIndex = left;
        int minIndex = left;
        // i = left + 1 -> 每次找最大最小值下标的时候, 可以不用算默认给的最大值和最小值下标
        for (int i = left + 1; i <= right; i++) {
            if (array[i] > array[maxIndex]) {
                maxIndex = i;
            }
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
        }
        swap(array, minIndex, left);
        // 如果最大值为 left 的位置情况的话, 走到这, 最大值已经被交换到 min 位置上了
        if (maxIndex == left) {
            // 更新最大值的位置
            maxIndex = minIndex;
        }
        swap(array, maxIndex, right);
        left++;
        right--;
    }
}

public void heapSort(int[] array) {
    // 建大堆 从最后一个非叶子节点开始向下调整
    // 非叶子节点下标 = (孩子节点下标 - 1) / 2
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        shiftDown(array, parent, array.length);
    }
    // 建大堆完成后, 每次堆顶元素与最后一个元素交换, 锁定最大元素的位置
    for (int len = array.length - 1; len > 0; len--) {
        swap(array, 0, len); //根节点与最后一个元素交换
        shiftDown(array, 0, len); //根节点位置向下调整
    }
}
private void shiftDown(int[] array, int parent, int len) {
    int child = parent * 2 + 1;
    while (child < len) {
        if (child + 1 < len && array[child + 1] > array[child]) {
            child++;
        }
        // 判断父节点是否大于较大的孩子节点
        if (array[parent] < array[child]) {
            swap(array, parent, child);
            // 更新下标的位置
            parent = child;
            child = parent * 2 + 1;
        } else {
            return;
        }
    }
}