Java中的九种常见排序算法解析

在编程的世界里，排序算法就像是厨师的刀具，掌握它们能够让我们处理数据时更加得心应手。今天，我想与大家探讨的主题是Java中的九种常见排序算法。无论你是新手还是有经验的开发者，这些排序方法都能为你在数据处理时提供极大的帮助。

排序算法的基本概念

排序算法就是将一组数据按照一定的顺序进行排列的操作，在计算机科学中，常见的排序顺序有升序和降序。对于大量的数据，优化排序的效率尤为重要，因为这直接影响到程序的性能表现。

1. 冒泡排序

冒泡排序是一种简单的排序算法。通过重复遍历待排序的数列，比较相邻元素并交换它们。它的运行时间复杂度为O(n^2)，适合小规模数据的排序。

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

2. 选择排序

选择排序的思路是每次从未排序的部分中选择最小（或最大）的元素放到已排序序列的末尾。相比冒泡排序，它的交换次数较少，但时间复杂度同样为O(n^2)。

void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3. 插入排序

插入排序适用于少量数据的排序，基本思想是将待排序元素逐个插入到已排序的序列中，直到整个序列有序。时间复杂度同样为O(n^2)，但在数据接近有序时表现较好。

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

4. 快速排序

快速排序是一种分而治之的算法。首先选择一个基准元素，将数组分成两部分，大于基准的放在右边，小于基准的放在左边，然后递归处理这两部分。快速排序的平均时间复杂度为O(n log n)。

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

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

5. 归并排序

归并排序也是一种分而治之的排序算法，先将数组分成小块，然后再合并成有序数组。它的时间复杂度为O(n log n)，而且是稳定的排序算法。

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

void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];
    System.arraycopy(arr, left, L, 0, n1);
    System.arraycopy(arr, mid + 1, R, 0, n2);
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
}

6. 希尔排序

希尔排序是插入排序的泛化，它允许交换不相邻的元素，通过先对序列进行间隔分组进行排序，再逐渐缩小间隔，最终实现整组的有序。它的时间复杂度在O(n log n)到O(n^2)之间。

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

7. 计数排序

计数排序是一种非比较排序算法，适用于元素范围较小的整型序列。它通过统计数组中每个元素出现的次数，依次填充至结果数组。时间复杂度为O(n+k)，k为待排序元素的范围。

void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int num : arr) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]-- > 0) {
            arr[index++] = i;
        }
    }
}

8. 桶排序

桶排序的思路是将数据分到一定的“桶”中，再对每个桶内的数据使用某种排序算法，最后再将各个桶合并。它的效率在于拥有足够随机分布的输入数据，时间复杂度在O(n+k)。

void bucketSort(float[] arr) {
    int n = arr.length;
    if (n <= 0) return;
    @SuppressWarnings("unchecked")
    List[] buckets = new List[n];
    for (int i = 0; i < n; i++) {
        buckets[i] = new ArrayList<>();
    }
    for (float num : arr) {
        int bucketIndex = (int) (num * n);
        buckets[bucketIndex].add(num);
    }
    for (List bucket : buckets) {
        Collections.sort(bucket);
    }
    int index = 0;
    for (List bucket : buckets) {
        for (float num : bucket) {
            arr[index++] = num;
        }
    }
}

9. 基数排序

基数排序是通过将整数按位分割成不同的数字，将相同的数字归到一起，依次进行稳定的排序。它与其他排序算法不同，它的时间复杂度为O(nk)，k为数字的位数。

void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortForRadix(arr, exp);
    }
}

void countingSortForRadix(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    System.arraycopy(output, 0, arr, 0, n);
}

结论

掌握这九种排序方法，无论是处理简单的数据，还是面对复杂的场景，你都会发现自己更得心应手。选择合适的排序算法，不仅能够提高代码的运行效率，也能优化程序的性能。对于初学者来说，这些算法的实现也是一个很好的练习机会，可以帮助我们加深对数据结构与算法的理解。