Java中常用的6种排序算法详细分解

在Java中，常用的排序算法主要有六种：冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序。下面将详细讲解这六种算法的原理和实现过程。

冒泡排序

冒泡排序是一种简单的排序算法，它的原理是通过重复地遍历要排序的列表，每遍历一次就把相邻的两个元素比较大小并交换位置。具体实现过程如下：

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

以上代码实现了冒泡排序，时间复杂度为O($n^2$)。

选择排序

选择排序是一种简单的排序算法，它的原理是将列表中的数据分为两个部分，一部分是已排序的，一部分是未排序的。每次遍历未排序的部分，选择其中最小的元素，将其放到已排序的部分的末尾。具体实现如下：

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

以上代码实现了选择排序，时间复杂度为O($n^2$)。

插入排序

插入排序是一种简单的排序算法，它的原理是将一个元素插入到已排序的列表中，并保持已排序的列表依然有序。具体实现如下：

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

以上代码实现了插入排序，时间复杂度为O($n^2$)。

希尔排序

希尔排序是一种高效的排序算法，它是插入排序的改进版本，它将列表分成若干个子序列，对每个子序列进行插入排序，最终整个列表变得有序。具体实现如下：

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

以上代码实现了希尔排序，时间复杂度为O($n$ $\log$ $n$)。

归并排序

归并排序是一种常用的排序算法，它的原理是将列表分成若干个子序列，对每个子序列进行排序，最后整合每个子序列，得到一个有序的列表。具体实现如下：

public static void mergeSort(int[] arr, int left, int right) {
    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 i = left, j = mid + 1, k = 0;
    int[] temp = new int[right - left + 1];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    System.arraycopy(temp, 0, arr, left, temp.length);
}

以上代码实现了归并排序，时间复杂度为O($n$ $\log$ $n$)。

快速排序

快速排序是一种高效的排序算法，它的原理是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，再分别对这两部分数据进行排序。具体实现如下：

public static void quickSort(int[] arr, int left, int right) {
    int i, j, temp, pivot;
    if (left < right) {
        i = left;
        j = right;
        pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

以上代码实现了快速排序，时间复杂度为O($n$ $\log$ $n$)。

示例说明

以归并排序为例，对一个长度为10的整型数组[5, 2, 6, 0, 3, 9, 1, 7, 4, 8]进行排序，具体操作如下：

1. 将数组分为两个子序列[5, 2, 6, 0, 3]和[9, 1, 7, 4, 8]。
2. 对子序列[5, 2, 6, 0, 3]进行归并排序，将它排序成[0, 2, 3, 5, 6]。
3. 对子序列[9, 1, 7, 4, 8]进行归并排序，将它排序成[1, 4, 7, 8, 9]。
4. 将两个已排序的子序列[0, 2, 3, 5, 6]和[1, 4, 7, 8, 9]进行合并，得到一个有序的列表[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

此时，我们已经完成了对给定数组的排序。