常见排序算法原理与实现详解

特性总结

• 适用场景：元素集合越接近有序，效率越高。
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳定

2.1.2 希尔排序

希尔排序又称缩小增量法。基本思想是选定一个整数（增量），把待排序文件里的所有记录分成多个组，距离为该增量的记录分在同一组内，对每一组进行排序。之后减小增量，重复操作，直到增量为 1。

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始增量设为数组长度的一半，之后每次减半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                // 对间隔为 gap 的子序列进行直接插入排序
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 54, 2, 26, 9, 17, 5};
        System.out.print("原始数组：");
        for (int num : arr) System.out.print(num + " ");
        shellSort(arr);
        System.out.print("\n排序后的数组：");
        for (int num : arr) System.out.print(num + " ");
    }
}

特性总结

• 是对直接插入排序的优化，通过预排序让数组更接近有序。
• 时间复杂度取决于增量序列，通常优于 O(N^2)。
• 稳定性：不稳定

2.2 选择排序

基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

代码实现

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            // 寻找未排序部分的最小值索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {35, 26, 18, 47, 52, 9, 13};
        System.out.print("排序前：");
        for (int num : array) System.out.print(num + " ");
        selectionSort(array);
        System.out.print("\n排序后：");
        for (int num : array) System.out.print(num + " ");
    }
}

特性总结

• 思考简单，但实际效率不高，较少使用。
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

2.3 堆排序

堆排序利用堆积树（堆）这种数据结构设计，属于选择排序的一种。排升序建大堆，排降序建小堆。

import java.util.*;

class TreeNode {
    int value;
    TreeNode left, right, parent;
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class HeapSortWithTree {
    private TreeNode root;
    private int size;
    private TreeNode lastNode;

    public int[] sort(int[] array) {
        if (array == null || array.length <= 1) return array;
        buildMaxHeap(array);
        int[] result = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            result[i] = extractMax();
        }
        return result;
    }

    private void buildMaxHeap(int[] array) {
        root = null; size = 0; lastNode = null;
        for (int num : array) insert(num);
    }

    private void insert(int value) {
        TreeNode newNode = new TreeNode(value);
        size++;
        if (root == null) {
            root = newNode; lastNode = root;
            return;
        }
        TreeNode parent = findInsertParent();
        if (parent.left == null) parent.left = newNode;
        else parent.right = newNode;
        newNode.parent = parent;
        lastNode = newNode;
        bubbleUp(newNode);
    }

    private TreeNode findInsertParent() {
        List<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.remove(0);
            if (current.left == null || current.right == null) return current;
            queue.add(current.left);
            queue.add(current.right);
        }
        return null;
    }

    private void bubbleUp(TreeNode node) {
        while (node.parent != null && node.value > node.parent.value) {
            int temp = node.value;
            node.value = node.parent.value;
            node.parent.value = temp;
            node = node.parent;
        }
    }

    private void bubbleDown(TreeNode node) {
        while (true) {
            TreeNode largest = node;
            if (node.left != null && node.left.value > largest.value) largest = node.left;
            if (node.right != null && node.right.value > largest.value) largest = node.right;
            if (largest == node) break;
            int temp = node.value;
            node.value = largest.value;
            largest.value = temp;
            node = largest;
        }
    }

    private int extractMax() {
        if (root == null) throw new IllegalStateException("堆为空");
        int maxValue = root.value;
        size--;
        if (size == 0) {
            root = null; lastNode = null;
            return maxValue;
        }
        root.value = lastNode.value;
        TreeNode newLastNode = findNewLastNode();
        if (lastNode.parent != null) {
            if (lastNode.parent.right == lastNode) lastNode.parent.right = null;
            else lastNode.parent.left = null;
        }
        lastNode = newLastNode;
        bubbleDown(root);
        return maxValue;
    }

    private TreeNode findNewLastNode() {
        if (size == 1) return root;
        List<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        TreeNode result = root;
        for (int i = 0; i < size - 1; i++) {
            TreeNode current = queue.remove(0);
            result = current;
            if (current.left != null) queue.add(current.left);
            if (current.right != null) queue.add(current.right);
        }
        return result;
    }

    public static void main(String[] args) {
        HeapSortWithTree heapSort = new HeapSortWithTree();
        int[] array = {14, 10, 8, 7, 9, 3, 2, 4, 1};
        System.out.print("排序前：");
        for (int num : array) System.out.print(num + " ");
        int[] sortedArray = heapSort.sort(array);
        System.out.print("\n排序后：");
        for (int num : sortedArray) System.out.print(num + " ");
    }
}

特性总结

• 利用堆选数，效率较高。
• 时间复杂度：O(N*logN)
• 空间复杂度：O(1)
• 稳定性：不稳定

2.4 交换排序

冒泡排序

通过相邻元素比较和交换，将较大元素向尾部移动。

public class BubbleSort {
    public static void bubbleSortOptimized(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果本轮没有交换，说明已有序，提前结束
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] testArr = {64, 34, 25, 12, 22, 11, 90};
        System.out.print("排序前：");
        printArray(testArr);
        bubbleSortOptimized(testArr);
        System.out.print("排序后：");
        printArray(testArr);
    }

    private static void printArray(int[] arr) {
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }
}

快速排序

快速排序采用分治策略。任取基准值，将序列分割成左小右大的两子序列，递归处理。

分区方式有三种：

1. Hoare 版：双指针从两端向中间扫描。
2. 挖坑法：填补空缺，最后填入基准值。
3. 前后指针：维护小于基准值的区域边界。

public class QuickSort {
    public static void quickSort(int[] array, int left, int right) {
        if (right - left <= 1) return;
        int div = partition(array, left, right);
        quickSort(array, left, div);
        quickSort(array, div + 1, right);
    }

    // Hoare 分区示例
    private static int partition(int[] array, int left, int right) {
        int i = left, j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) j--;
            while (i < j && array[i] <= pivot) i++;
            swap(array, i, j);
        }
        swap(array, i, left);
        return i;
    }

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

    // 非递归实现使用栈模拟
    public static void quickSortNonR(int[] a, int left, int right) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            if (right - left <= 1) continue;
            int div = partition(a, left, right);
            stack.push(div + 1);
            stack.push(right);
            stack.push(left);
            stack.push(div);
        }
    }
}

特性总结

• 综合性能和使用场景较好。
• 时间复杂度：平均 O(N*logN)，最坏 O(N^2)
• 空间复杂度：O(logN) ~ O(N)
• 稳定性：不稳定

2.5 归并排序

归并排序基于分治法，将已有序的子序列合并得到完全有序序列。

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int[] temp = new int[arr.length];
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            sort(arr, left, mid, temp);
            sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, t = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp[t++] = arr[i++];
            else temp[t++] = arr[j++];
        }
        while (i <= mid) temp[t++] = arr[i++];
        while (j <= right) temp[t++] = arr[j++];
        t = 0;
        while (left <= right) arr[left++] = temp[t++];
    }

    public static void main(String[] args) {
        int[] testArr = {12, 11, 13, 5, 6, 7};
        System.out.print("排序前：");
        printArray(testArr);
        mergeSort(testArr);
        System.out.print("排序后：");
        printArray(testArr);
    }

    private static void printArray(int[] arr) {
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }
}

特性总结

• 缺点是需要 O(N) 的空间复杂度。
• 常用于解决磁盘中的外排序问题。
• 时间复杂度：O(N*logN)
• 空间复杂度：O(N)
• 稳定性：稳定

海量数据排序

当内存只有 1G，数据有 100G 时，需采用外部排序。常用方法是先将文件切分，每份在内存中排序，再对有序文件做多路归并。

三、复杂度及稳定性对比