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

一、排序

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

二、常见的排序算法实现

2.1 插入排序

2.1.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

2.1.2 直接插入排序

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。

代码实现：

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();
    }
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.1.3 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：选定一个整数（增量），把待排序文件里的所有记录分成多个组，所有距离为该增量的记录分在同一组内，然后对每一组内的记录进行排序。之后，减小这个增量，重复上述分组和排序的操作。当增量最终变为 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 + " ");
        }
    }
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
4. 稳定性：不稳定

2.2 选择排序

2.2.1 基本思想

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

2.2.2 直接选择排序

在元素集合 array[i]–array[n-1] 中选择关键码最大 (小) 的数据元素。若它不是这组元素中的最后一个 (第一个) 元素，则将它与这组元素中的最后一个（第一个）元素交换。在剩余的 array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。

直接选择排序代码示例：

// 直接选择排序方法
public static void selectionSort(int[] arr) {
    // 数组为空或长度小于 2，无需排序
    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 + " ");
    }
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.2.3 堆排序

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

代码实现：

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

// 二叉树节点类
class TreeNode {
    int value;
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点
    TreeNode 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;

    /**
     * 堆排序主方法
     * @param array 待排序数组
     * @return 排序后的数组
     */
    public int[] sort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        // 1. 构建最大堆
        buildMaxHeap(array);
        // 2. 执行堆排序
        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 + " ");
        }
    }
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1 冒泡排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

代码实现：

/**
 * 基础版冒泡排序
 * 每次遍历将最大元素"浮"到末尾
 */
public static void bubbleSortBasic(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    // 外层循环控制需要进行多少轮比较
    for (int i = 0; i < n - 1; i++) {
        // 内层循环进行每轮的比较和交换
        // 每轮结束后，最大的元素已"浮"到末尾，下一轮可减少一次比较
        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;
            }
        }
    }
}

/**
 * 优化版冒泡排序
 * 添加标志位，当某轮未发生交换时说明数组已有序，可提前结束
 */
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[] testArr1 = {64, 34, 25, 12, 22, 11, 90};
    int[] testArr2 = {5, 1, 4, 2, 8};
    System.out.print("基础版排序前： ");
    printArray(testArr1);
    bubbleSortBasic(testArr1);
    System.out.print("基础版排序后： ");
    printArray(testArr1);
    System.out.print("\n优化版排序前： ");
    printArray(testArr2);
    bubbleSortOptimized(testArr2);
    System.out.print("优化版排序后： ");
    printArray(testArr2);
}

// 辅助方法：打印数组
private static void printArray(int[] arr) {
    for (int num : arr) {
        System.out.print(num + " ");
    }
    System.out.println();
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

2.3.2 快速排序

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

import java.util.Stack;

// 假设按照升序对 array 数组中 [left, right) 区间中的元素进行排序
void QuickSort(int[] array, int left, int right) {
    if (right - left <= 1) {
        return;
    }
    // 按照基准值对 array 数组的 [left, right) 区间中的元素进行划分
    int div = partion(array, left, right);
    // 划分成功后以 div 为边界形成了左右两部分 [left, div) 和 [div+1, right)
    // 递归排 [left, div)
    QuickSort(array, left, div);
    // 递归排 [div+1, right)
    QuickSort(array, div + 1, right);
}

// 辅助方法：交换
private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

// 划分方法：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;
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有：

1. Hoare 版

2. 挖坑法

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--;
        }
        array[i] = array[j];
        while (i < j && array[i] <= pivot) {
            i++;
        }
        array[j] = array[i];
    }
    array[i] = pivot;
    return i;
}

3. 前后指针

写法一：

private static int partition(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, prev, left);
    return prev;
}

写法二：

private static int partition(int[] array, int left, int right) {
    int d = left + 1;
    int pivot = array[left];
    for (int i = left + 1; i <= right; i++) {
        if (array[i] < pivot) {
            swap(array, i, d);
            d++;
        }
    }
    swap(array, d - 1, left);
    return d - 1;
}

快速排序优化

1. 三数取中法选 key
2. 递归到小的子区间时，可以考虑使用插入排序

快速排序非递归

void quickSortNonR(int[] a, int left, int right) {
    Stack<Integer> st = new Stack<>();
    st.push(left);
    st.push(right);
    while (!st.empty()) {
        right = st.pop();
        left = st.pop();
        if (right - left <= 1) continue;
        int div = PartSort1(a, left, right); // 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)
        st.push(div + 1);
        st.push(right);
        st.push(left);
        st.push(div);
    }
}

快速排序总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)

2.4 归并排序

2.4.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：

代码示例：

/**
 * 归并排序主方法
 * @param arr 待排序的数组
 */
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);
}

/**
 * 递归分治排序
 * @param arr 待排序数组
 * @param left 左边界索引
 * @param right 右边界索引
 * @param temp 临时数组
 */
private static void sort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        // 找到中间位置，将数组分为两部分
        int mid = left + (right - left) / 2;
        // 避免直接 (left+right) 可能的溢出
        // 递归排序左半部分
        sort(arr, left, mid, temp);
        // 递归排序右半部分
        sort(arr, mid + 1, right, temp);
        // 合并已排序的两部分
        merge(arr, left, mid, right, temp);
    }
}

/**
 * 合并两个已排序的子数组
 * @param arr 原数组
 * @param left 左子数组起始索引
 * @param mid 中间索引（左子数组结束索引）
 * @param right 右子数组结束索引
 * @param 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("排序前： ");
    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();
}

2.4.2 归并排序总结

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序 前提：内存只有 1G，需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

先把文件切分成 200 份，每个 512 M 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以进行 2 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

三、排序算法复杂度及稳定性分析

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n2)	O(n2)	O(1)	稳定
插入排序	O(n)	O(n2)	O(n2)	O(1)	稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
希尔排序	O(n)	O(n1.3)	O(n2)	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(n2)	O(log(n)) ~ O(n)	不稳定
归并排序	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(n)	稳定

总结

本文介绍了常见的排序算法，通过对代码和原理解释了各个算法的特征，最后介绍了对各种算法的复杂度及稳定性分析。