Java 数据结构：七大排序算法（上） | 极客日志

Java 数据结构：七大排序算法（上） | 极客日志

tmp

array[j+1]

/**
 * 直接插入排序
 * 
 * 时间复杂度:
 * 最好情况：数据完全有序 O(N)
 * 最坏情况：数据完全逆序 O(N^2)
 * 结论：数据越有序，排序越快，适合基本有序的数据场景
 * 
 * 空间复杂度：O(1)
 * 稳定性：稳定
 *
 * @param array 待排序数组
 */
public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i];
        int j = i - 1;
        // 在已排序区间 [0, i-1] 中查找插入位置
        for (; j >= 0; j--) {
            if (array[j] > tmp) {
                // 保持稳定性，相等时不交换
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // 插入元素
        array[j + 1] = tmp;
    }
}

/**
 * 希尔排序
 * 
 * 时间复杂度：O(n^1.3) ~ O(n^1.5) (取决于 gap 选取策略)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 *
 * @param array 待排序数组
 */
public static void shellSort(int[] array) {
    int gap = array.length;
    while (gap > 1) {
        gap /= 2;
        shell(array, gap);
    }
}

private static 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;
    }
}

/**
 * 选择排序
 * 
 * 时间复杂度：最好/最坏均为 O(N^2)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 *
 * @param array 待排序数组
 */
public static void selectSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        swap(array, minIndex, i);
    }
}

public static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

public static void selectSort2(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int minIndex = left;
        int maxIndex = left;
        for (int i = left; i <= right; i++) {
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
            if (array[i] > array[maxIndex]) {
                maxIndex = i;
            }
        }
        swap(array, left, minIndex);
        // 特殊情况处理：如果最大值原本就在 left 位置，上面的交换将其移到了 minIndex
        if (maxIndex == left) {
            maxIndex = minIndex;
        }
        swap(array, right, maxIndex);
        left++;
        right--;
    }
}

/**
 * 堆排序
 * 
 * 时间复杂度：O(N*logN)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 *
 * @param array 待排序数组
 */
public static void heapSort(int[] array) {
    createBigHeap(array);
    int end = array.length - 1;
    while (end > 0) {
        swap(array, 0, end);
        shiftDown(array, 0, end);
        end--;
    }
}

private static void createBigHeap(int[] array) {
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        shiftDown(array, parent, array.length);
    }
}

private static void shiftDown(int[] array, int parent, int end) {
    int child = parent * 2 + 1;
    while (child < end) {
        // 确保右子树存在且比左子树大
        if (child + 1 < end && array[child + 1] > array[child]) {
            child++;
        }
        if (array[child] > array[parent]) {
            swap(array, child, parent);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}