常见排序算法及其java实现

以下是常见的排序算法及其 ​​Java 实现​​，包括 ​​时间复杂度、空间复杂度、稳定性​​ 分析，并附上代码示例。

一、冒泡排序（Bubble Sort）​

原理​​：重复比较相邻元素，较大的元素逐步“冒泡”到数组末尾。
时间复杂度​​：

• 最好情况（已有序）：​​O(n)​​
• 平均和最坏情况：​​O(n²)​​

​​空间复杂度​​：​​O(1)​​（原地排序）
​​稳定性​​：​​稳定​​（相同元素相对位置不变）

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean 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; // 提前终止
    }
}

二、选择排序（Selection Sort）​​ ​​

原理​​：每次选择未排序部分的最小元素，放到已排序部分的末尾。
​​时间复杂度​​：​​O(n²)​​（无论数据是否有序）
​​空间复杂度​​：​​O(1)​​
​​稳定性​​：​​不稳定​​（可能破坏相同元素的顺序） ​​

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}   

三、插入排序（Insertion Sort）​​

​​原理​​：将未排序元素逐个插入到已排序部分的正确位置。
​​时间复杂度​​：

• 最好情况（已有序）：​​O(n)​​
• 平均和最坏情况：​​O(n²)​​

​​空间复杂度​​：​​O(1)​​
​​稳定性​​：​​稳定​​ ​​

public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 后移
            j--;
        }
        arr[j + 1] = key; // 插入
    }
}          ​​

四、快速排序（Quick Sort）​​ ​​

原理​​：分治思想，选择一个基准（pivot），将数组分为小于基准和大于基准的两部分，递归排序。
​​时间复杂度​​：

• 平均情况：​​O(n log n)​​
• 最坏情况（如数组已有序）：​​O(n²)​​（可通过随机化基准避免）

​​空间复杂度​​：​​O(log n)​​（递归栈开销）
​​稳定性​​：​​不稳定​​ ​​

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 把基准放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}  

五、归并排序（Merge Sort）​​ ​​

原理​​：分治思想，将数组分为两半，分别排序后合并。
​​时间复杂度​​：​​O(n log n)​​（所有情况）
​​空间复杂度​​：​​O(n)​​（需要额外数组）
​​稳定性​​：​​稳定​​

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    // 合并
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 处理剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}  

六、堆排序（Heap Sort）​

​​原理​​：利用堆数据结构（大顶堆/小顶堆）进行排序。
​​时间复杂度​​：​​O(n log n)​​（所有情况）
​​空间复杂度​​：​​O(1)​​（原地排序）
​​稳定性​​：​​不稳定

public void heapSort(int[] arr) {
    int n = arr.length;

    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 逐个提取堆顶元素
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶和最后一个元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 调整堆
        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 左子节点比根大
    if (left < n && arr[left] > arr[largest]) largest = left;

    // 右子节点比根大
    if (right < n && arr[right] > arr[largest]) largest = right;

    // 如果最大值不是根节点，交换并继续调整
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

总结​​

推荐选择​​：

• ​​小规模数据​​：插入排序（稳定）或冒泡排序（简单）。
• ​大规模数据​​：快速排序（最快）、归并排序（稳定）、堆排序（原地排序）。