正文

Java常见排序算法解析及空间复杂度全揭秘

/0 浏览量
0624

在Java编程中，排序算法是非常基础且重要的内容。高效的排序算法不仅可以优化程序的性能，还能使数据结构更加清晰。本文将解析Java中常见的排序算法，并深入探讨它们的空间复杂度。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地遍历待排序的列表，比较每对相邻的项，并在必要时交换它们的位置。这个过程一直重复，直到没有再需要交换的元素，也就是该列表已经排序完成。

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

冒泡排序的空间复杂度为O(1)，因为它在原地进行排序，不需要额外的存储空间。

2. 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

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

选择排序的空间复杂度也是O(1)。

3. 插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public void insertionSort(int[] array) {
    int n = array.length;
    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

插入排序的空间复杂度同样是O(1)。

4. 快速排序（Quick Sort）

快速排序是一种非常高效的排序算法。它采用分而治之的策略，将原始数组分成较小的数组和较大的数组，并对这两个数组分别进行快速排序。

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

private int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
}

快速排序的平均空间复杂度为O(log n)，但在最坏情况下，空间复杂度为O(n)。

5. 归并排序（Merge Sort）

归并排序是一种分而治之的算法。它将原始数组分成两半，递归地对它们进行排序，然后将结果合并成一个有序数组。

public void mergeSort(int[] array, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, low, mid, high);
    }
}

private void merge(int[] array, int low, int mid, int high) {
    int[] leftArray = new int[mid - low + 1];
    int[] rightArray = new int[high - mid];
    for (int i = 0; i < leftArray.length; i++) {
        leftArray[i] = array[low + i];
    }
    for (int j = 0; j < rightArray.length; j++) {
        rightArray[j] = array[mid + 1 + j];
    }
    int i = 0, j = 0, k = low;
    while (i < leftArray.length && j < rightArray.length) {
        if (leftArray[i] <= rightArray[j]) {
            array[k] = leftArray[i];
            i++;
        } else {
            array[k] = rightArray[j];
            j++;
        }
        k++;
    }
    while (i < leftArray.length) {
        array[k] = leftArray[i];
        i++;
        k++;
    }
    while (j < rightArray.length) {
        array[k] = rightArray[j];
        j++;
        k++;
    }
}

归并排序的空间复杂度为O(n)。

总结

以上就是Java中常见的几种排序算法及其空间复杂度的解析。每种排序算法都有其特点和适用场景，了解它们的优缺点可以帮助我们在实际开发中做出更明智的选择。

-- 展开阅读全文 --