Java 常见排序算法代码分享

本文将分享 Java 中常见的排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序，并提供相关算法的代码示例和分析。

冒泡排序

冒泡排序是一种简单的排序算法。下面是它的基本操作：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对第0个到第n-1个数据进行一次遍历，遍历过程中，不断交换相邻逆序的元素，最终实现的一次遍历是把最大的元素移到了数组的末尾。
3. 对前n-1个元素重复上述步骤，直到整个数组按照从小到大的顺序排列。

冒泡排序的时间复杂度为O(n^2)。

以下是冒泡排序的Java代码示例：

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

选择排序

选择排序的基本思想是：首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置，接着，再从剩余未排序的元素中继续寻找最小的元素，然后放到已排序序列的末尾，直到所有元素均排序完毕。

选择排序的时间复杂度为O(n^2)。

以下是选择排序的Java代码示例：

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

插入排序

插入排序是一种简单的排序算法。基本思想是：将待排序的数据分成两部分，前一部分包含有序的数据，后一部分为无序的数据，从后往前扫描未排序的数据，每次插入一个数，使得前面有序序列仍然有序。

插入排序的时间复杂度为O(n^2)。

以下是插入排序的Java代码示例：

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

希尔排序

希尔排序是插入排序的一种高效率的改进版本，基本思想是分组插入排序，通过设定合适的步长缩小插入排序的范围，达到了优化插入排序的目的。

希尔排序的时间复杂度为O(n(logn)^2)。

以下是希尔排序的Java代码示例：

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

归并排序

归并排序使用分治策略，将待排序序列分为若干个子序列，对每个子序列进行排序，然后合并成一个有序序列，实现整体有序。

归并排序的时间复杂度为O(nlogn)。

以下是归并排序的Java代码示例：

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);
    }
}

public static void merge(int[] arr, 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 (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            k++;
            i++;
        } else {
            temp[k] = arr[j];
            k++;
            j++;
        }
    }
    while (i <= mid) {
        temp[k] = arr[i];
        k++;
        i++;
    }
    while (j <= right) {
        temp[k] = arr[j];
        k++;
        j++;
    }
    for (int m = 0; m < temp.length; m++) {
        arr[left + m] = temp[m];
    }
}

快速排序

通过递归的方式，将数组分成两个子数组。分割的过程是：将一个数组分成两个子数组，使得左子数组的所有元素都小于右子数组的所有元素。

快速排序的时间复杂度为O(nlogn)。

以下是快速排序的Java代码示例：

public static void quickSort(int[] arr, int left, int right){
    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[left];
    int i = left;
    int j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    return i;
}

结语

以上就是Java中常见的排序算法。每种排序算法都有其特点和适用范围，在实际应用中需要根据具体问题来选择合适的算法。