Java集合排序详解

一、选择排序

选择排序（Selection sort）是一种简单直观的排序算法，其基本思想是：首先在序列中找到最小值，然后将其放到序列的起始位置；接着再从剩余未排序的元素中继续寻找最小值，然后放到已排序序列的末尾。以此类推，直到所有的元素都排完为止。下面是该排序算法的代码实现：

public static void selectionSort(Integer[] 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)，是一种较慢的排序算法。

二、冒泡排序

冒泡排序（Bubble sort）是一种简单直观的排序算法，其基本思想是：依次比较相邻两个元素的大小关系，如果顺序不对，则进行交换。一次排序可以让最大的元素浮到序列的末尾；接着继续进行下一轮排序，直到排序完成。下面是该排序算法的代码实现：

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

冒泡排序的时间复杂度是O(n^2)，也是一种较慢的排序算法。

三、插入排序

插入排序（Insertion sort）是一种简单直观的排序算法，其基本思想是：将一个元素插入到已经排好序的序列中，使得插入后仍然有序。插入排序的实现通常采用就地排序的方法，即在原数组上进行操作，不需要额外的存储空间。下面是该排序算法的代码实现：

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

插入排序的时间复杂度是O(n^2)，但在序列基本有序的情况下，插入排序的效率非常高。

四、快速排序

快速排序（Quick sort）是一种高效的排序算法，其基本思想是：选择一个元素作为基准值，将序列中小于基准值的元素放到基准值的左边，将大于基准值的元素放到基准值的右边。然后对左右两个子序列分别进行快速排序，直到整个序列有序。下面是该排序算法的代码实现：

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

快速排序的时间复杂度平均情况下是O(nlogn)，最坏情况下是O(n^2)。

五、归并排序

归并排序（Merge sort）是一种高效的排序算法，其基本思想是：将序列分成两个子序列，分别对子序列进行排序，然后将排好序的子序列合并成一个有序的序列。归并排序使用了分治的思想，以递归方式实现。下面是该排序算法的代码实现：

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

public static void merge(Integer[] arr, int left, int middle, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = middle + 1, k = 0;
    while (i <= middle && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= middle) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

归并排序的时间复杂度是O(nlogn)，但实现比较复杂，需要额外的存储空间。

原创文章，作者：BKLCT，如若转载，请注明出处：https://www.506064.com/n/361586.html