经典排序算法详解：插入、希尔、选择、冒泡、堆与快速排序

经典排序算法详解

一、插入排序

1.1 直接插入排序

直接插入排序的基本思想是：将第一个元素视为有序序列，从第二个元素开始，依次将其插入到前面已排序的序列中。如果当前元素比前一个元素小，则前一个元素后移，直到找到合适位置。

public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i];
        int j = i - 1;
        // 向前查找并移动元素
        for (; j >= 0; j--) {
            if (tmp < array[j]) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        // 插入到正确位置
        array[j + 1] = tmp;
    }
}

• 时间复杂度：最坏 O(N²)，最好 O(N)
• 空间复杂度：O(1)
• 稳定性：稳定

1.2 希尔排序

希尔排序（缩小增量法）是对插入排序的优化。它先将整个待排序记录分割成若干子序列，分别进行直接插入排序，随着增量逐渐减小，子序列包含的元素越来越多，当增量为 1 时，整个文件恰被分成一组，算法便终止。

public static void shellSort(int[] array) {
    int gap = array.length;
    while (gap > 1) {
        gap /= 2;
        shell(array, gap);
    }
}

private static void shell(int[] arr, int gap) {
    for (int i = gap; i < arr.length; i++) {
        int tmp = arr[i];
        int j = i - gap;
        for (; j >= 0; j -= gap) {
            if (tmp < arr[j]) {
                arr[j + gap] = arr[j];
            } else {
                break;
            }
        }
        arr[j + gap] = tmp;
    }
}

• 时间复杂度：O(N^1.25) 左右
• 空间复杂度：O(1)

二、选择排序

2.1 单向选择排序

每次从未排序部分选出最小值，放到已排序部分的末尾。

public static void selectSort2(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        swap(array, minIndex, i);
    }
}

2.2 双向选择排序

同时从两端寻找最大值和最小值，分别交换到两端，减少比较次数。

public static void selectSort(int[] array) {
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int maxIndex = left;
        int minIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < array[minIndex]) minIndex = i;
            if (array[i] > array[maxIndex]) maxIndex = i;
        }
        swap(array, left, minIndex);
        // 处理 maxIndex 已被交换的情况
        if (maxIndex == left) maxIndex = minIndex;
        swap(array, right, maxIndex);
        left++;
        right--;
    }
}

• 时间复杂度：O(N²)
• 空间复杂度：O(1)

2.3 堆排序

利用大根堆的性质，将堆顶元素与末尾元素交换，再调整堆，重复直至有序。

public static void createHeap(int[] array) {
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        siftDown(array, parent, array.length);
    }
}

private static void siftDown(int[] array, int parent, int size) {
    int child = 2 * parent + 1;
    while (child < size) {
        if (child + 1 < size && array[child] < array[child + 1]) {
            child = child + 1;
        }
        if (array[child] > array[parent]) {
            swap(array, child, parent);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

public static void heapSort(int[] array) {
    createHeap(array);
    int end = array.length - 1;
    while (end > 0) {
        swap(array, 0, end);
        siftDown(array, 0, end);
        end--;
    }
}

• 时间复杂度：O(N*logN)
• 空间复杂度：O(1)

三、交换排序

3.1 冒泡排序

通过相邻元素比较交换，将最大元素逐步'浮'到末尾。若一趟无交换则提前结束。

public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

• 时间复杂度：最好 O(N)，最坏 O(N²)
• 空间复杂度：O(1)
• 稳定性：稳定

3.2 快速排序

3.2.1 Hoare 版本

选取基准值，左右指针交替扫描，相遇时交换基准值。

public static void quickSort(int[] array) {
    quick(array, 0, array.length - 1);
}

private static void quick(int[] array, int left, int right) {
    if (left >= right) return;
    // 小区间使用插入排序优化
    if (right - left + 1 <= 10) {
        insertSort(array, left, right);
        return;
    }
    int index = middleNum(array, left, right);
    swap(array, left, index);
    int pos = partitionHoare(array, left, right);
    quick(array, left, pos - 1);
    quick(array, pos + 1, right);
}

private static int partitionHoare(int[] array, int left, int right) {
    int record = left;
    int tmp = array[left];
    while (left < right) {
        while (left < right && array[right] >= tmp) right--;
        while (left < right && array[left] <= tmp) left++;
        swap(array, left, right);
    }
    swap(array, record, left);
    return left;
}

// 辅助方法：三数取中
private static int middleNum(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    if (array[left] > array[right]) {
        if (array[right] > array[mid]) return right;
        else if (array[left] < array[mid]) return left;
        else return mid;
    } else {
        if (array[left] > array[mid]) return left;
        else if (array[right] < array[mid]) return right;
        else return mid;
    }
}

// 小区间插入排序优化
private static void insertSort(int[] array, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int tmp = array[i];
        int j = i - 1;
        for (; j >= left; j--) {
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = tmp;
    }
}

3.2.2 挖坑法

先挖掉基准值坑，左右指针填坑，最后回填基准值。

private static int partitionPit(int[] array, int left, int right) {
    int record = array[left];
    while (left < right) {
        while (left < right && array[right] >= record) right--;
        array[left] = array[right];
        while (left < right && array[left] <= record) left++;
        array[right] = array[left];
    }
    array[left] = record;
    return left;
}

3.2.3 前后指针法

cur 找小于基准值的数，prev 记录边界，遇到小于值则交换。

private static int partitionPointer(int[] array, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        if (array[cur] < array[left] && array[++prev] != array[cur]) {
            swap(array, cur, prev);
        }
        cur++;
    }
    swap(array, left, prev);
    return prev;
}

3.2.4 非递归快速排序

使用栈模拟递归过程，避免栈溢出。

public static void quickNor(int[] array) {
    quickSortNor(array, 0, array.length - 1);
}

private static void quickSortNor(int[] array, int left, int right) {
    Stack<Integer> stack = new Stack<>();
    int pivot = partitionHoare(array, left, right);
    if (pivot > left + 1) {
        stack.push(left);
        stack.push(pivot - 1);
    }
    if (pivot + 1 < right) {
        stack.push(pivot + 1);
        stack.push(right);
    }
    while (!stack.isEmpty()) {
        right = stack.pop();
        left = stack.pop();
        pivot = partitionHoare(array, left, right);
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < right) {
            stack.push(pivot + 1);
            stack.push(right);
        }
    }
}

四、归并排序

4.1 递归归并排序

分治策略，先递归拆分，再合并有序子数组。

public static void mergeSort(int[] array) {
    mergeSortM(array, 0, array.length - 1);
}

private static void mergeSortM(int[] array, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSortM(array, left, mid);
    mergeSortM(array, mid + 1, right);
    merge(array, left, mid, right);
}

private static void merge(int[] array, int left, int mid, int right) {
    int[] tmpArr = new int[right - left + 1];
    int k = 0;
    int s1 = left;
    int s2 = mid + 1;
    while (s1 <= mid && s2 <= right) {
        if (array[s1] <= array[s2]) {
            tmpArr[k++] = array[s1++];
        } else {
            tmpArr[k++] = array[s2++];
        }
    }
    while (s1 <= mid) tmpArr[k++] = array[s1++];
    while (s2 <= right) tmpArr[k++] = array[s2++];
    for (int i = 0; i < tmpArr.length; i++) {
        array[i + left] = tmpArr[i];
    }
}

• 时间复杂度：O(N*logN)
• 空间复杂度：O(logN)
• 稳定性：稳定

4.2 非递归归并排序

自底向上，按步长 gap 合并。

public static void mergeNor(int[] array) {
    int gap = 1;
    while (gap < array.length) {
        for (int i = 0; i < array.length; i += gap * 2) {
            int left = i;
            int mid = left + gap - 1;
            int right = mid + gap;
            if (mid >= array.length) mid = array.length - 1;
            if (right >= array.length) right = array.length - 1;
            merge(array, left, mid, right);
        }
        gap *= 2;
    }
}

五、计数排序

适用于整数范围有限的场景，无需比较，基于计数。

private static void sortCount(int[] array) {
    int maxVal = array[0];
    int minVal = array[0];
    for (int i = 0; i < array.length; i++) {
        if (array[i] > maxVal) maxVal = array[i];
        if (array[i] < minVal) minVal = array[i];
    }
    int len = maxVal - minVal + 1;
    int[] count = new int[len];
    for (int i = 0; i < array.length; i++) {
        count[array[i] - minVal]++;
    }
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            array[index] = i + minVal;
            index++;
            count[i]--;
        }
    }
}

六、性能测试参考

提供不同数据分布下的排序耗时测试。

public static void order(int[] arr) {
    for (int i = 0; i < arr.length; i++) arr[i] = i;
}

public static void reverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) arr[i] = arr.length - i;
}

public static void disorder(int[] arr) {
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) arr[i] = random.nextInt(100);
}

public static void testSort(int[] arr, String name, Consumer<int[]> sorter) {
    int[] tmpArray = Arrays.copyOf(arr, arr.length);
    long startTime = System.currentTimeMillis();
    sorter.accept(tmpArray);
    long endTime = System.currentTimeMillis();
    System.out.println(name + " 时间：" + (endTime - startTime));
}

注：以上代码假设存在 swap 工具方法及必要的 import 语句。

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