原地排序

1. 原地排序的基本概念

1.1 什么是原地排序？

原地排序是一种排序算法，它在排序过程中只使用常数级别的额外空间。换句话说，原地排序算法在排序过程中不需要额外的存储空间来保存数据副本，只需要原始数据的空间来进行排序操作。因此，原地排序的空间复杂度为 O(1)。

常见的原地排序算法包括冒泡排序、选择排序、插入排序等，它们在排序过程中只依赖于输入数据数组本身，而不需要开辟新的数组来保存临时的结果。

1.2 原地排序的特点

空间复杂度 O(1)：原地排序不需要额外的内存空间，所有操作都在原始数组上进行。
高效性：原地排序算法在空间利用上非常高效，适用于内存有限的场景。
不稳定性：许多原地排序算法，如选择排序，可能会改变相同元素的相对顺序，因此它们是不稳定排序。但是，像冒泡排序和插入排序也有可以通过改进保持稳定性的实现。

1.3 原地排序与非原地排序的对比

原地排序：排序过程中不使用额外的存储空间，所有的操作都在原始数据上进行。常见的原地排序算法包括选择排序、插入排序、冒泡排序等。
非原地排序：排序过程中会使用额外的空间来存储临时数据，常见的非原地排序算法有归并排序和快速排序的某些实现。

原地排序的优点在于它不需要额外的内存开销，适合处理大型数据集，但通常会在时间复杂度上做出一些妥协，特别是在排序效率较低的情况下。

2. 常见的原地排序算法

2.1 选择排序

选择排序是一种典型的原地排序算法，其基本思想是每一轮从待排序部分选择最小（或最大）的元素，并将其与当前的元素交换位置。

选择排序的 Java 实现代码

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        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 printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("排序前：");
        printArray(arr);
        selectionSort(arr);
        System.out.println("排序后：");
        printArray(arr);
    }
}

代码注释：

外层循环：控制每次选择最小值的位置。
内层循环：遍历当前未排序的部分，找出最小值。
交换操作：如果最小值的位置发生变化，就将最小值与当前位置交换，完成一轮排序。
时间复杂度：选择排序的时间复杂度为 O(n²)，由于内外两层循环。
空间复杂度：空间复杂度为 O(1)，因为它不需要额外的空间来存储数据。

2.2 冒泡排序

冒泡排序是另一个常见的原地排序算法。它通过不断交换相邻元素，使得较大的元素逐渐“冒泡”到数组的末尾。

冒泡排序的 Java 实现代码

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        boolean swapped;  // 标记是否发生过交换
        // 外层循环，控制排序的轮数
        for (int i = 0; i < arr.length - 1; i++) {
            swapped = false;
            // 内层循环，进行相邻元素的比较和交换
            for (int j = 0; j < arr.length - 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 printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

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

代码注释：

外层循环：每一轮通过内层循环将最大元素“冒泡”到末尾。
内层循环：逐一比较相邻元素并交换，直到没有交换发生。
优化：通过 swapped 变量来判断是否发生了交换，如果没有交换则提前结束排序。
时间复杂度：最坏和平均情况下，时间复杂度为 O(n²)，最佳情况下（数组已排序），时间复杂度为 O(n)。
空间复杂度：空间复杂度为 O(1)，因为所有操作都在原数组上进行。

2.3 插入排序

插入排序是一种简单的原地排序算法，它通过将当前元素插入到已经排好序的部分中，逐步完成排序。

插入排序的 Java 实现代码

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将大于 key 的元素逐个移到右边
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 插入 key 到正确位置
            arr[j + 1] = key;
        }
    }

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

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