Java之经典排序算法

本文将详细讲解 Java 中常见的经典排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序等七种算法，并给出示例代码。

冒泡排序

冒泡排序是最简单的排序算法之一，基本思想是将相邻的元素两两比较，如果前一个元素比后一个元素大，就将它们两者交换位置。重复这个过程，直到整个序列有序为止。

下面是 Java 实现代码：

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

选择排序

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

下面是 Java 实现代码：

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    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;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

插入排序

插入排序的基本思想是将待排序的元素按大小插入到已排序好的部分元素中。

下面是 Java 实现代码：

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int n = arr.length;
    int preIndex, current;
    for (int i = 1; i < n; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

希尔排序

希尔排序是插入排序的一种高效率改进版本。基本思想是将数组分成若干长度为 gap 的子序列，然后对每个子序列进行插入排序，最后合并成一个完整的序列。

下面是 Java 实现代码：

public static void shellSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int j = i;
            int current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = current;
        }
        gap /= 2;
    }
}

归并排序

归并排序是一种分治思想的排序算法，它将原始序列分为若干个子序列，分别进行排序，然后将排好序的子序列合并成一个完整的有序序列。

下面是 Java 实现代码：

public static void mergeSort(int[] arr, int left, int right) {
    if (arr == null || arr.length == 0) {
        return;
    }
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    for (int p = 0; p < tmp.length; p++) {
        arr[left + p] = tmp[p];
    }
}

快速排序

快速排序是一种分治思想的排序算法，通过一趟排序将要排序的数列分成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，再对这两部分数据分别进行快速排序。

下面是 Java 实现代码：

public static void quickSort(int[] arr, int left, int right) {
    if (arr == null || arr.length == 0) {
        return;
    }
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; 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[right];
    arr[right] = temp;
    return i + 1;
}

堆排序

堆排序是一种树形选择排序算法，它利用了堆这种数据结构的特点进行排序，构造一个堆，将要排序的序列放在堆中，然后进行排序。

下面是 Java 实现代码：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        adjustHeap(arr, 0, i);
    }
}

private static void adjustHeap(int[] arr, int i, int length) {
    int temp = arr[i];
    for (int j = 2 * i + 1; j < length; j = j * 2 + 1) {
        if (j + 1 < length && arr[j] < arr[j + 1]) {
            j++;
        }
        if (arr[j] > temp) {
            arr[i] = arr[j];
            i = j;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

示例说明

以冒泡排序和快速排序为例，给出示例以说明排序过程。

假设要排序的数组为：

{6, 3, 8, 2, 9, 1}

冒泡排序示例

第一次排序：

[3, 6] [8, 2] [9, 1]

第二次排序：

[3, 2, 6] [8, 1, 9]

第三次排序：

[2, 3, 6, 1, 8, 9]

第四次排序：

[2, 3, 1, 6, 8, 9]

第五次排序：

[2, 1, 3, 6, 8, 9]

第六次排序：

[1, 2, 3, 6, 8, 9]

快速排序示例

以中间数 8 为枢轴进行快速排序，排序过程如下：

left=0, right=5, pivotIndex=2

[3, 6, 1, 2, 9, 8]

left=0, right=1, pivotIndex=0

[3, 6, 1, 2, 9, 8]

left=3, right=5, pivotIndex=5

[3, 6, 1, 2, 8, 9]

left=3, right=4, pivotIndex=3

[3, 2, 1, 6, 8, 9]

left=0, right=2, pivotIndex=1

[2, 3, 1, 6, 8, 9]

left=0, right=0, pivotIndex=0

[2, 3, 1, 6, 8, 9]

left=4, right=5, pivotIndex=5

[2, 3, 1, 6, 8, 9]

left=4, right=4, pivotIndex=4

[2, 3, 1, 6, 8, 9]

left=2, right=3, pivotIndex=2

[1, 3, 2, 6, 8, 9]

left=2, right=1, pivotIndex=2

[1, 3, 2, 6, 8, 9]

经过上述操作，排序完成，最终数组为：

{1, 2, 3, 6, 8, 9}

这就是冒泡排序和快速排序两种算法的基本思想、示例和 Java 实现代码。

阅读剩余 85%