java 数组排序算法

数组排序是计算机科学中的基础问题，有多种经典算法。以下是主要的排序方法分类及代表算法：

一、比较排序算法（基于元素比较）

1. 冒泡排序 (Bubble Sort)

   • 原理：重复遍历数组，比较相邻元素并交换，将最大/小值"冒泡"到末尾。
   • 时间复杂度：
     • 平均 & 最坏：O(n²)
     • 最好（已有序）：O(n)
   • 空间复杂度：O(1)（原地排序）
   • 稳定性：✅ 稳定

2. 选择排序 (Selection Sort)

   • 原理：每次从未排序部分选择最小（或最大）元素，与未排序部分首元素交换。
   • 时间复杂度：O(n²)（任何情况）
   • 空间复杂度：O(1)
   • 稳定性：❌ 不稳定（交换可能破坏顺序）

3. 插入排序 (Insertion Sort)

   • 原理：将未排序元素逐个插入已排序部分的正确位置。
   • 时间复杂度：
     • 平均 & 最坏：O(n²)
     • 最好（已有序）：O(n)
   • 空间复杂度：O(1)
   • 稳定性：✅ 稳定

4. 希尔排序 (Shell Sort)

   • 原理：插入排序的改进版，通过分组间隔比较减少元素移动次数。
   • 时间复杂度：O(n log n) ~ O(n²)（取决于间隔序列）
   • 空间复杂度：O(1)
   • 稳定性：❌ 不稳定

5. 快速排序 (Quick Sort)

   • 原理：分治法。选取基准值，将数组分为小于基准和大于基准的两部分，递归排序。
   • 时间复杂度：
     • 平均：O(n log n)
     • 最坏（极端不平衡）：O(n²)
   • 空间复杂度：O(log n)（递归栈）
   • 稳定性：❌ 不稳定

6. 归并排序 (Merge Sort)

   • 原理：分治法。将数组递归拆分为子数组排序，再合并有序子数组。
   • 时间复杂度：O(n log n)（任何情况）
   • 空间复杂度：O(n)（合并需额外空间）
   • 稳定性：✅ 稳定

7. 堆排序 (Heap Sort)

   • 原理：将数组构建为最大堆，重复从堆顶取最大值放入已排序区。
   • 时间复杂度：O(n log n)
   • 空间复杂度：O(1)
   • 稳定性：❌ 不稳定

二、非比较排序算法（基于数值特性）

1. 计数排序 (Counting Sort)

   • 原理：统计每个元素出现次数，直接计算元素在有序数组中的位置。
   • 要求：元素为整数且范围 k 较小。
   • 时间复杂度：O(n + k)
   • 空间复杂度：O(n + k)
   • 稳定性：✅ 稳定

2. 桶排序 (Bucket Sort)

   • 原理：将元素分到多个桶中，对每个桶单独排序后合并。
   • 要求：数据均匀分布。
   • 时间复杂度：
     • 平均：O(n + k)（k 为桶数）
     • 最坏：O(n²)（所有元素集中在一个桶）
   • 空间复杂度：O(n + k)
   • 稳定性：✅ 稳定（取决于桶内排序算法）

3. 基数排序 (Radix Sort)

   • 原理：按位数从低位到高位依次排序（通常用计数排序作为子过程）。
   • 要求：元素为整数或固定位数的字符串。
   • 时间复杂度：O(d(n + k))（d 为最大位数，k 为基数）
   • 空间复杂度：O(n + k)
   • 稳定性：✅ 稳定

三、总结对比

关键结论：

• 高效通用排序：快速排序（平均最优）、归并排序（稳定且高效）、堆排序（避免最坏情况）。
• 小规模数据：插入排序（简单且对部分有序数据高效）。
• 非比较场景：计数排序、桶排序、基数排序（特定条件下可达线性时间复杂度）。

模板模式实现数组排序
1.抽象类（抽象排序）

public abstract class AbstractSort {


    final void abstractSort(Number[] numbers) {
        beforeSort(numbers);
        Number[] result = sort(numbers);
        afterSort(result);
    }


    private void beforeSort(Number[] numbers) {
        System.out.println("排序前的数组:");
        for (Number number : numbers) {
            System.out.print(" " + number);
        }
        System.out.println();
    }


    private void afterSort(Number[] numbers) {
        System.out.println("排序后的数组:");
        for (Number number : numbers) {
            System.out.print(" " + number);
        }
        System.out.println();
    }


    abstract Number[] sort(Number[] numbers);


}

接下来就是各大排序算法：均继承抽象排序类
2.冒泡排序

public class BubbleSort extends AbstractSort {


    @Override
    public Number[] sort(Number[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length - 1 - i; j++) {
                if (numbers[j].doubleValue() > numbers[j + 1].doubleValue()) {
                    Number temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
        return numbers;
    }


}

3.桶排序

public class BucketSort extends AbstractSort {
    @Override
    Number[] sort(Number[] numbers) {
        // 分别定义最大、最小值
        Number min = numbers[0], max = numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i].doubleValue() > max.doubleValue()) {
                max = numbers[i];
            }
            if (numbers[i].doubleValue() < min.doubleValue()) {
                min = numbers[i];
            }
        }


        //桶初始化
        int bucketCount = numbers.length;
        ArrayList<LinkedList<Double>> list = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            list.add(new LinkedList<>());
        }




        //将每个元素放入桶中
        double d = max.doubleValue() - min.doubleValue();
        for (Number number : numbers) {
            int num = (int) ((number.doubleValue() - min.doubleValue()) * (bucketCount - 1) / d);
            list.get(num).add(number.doubleValue());
        }


        //对每个桶内部进行排序
        for (LinkedList<Double> doubles : list) {
            Collections.sort(doubles);
        }


        //输出全部元素
        Number[] result = new Number[bucketCount];
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                result[index++] = list.get(i).get(j);
            }
        }


        return result;
    }
}

4.计数排序

public class CountSort extends AbstractSort {


    @Override
    Number[] sort(Number[] numbers) {
        sort(numbers, 1);
        return numbers;
    }
    
    void sort(Number[] numbers, Number offset) {
        int[] count = new int[numbers.length];
        for (Number number : numbers) {
            count[number.intValue() - offset.intValue()]++;
        }


        // 填充数组
        for (int i = 0, k = 0; i < count.length; i++) {
            for (int j = 0; j < count[i]; j++) {
                numbers[k++] = i + offset.intValue();
            }
        }


    }


}

5.堆排序

public class HeapSort extends AbstractSort {


    @Override
    Number[] sort(Number[] numbers) {
        // 把无序数组构建成最大堆
        for (int i = numbers.length / 2 - 1; i >= 0; i--) {
            adjustHeap(numbers, i, numbers.length);
        }
        // 调整堆结构+交换堆顶元素与末尾元素，调整堆产生新的堆顶
        for (int i = numbers.length - 1; i > 0; i--) {
            Number temp = numbers[i];
            numbers[i] = numbers[0];
            numbers[0] = temp;
            // "下沉"调整最大堆
            adjustHeap(numbers, 0, i);
        }


        return numbers;
    }


    void adjustHeap(Number[] numbers, int parentIndex, int length) {
        // temp 保存父节点值，用于最后的赋值
        Number temp = numbers[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length) {
            // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if (childIndex + 1 < length && numbers[childIndex].doubleValue()
                    < numbers[childIndex + 1].doubleValue()) {
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，则直接跳出
            if (temp.doubleValue() >= numbers[childIndex].doubleValue()) {
                break;
            }
            // 无须真正交换，单向赋值即可
            numbers[parentIndex] = numbers[childIndex];
            parentIndex = childIndex;
            // 下一个左孩子
            childIndex = 2 * childIndex + 1;
        }
        numbers[parentIndex] = temp;
    }


}

6.插入排序

public class InsertSort extends AbstractSort {
    @Override
    Number[] sort(Number[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            // 当前待比较的元素
            Number temp = numbers[i];
            for (int j = i - 1; j >= 0; j--) {
                // 前面的元素比当前待比较的元素大
                if (numbers[j].doubleValue() > temp.doubleValue()) {
                    // 前面的大元素右移一位
                    numbers[j + 1] = numbers[j];


                    // 若索引0的数还比temp大，那说明temp是最小元素，放在索引0的位置上
                    if (j == 0) {
                        numbers[j] = temp;
                    }
                } else {
                    // 遇到了比当前待比较的元素小，插在后一位
                    numbers[j + 1] = temp;
                    break;
                }


            }
        }
        return numbers;
    }


}

7.归并排序

public class MergeSort extends AbstractSort {


    @Override
    Number[] sort(Number[] numbers) {
        return mergeSort(numbers);
    }


    private Number[] mergeSort(Number[] numbers) {
        // 拆分到只剩下一个元素，返回
        if (numbers.length < 2) {
            return numbers;
        }
        int mid = numbers.length / 2;
        // 左数组
        Number[] left = Arrays.copyOfRange(numbers, 0, mid);
        left = mergeSort(left);
        // 右数组
        Number[] right = Arrays.copyOfRange(numbers, mid, numbers.length);
        right = mergeSort(right);
        return merge(left, right);
    }


    private Number[] merge(Number[] left, Number[] right) {
        Number[] result = new Number[left.length + right.length];
        int indexLeft = 0;
        int indexRight = 0;
        for (int i = 0; i < result.length; i++) {
            if (indexLeft < left.length && indexRight < right.length) {
                if (left[indexLeft].doubleValue() <= right[indexRight].doubleValue()) {
                    result[i] = left[indexLeft++].doubleValue();
                } else {
                    result[i] = right[indexRight++].doubleValue();
                }
            } else if (indexLeft >= left.length) {
                result[i] = right[indexRight++].doubleValue();
            } else {
                result[i] = left[indexLeft++].doubleValue();
            }
        }
        return result;
    }


}

8.快速排序

public class QuickSort extends AbstractSort {


    @Override
    Number[] sort(Number[] numbers) {
        quickSort(numbers, 0, numbers.length - 1);
        return numbers;
    }
    
    private void quickSort(Number[] numbers, int left, int right) {
        // 分别设置向右搜索i、向左搜索j指针
        int i = left;
        int j = right;


        // 基准
        Number temp = numbers[i];
        while (i < j) {
            //numbers[i]不小于基准，不用交换，继续向前搜索
            while (i < j && numbers[j].doubleValue() > temp.doubleValue()) {
                j--;
            }
            while (i < j && numbers[i].doubleValue() < temp.doubleValue()) {
                i++;
            }
            // i和j位置的元素互换
            Number tmp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = tmp;
        }
        if (left < i - 1) {
            // 同样的方式处理左子区
            quickSort(numbers, left, i - 1);
        }
        if (right > i + 1) {
            quickSort(numbers, i + 1, right);
        }




    }


}

9.基数排序

public class RadixSort<T> extends AbstractSort {


    @Override
    Number[] sort(Number[] numbers) {
        Number max = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i].intValue() > max.intValue()) {
                max = numbers[i];
            }
        }


        // 最大数是几位数
        int maxLength = (max.intValue() + "").length();
        int[][] bucket = new int[10][numbers.length];


        // 定义一个一维数组来记录每个桶中每次放入的元素个数
        int[] bucketElementCounts = new int[10];


        // 通过n取出每个元素上的位数
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < numbers.length; j++) {
                int digit = numbers[j].intValue() / n % 10;
                // 将元素放入对应的桶中
                bucket[digit][bucketElementCounts[digit]] = numbers[j].intValue();
                // 将桶中的元素个数++
                // 这样接下来的元素就可以排在前面的元素后面
                bucketElementCounts[digit]++;
            }
            // 按照桶里的元素取出并放回原数组
            int index = 0;
            for (int k = 0; k < bucket.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        numbers[index++] = bucket[k][l];
                    }
                    bucketElementCounts[k] = 0;
                }
            }
        }


        return numbers;
    }
}

10.选择排序

public class SelectSort extends AbstractSort {
    @Override
    Number[] sort(Number[] numbers) {
        for (int i = 0; i < numbers.length - 1; i++) {
            // 记录当前元素位置
            int index = i;
            for (int j = i + 1; j < numbers.length; j++) {
                // 从下一个元素开始查找，找到最小的之后与i换位置
                if (numbers[j].doubleValue() < numbers[index].doubleValue()) {
                    index = j;
                }
            }
            // numbers[i]与numbers[index]换位置
            Number temp = numbers[i];
            numbers[i] = numbers[index];
            numbers[index] = temp;
        }
        return numbers;
    }


}

11.希尔排序

public class ShellSort extends AbstractSort {
    @Override
    Number[] sort(Number[] numbers) {
        for (int gap = numbers.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < numbers.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (numbers[j].doubleValue() > numbers[j + gap].doubleValue()) {
                        Number temp = numbers[j];
                        numbers[j] = numbers[j + gap];
                        numbers[j + gap] = temp;
                    }
                }
            }
        }
        return numbers;
    }
}

12.测试方法

public class Main {
    public static void main(String[] args) {
        Integer[] integers = new Integer[]{30, 11, 6, 25, 40, 17, 12, 55, 36};
        new HeapSort().abstractSort(integers);
    }
}