Java实现十大经典排序算法详解

本文全面讲解十大经典排序算法的实现原理，并提供完整的Java代码实现。每种算法的时间复杂度、空间复杂度和稳定性分析见文末总结表格。

一、冒泡排序（Bubble Sort）

算法逻辑：

1. 依次比较相邻元素，前大后小则交换
2. 每轮遍历将最大值冒泡到末尾
3. 重复n-1轮完成排序

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]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

二、选择排序（Selection Sort）

算法逻辑：

1. 在未排序序列中找到最小元素
2. 与序列起始位置元素交换
3. 重复上述过程直到排序完成

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;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

三、插入排序（Insertion Sort）

算法逻辑：

1. 将第一个元素视为已排序序列
2. 取出下一个元素，在已排序序列中从后向前扫描
3. 找到相应位置插入元素
4. 重复步骤2-3

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

四、希尔排序（Shell Sort）

算法逻辑：

1. 定义增量序列（本文使用gap/2）
2. 按增量分组进行插入排序
3. 逐步缩小增量直至1

public static void shellSort(int[] arr) {
    for(int gap=arr.length/2; gap>0; gap/=2) {
        for(int i=gap; i<arr.length; 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;
        }
    }
}

五、归并排序（Merge Sort）

算法逻辑：

1. 将数组递归分成两半
2. 对子数组进行排序
3. 合并两个有序子数组

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int[] temp = new int[arr.length]; // 临时数组用于合并操作
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(int[] arr, int low, int high, int[] temp) {
        if (low >= high) return; // 递归终止条件
        
        int mid = low + (high - low) / 2; // 防止整数溢出
        sort(arr, low, mid, temp);      // 递归排序左半部分
        sort(arr, mid + 1, high, temp); // 递归排序右半部分
        merge(arr, low, mid, high, temp); // 合并两个有序区间
    }

    private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
        int i = low;    // 左区间起始指针
        int j = mid + 1; // 右区间起始指针
        int t = 0;      // 临时数组指针

        // 合并两个有序区间到临时数组
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }

        // 处理剩余元素
        while (i <= mid) temp[t++] = arr[i++];
        while (j <= high) temp[t++] = arr[j++];

        // 将临时数组数据拷贝回原数组
        t = 0;
        while (low <= high) {
            arr[low++] = temp[t++];
        }
    }

    public static void main(String[] args) {
        // 测试用例
        int[] arr1 = {8, 4, 5, 7, 1, 3, 6, 2};
        mergeSort(arr1);
        System.out.println("排序结果 1: " + Arrays.toString(arr1)); // [1,2,3,4,5,6,7,8]

        int[] arr2 = {5};
        mergeSort(arr2);
        System.out.println("排序结果 2: " + Arrays.toString(arr2)); // [5]

        int[] arr3 = {};
        mergeSort(arr3);
        System.out.println("排序结果 3: " + Arrays.toString(arr3)); // []

        int[] arr4 = {9, 9, 4, 4, 2};
        mergeSort(arr4);
        System.out.println("排序结果 4: " + Arrays.toString(arr4)); // [2,4,4,9,9]

        int[] arr5 = {1, 2, 3, 4, 5};
        mergeSort(arr5);
        System.out.println("排序结果 5: " + Arrays.toString(arr5)); // [1,2,3,4,5]

        int[] arr6 = {5, 4, 3, 2, 1};
        mergeSort(arr6);
        System.out.println("排序结果 6: " + Arrays.toString(arr6)); // [1,2,3,4,5]
    }
}

六、快速排序（Quick Sort）

算法逻辑：

1. 选取基准元素（pivot）
2. 将数组分为小于和大于基准的两部分
3. 递归排序子数组

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

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

private static int partition(int[] arr, int low, int high) {
    // 分区实现代码（详见完整代码）
}

七、堆排序（Heap Sort）

算法逻辑：

1. 构建最大堆
2. 将堆顶元素与末尾元素交换
3. 调整堆结构
4. 重复步骤2-3

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 1. 构建最大堆（从最后一个非叶子节点开始调整）
        int n = arr.length;
        for (int i = n/2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 逐个提取堆顶元素（最大值）
        for (int i = n-1; i >= 0; i--) {
            // 将当前堆顶（最大值）移到数组末尾
            swap(arr, 0, i);
            // 调整剩余元素重建最大堆（堆大小减1）
            heapify(arr, i, 0);
        }
    }

    // 调整以节点i为根的子树为最大堆
    private static void heapify(int[] arr, int heapSize, int i) {
        int largest = i;       // 初始化最大元素为当前根节点
        int left = 2 * i + 1;  // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引

        // 比较左子节点与当前最大值
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }

        // 比较右子节点与当前最大值
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点，则交换并递归调整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, heapSize, largest);
        }
    }

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

    public static void main(String[] args) {
        // 测试用例
        int[] arr1 = {4, 10, 3, 5, 1};
        heapSort(arr1);
        System.out.println("排序结果 1: " + Arrays.toString(arr1)); // [1,3,4,5,10]

        int[] arr2 = {12};
        heapSort(arr2);
        System.out.println("排序结果 2: " + Arrays.toString(arr2)); // [12]

        int[] arr3 = {};
        heapSort(arr3);
        System.out.println("排序结果 3: " + Arrays.toString(arr3)); // []

        int[] arr4 = {5, 5, 3, 3, 2};
        heapSort(arr4);
        System.out.println("排序结果 4: " + Arrays.toString(arr4)); // [2,3,3,5,5]

        int[] arr5 = {1, 2, 3, 4, 5};
        heapSort(arr5);
        System.out.println("排序结果 5: " + Arrays.toString(arr5)); // [1,2,3,4,5]

        int[] arr6 = {9, 7, 5, 3, 1};
        heapSort(arr6);
        System.out.println("排序结果 6: " + Arrays.toString(arr6)); // [1,3,5,7,9]
    }
}

八、桶排序（Bucket Sort）

算法逻辑：

1. 创建若干空桶
2. 将元素分配到对应区间桶中
3. 对每个非空桶排序
4. 合并所有桶元素

import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;

public class BucketSort {

    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 确定最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) {
                min = num;
            } else if (num > max) {
                max = num;
            }
        }

        // 所有元素相等，无需排序
        if (max == min) {
            return;
        }

        // 初始化桶
        int bucketCount = arr.length;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int num : arr) {
            // 计算桶的索引，确保均匀分布
            int bucketIndex = ((num - min) * (bucketCount - 1)) / (max - min);
            buckets.get(bucketIndex).add(num);
        }

        // 对每个桶进行排序并合并
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket); // 使用内置排序算法
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {3, 1, 4, 2, 5};
        bucketSort(arr1);
        System.out.println("排序结果 1: " + Arrays.toString(arr1));

        int[] arr2 = {5, 3, 9, 1, 7};
        bucketSort(arr2);
        System.out.println("排序结果 2: " + Arrays.toString(arr2));

        int[] arr3 = {9, 5, 7, 3, 2, 1};
        bucketSort(arr3);
        System.out.println("排序结果 3: " + Arrays.toString(arr3));

        int[] arr4 = {1, 0, 100, 50};
        bucketSort(arr4);
        System.out.println("排序结果 4: " + Arrays.toString(arr4));
    }
}

九、计数排序（Counting Sort）

算法逻辑：

1. 统计元素出现次数
2. 计算元素正确位置
3. 反向填充目标数组

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]++;
    
    // 计算位置
    for(int i=1; i<count.length; i++) {
        count[i] += count[i-1];
    }
    
    // 构建结果数组
    int[] output = new int[arr.length];
    for(int i=arr.length-1; i>=0; i--) {
        output[--count[arr[i]]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

十、基数排序（Radix Sort）

算法逻辑：

1. 从低位到高位依次排序
2. 使用稳定排序算法（通常为计数排序）
3. 逐位排序直到最高位

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) {
    // 按指定位进行计数排序
}

总结对比表

注：k为桶的数量或数值范围