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

特性总结：

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

2.1.2 希尔排序

希尔排序是对直接插入排序的优化，又称缩小增量法。它先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录'基本有序'时，再对全体记录进行一次直接插入排序。

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("原始数组：" + java.util.Arrays.toString(arr));
        shellSort(arr);
        System.out.println("\n排序后的数组：" + java.util.Arrays.toString(arr));
    }
}

特性总结：

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

2.2 选择排序

2.2.1 直接选择排序

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

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("排序前：" + java.util.Arrays.toString(array));
        selectionSort(array);
        System.out.println("\n排序后：" + java.util.Arrays.toString(array));
    }
}

特性总结：

• 逻辑简单，但效率一般，实际使用较少。
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 不稳定排序。

2.2.2 堆排序

堆排序利用堆这种数据结构设计，属于选择排序的一种。排升序建大堆，排降序建小堆。这里展示一种基于树结构的实现方式，便于理解堆的性质。

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

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("排序前：" + java.util.Arrays.toString(array));
        int[] sortedArray = heapSort.sort(array);
        System.out.println("\n排序后：" + java.util.Arrays.toString(sortedArray));
    }
}

特性总结：

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

2.3 交换排序

2.3.1 冒泡排序

通过重复走访要排序的数列，一次比较两个元素，如果顺序错误就交换过来。较大的元素会像气泡一样逐渐浮到末尾。

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("排序前：" + java.util.Arrays.toString(testArr));
        bubbleSortOptimized(testArr);
        System.out.println("\n排序后：" + java.util.Arrays.toString(testArr));
    }
}

特性总结：

• 易于理解，适合教学。
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定排序。

2.3.2 快速排序

快速排序是分治法的典型应用。任取基准值，将小于基准值的放左边，大于的放右边，然后递归处理左右子序列。

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;
        int 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 main(String[] args) {
        int[] array = {3, 2, 1, 5, 4};
        System.out.print("排序前：" + java.util.Arrays.toString(array));
        quickSort(array, 0, array.length);
        System.out.println("\n排序后：" + java.util.Arrays.toString(array));
    }
}

优化策略：

1. 三数取中：避免基准值极端化导致性能下降。
2. 小区间插入排序：当区间较小时，切换为插入排序效率更高。
3. 非递归实现：使用栈模拟递归过程，防止栈溢出。

特性总结：

• 综合性能最好，实际应用广泛。
• 平均时间复杂度：O(N*logN)
• 最坏情况：O(N^2)
• 不稳定排序。

2.4 归并排序

归并排序采用分治法，将已有序的子序列合并，得到完全有序的序列。核心在于'分'与'治'。

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;
        int j = mid + 1;
        int 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("排序前：" + java.util.Arrays.toString(testArr));
        mergeSort(testArr);
        System.out.println("\n排序后：" + java.util.Arrays.toString(testArr));
    }
}

海量数据处理： 当数据量超过内存限制（如 100G 数据只有 1G 内存），外部排序成为必要。归并排序是最常用的外部排序方案：先将文件切分，内存排序后写回磁盘，最后进行多路归并。

特性总结：

• 缺点是需要 O(N) 的空间复杂度。
• 时间复杂度：O(N*logN)
• 空间复杂度：O(N)
• 稳定排序。

三、排序算法复杂度及稳定性对比

四、总结

排序是计算机科学中最基础也最重要的操作之一。不同的场景需要选择不同的算法：

• 小规模数据：插入排序往往表现不错，且稳定。
• 大规模随机数据：快速排序通常是首选，速度最快。
• 对稳定性有要求：归并排序或插入排序是更好的选择。
• 内存受限：堆排序和原地快速排序更合适。

掌握这些算法的核心思想与实现细节，能帮助你更好地应对实际开发中的性能挑战。