算法-排序算法

在 Java 中，常见的排序算法包括 冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、希尔排序、计数排序、桶排序、基数排序 等。下面分别给出这些排序算法的 Java 实现，并附上简要说明。

一、冒泡排序（Bubble Sort）

public static 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]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定

二、选择排序（Selection Sort）

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

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

三、插入排序（Insertion Sort）

public static 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;
    }
}

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定

四、快速排序（Quick Sort）

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

• 时间复杂度：平均 O(n log n)，最坏 O(n²)
• 空间复杂度：O(log n)
• 稳定性：不稳定

五、归并排序（Merge Sort）

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    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[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    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)
• 空间复杂度：O(n)
• 稳定性：稳定

六、堆排序（Heap Sort）

public static void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

七、希尔排序（Shell Sort）

public static 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 = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

• 时间复杂度：O(n log n) ~ O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

八、计数排序（Counting Sort）

public static 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;
        }
    }
}

• 时间复杂度：O(n + k)，k 为数据范围
• 空间复杂度：O(k)
• 稳定性：稳定

九、桶排序（Bucket Sort）

public static void bucketSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int bucketCount = (max - min) / arr.length + 1;
    List<List<Integer>> buckets = new ArrayList<>(bucketCount);

    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }

    for (int num : arr) {
        int index = (num - min) / arr.length;
        buckets.get(index).add(num);
    }

    int index = 0;
    for (List<Integer> bucket : buckets) {
        Collections.sort(bucket);
        for (int num : bucket) {
            arr[index++] = num;
        }
    }
}

• 时间复杂度：O(n + k) ~ O(n²)
• 空间复杂度：O(n + k)
• 稳定性：稳定

十、基数排序（Radix Sort）

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

private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int num : arr) {
        count[(num / 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);
}

• 时间复杂度：O(n * k)，k 为最大数的位数
• 空间复杂度：O(n + k)
• 稳定性：稳定

十一、排序算法对比表

十二、总结

• 通用排序：快速排序、归并排序、堆排序（时间复杂度 O(n log n)）
• 小数据量排序：插入排序、冒泡排序、选择排序
• 非比较排序：计数排序、桶排序、基数排序（适合整数或有限范围数据）
• 稳定性要求高：归并排序、插入排序、计数排序等
• 空间要求低：原地排序算法（如快排、堆排序）

可以根据具体场景选择合适的排序算法。在实际开发中，Java 的 Arrays.sort() 已经对各种类型做了优化，推荐优先使用。