一文带你了解Java排序算法

在计算机科学中，排序算法是一种将一组数据按照特定规则进行排列的过程。Java中提供了多种排序算法实现，本文将为您介绍常见的排序算法及其实现方式。

冒泡排序

冒泡排序是一种基本的排序算法，通过重复遍历要排序的列表来比较相邻的两个元素，如果顺序错误，则进行交换，直到没有任何交换发生为止。

public static void bubbleSort(int[] arr) {
    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;
            }
        }
    }
}

快速排序

快速排序是一种高效的排序算法，也是基于比较的排序算法。它通过将一个序列分成两个子序列来递归地进行排序，直到序列被分为长度为1的子序列为止。

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int left, int right) {
    int i, j, base, temp;
    if (left > right) {
        return;
    }
    i = left;
    j = right;
    // 取左侧的值作为基准
    base = arr[left];
    while (i < j) {
        while (arr[j] >= base && i < j) {
            j--;
        }
        while (arr[i] <= base && i < j) {
            i++;
        }
        if (i < j) {
            // 交换位置
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准值归位
    arr[left] = arr[i];
    arr[i] = base;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

选择排序

选择排序是另外一种简单的排序算法，基本思想是从未排序的部分中选出最小的元素，并将其放在已排序的末尾位置。

public static void selectionSort(int[] arr) {
    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;
            }
        }
        // 交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

插入排序

插入排序是一种简单的排序算法，基本思想是将未排序的元素逐个插入到已排序的序列中。插入排序通常是在小的序列上做的最好的，或者数据在初始状态下几乎被排好序了。

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

总结

在本文中，我们介绍了四种排序算法：冒泡排序、快速排序、选择排序和插入排序。以上四种排序算法都是常见的基本排序算法，它们的实现方法并不太难，但是它们的区别很重要。在不同的情况下，它们的性能可能会有所不同，因此，我们应该在需要使用排序时，选择最适合我们需求的排序算法来进行操作。