Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

Java各种排序算法汇总

本文将详细讲解Java中常见的各种排序算法，包括冒泡排序、选择排序、归并排序、希尔排序、堆排序等，以及他们的实现代码和时间复杂度分析。

冒泡排序

冒泡排序是一种基础的排序算法，核心思想是将相邻的元素两两比较，将较大的元素向后移动。代码如下：

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

时间复杂度为O(n^2)，不适用于大量数据的排序。

选择排序

选择排序的核心思想是每次选择一个最小/最大的元素，在未排序的元素中寻找最小/最大的元素，将其放置于序列起始位置。代码如下：

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

时间复杂度为O(n^2)，比较次数与冒泡排序相同，但是交换次数会减少。

归并排序

归并排序是一种基于分治思想的排序算法，核心思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后合并子序列成一个整体有序的序列。代码如下：

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

public static void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = array[i++];
    }
    while (j <= right) {
        temp[k++] = array[j++];
    }
    System.arraycopy(temp, 0, array, left, temp.length);
}

时间复杂度为O(nlogn)，稳定性好，但是需要使用额外的空间。

希尔排序

希尔排序是一种基于插入排序的排序算法，核心思想是将待排序的序列分成若干个增量序列，对每个增量序列进行插入排序，最后当增量为1时，整个序列排成一个有序序列。代码如下：

public static void shellSort(int[] array) {
    int gap = array.length / 2;
    while (gap > 0) {
        for (int i = gap; i < array.length; i++) {
            int j = i;
            int temp = array[j];
            if (array[j] < array[j - gap]) {
                while (j - gap >= 0 && temp < array[j - gap]) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                array[j] = temp;
            }
        }
        gap = gap / 2;
    }
}

时间复杂度比较复杂，平均情况下为O(nlogn)。

堆排序

堆排序是一种基于完全二叉树结构的排序算法，核心思想是将待排序的元素构建成一个堆，然后依次取出堆顶元素，加入有序序列中。代码如下：

public static void heapSort(int[] array) {
    int len = array.length - 1;
    for (int i = len / 2; i >= 0; i--) {
        heapAdjust(array, i, len);
    }
    for (int i = len; i > 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        heapAdjust(array, 0, i - 1);
    }
}

public static void heapAdjust(int[] array, int parent, int len) {
    int temp = array[parent];
    int child = 2 * parent + 1;
    while (child <= len) {
        if (child + 1 <= len && array[child] < array[child + 1]) {
            child++;
        }
        if (temp >= array[child]) {
            break;
        } else {
            array[parent] = array[child];
            parent = child;
            child = 2 * parent + 1;
        }
    }
    array[parent] = temp;
}

时间复杂度为O(nlogn)，不稳定。

示例说明

例如，我们有一个待排序的数组：

int[] array = new int[]{4, 9, 8, 3, 5, 1, 6, 2, 7};

如果我们希望对这个数组进行归并排序，我们可以使用以下代码：

MergeSort.mergeSort(array, 0, array.length - 1);

最终得到的有序数组如下：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

再例如，如果我们希望对一个包含大量元素的数组进行排序，我们可以选择堆排序算法，通过以下代码实现：

int[] array = new int[100000];
for (int i = 0; i < 100000; i++) {
    array[i] = (int) (Math.random() * 100000);
}
HeapSort.heapSort(array);

以上代码将产生包含100000个随机元素的数组，然后使用堆排序算法进行排序。