Java 经典排序算法全解析 | 极客日志

Javajava算法

Java 经典排序算法全解析

Java 排序算法涵盖插入、希尔、选择、堆、冒泡、快速、归及非比较排序。文章详解各算法原理、代码实现及性能对比，包含三数取中、非递归快排等优化方案，适用于不同数据规模与稳定性需求场景。

蜜桃汽水发布于 2026/2/13更新于 2026/4/251 浏览

Java 经典排序算法全解析

排序基础

在深入具体算法之前，先明确几个核心概念。稳定的排序是指排序前后相同元素的相对顺序不变；内部排序指数据完全在内存中完成；外部排序则涉及磁盘等外部存储，通常用于海量数据。

插入排序

核心思路是假设第一个元素已有序，从第二个元素开始，将其与前面已排序的元素比较，找到合适位置插入。当待排序数组基本有序时，效率极高。

public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int j = i - 1;
        int tmp = array[i];
        for (; j >= 0; j--) {
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = tmp;
    }
}

性能分析：

时间复杂度：O(N^2)，最好情况（已有序）为 O(N)。
空间复杂度：O(1)。
稳定性：稳定。

希尔排序

这是对直接插入排序的优化。通过分组缩小增量，让较大的元素快速后移，较小的元素快速前移。最后将整体视为一组进行插入，此时序列已基本有序，效率接近 O(N)。

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

private static   {
     (   gap; i < array.length; i++) {
           i - gap;
           array[i];
         (; j >= ; j -= gap) {
             (array[j] > tmp) {
                array[j + gap] = array[j];
            }  {
                ;
            }
        }
        array[j + gap] = tmp;
    }
}

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

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

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

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

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

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

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

private static void quick(int[] array, int start, int end) {
    if (start >= end) return;
    int pivot = partitionHoare(array, start, end);
    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}

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

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

// 优化后的快排
private static void quickOptimized(int[] array, int start, int end) {
    if (start >= end) return;
    if (end - start + 1 <= 15) {
        insertSort(array, start, end);
        return;
    }
    int index = middleNum(array, start, end);
    swap(index, start, array);
    int pivot = partitionHoare(array, start, end);
    quickOptimized(array, start, pivot - 1);
    quickOptimized(array, pivot + 1, end);
}

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

private static void merge(int[] array, int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    merge(array, start, mid);
    merge(array, mid + 1, end);
    mergeHeB(array, start, mid, end);
}

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

public static void countSort(int[] array) {
    int minVal = array[0], maxVal = array[0];
    for (int x : array) {
        if (x < minVal) minVal = x;
        if (x > maxVal) maxVal = x;
    }
    int len = maxVal - minVal + 1;
    int[] count = new int[len];
    for (int x : array) count[x - minVal]++;
    
    int k = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            array[k++] = i + minVal;
            count[i]--;
        }
    }
}