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

排序算法详解

一、排序基础概念

1.1 基本概念

排序是指将一串记录按照某个或某些关键字的大小，递增或递减排列的操作。

稳定性：假设待排序序列中存在多个相同关键字的记录。若排序后这些记录的相对次序保持不变（即原序列中 r[i] 在 r[j] 之前，排序后仍在之前），则称该算法稳定；否则不稳定。

内部排序：数据元素全部存放在内存中进行排序。 外部排序：数据量过大无法全部放入内存，需借助外存辅助的排序过程。

1.2 常见算法概览

常见的排序算法包括插入排序、选择排序、交换排序、归并排序等。不同算法在时间复杂度、空间复杂度和稳定性上各有优劣，适用于不同的场景。

二、常见排序算法实现

2.1 插入排序

基本思想

直接插入排序是一种简单的插入排序法。其核心是将待排序记录按其关键码值逐个插入到一个已排好序的有序序列中，直到所有记录插入完毕。

代码实现

public class InsertionSort {
    /**
     * 直接插入排序算法
     * @param arr 待排序的数组
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 从第二个元素开始遍历，第一个元素默认已排序
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将大于 key 的元素向后移动一位
            while (j >= 0 && key < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 将 key 插入到正确位置
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] testArr = {32, 26, 87, 72, 26, 17};
        System.out.print("原始序列：");
        printArray(testArr);
        insertionSort(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^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 时，需采用外部排序。常用方法是先将文件切分，每份在内存中排序，再对有序文件做多路归并。

三、复杂度及稳定性对比

排序方法	最好情况	平均情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
希尔排序	O(n)	O(n^1.3)	O(n²)	O(1)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定