# SortAlgorithm

**Repository Path**: soria391206/SortAlgorithm

## Basic Information

- **Project Name**: SortAlgorithm
- **Description**: 十大排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。
- **Primary Language**: Unknown
- **License**: GPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-04-24
- **Last Updated**: 2025-04-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 汇总
以下是十大排序算法汇总表：

![十种排序算法汇总](十大排序算法.png)

关于稳定性和占用内存的说明：
- 稳定性：如果`A = B`，排序前A在B前面，排序后A也在B前面，则为稳定；如果出现了排序后A在B后面的情况，则为不稳定。
- 占用内存：`in`代表占用常数内存，不消耗额外内存；`out`代表消耗常数内存。
---
# 开始
笔记中使用了自定义的类，分别是`SortEnum`枚举类和`SortUtil`工具类。
`SortEnum`枚举类如下：
```java
public enum SortEnum {  
    BUBBLE("冒泡排序"),  
    SELECTION("选择排序"),  
    INSERTION("插入排序"),  
    SHELL("希尔排序"),  
    MERGE("归并排序"),  
    QUICK("快速排序"),  
    HEAP("堆排序"),  
    COUNTING("计数排序"),  
    BUCKET("桶排序"),  
    RADIX("基数排序");  
  
    // 排序算法名称  
    private final String name;  
  
    SortEnum(String name) {  
        this.name = name;  
    }  
  
    public String getName() {  
        return name;  
    }  
}
```
`SortUtil`工具类如下：
```java
// 排序工具类  
public class SortUtil {  
  
    // 测试数组  
    private static final int[] TEST_ARRAY = {67, 21, 38, 10, 90, 30, 70, 77, 44, 58, 71, 31, 12, 68, 13};  
  
    // 打印数组  
    private static void print(SortEnum sort, int[] arr) {  
        System.out.print(sort.getName());  
        System.out.print(": [");  
        for (int i : arr) {  
            System.out.print(i + ", ");  
        }  
        System.out.println("\b\b]");  
    }  
  
    /**  
     * 交换数组中的两个元素  
     *  
     * @param arr 数组  
     * @param i   被交换的元素索引  
     * @param j   被交换的元素索引  
     */  
    public static void swap(int[] arr, int i, int j) {  
        int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }  
  
    public static void sort(SortEnum sort) {  
        int[] arr = TEST_ARRAY.clone();  
        switch (sort) {  
            case BUBBLE -> BubbleSort.sort(arr);  
            case SELECTION -> SelectionSort.sort(arr);  
            case INSERTION -> InsertionSort.sort(arr);  
            case SHELL -> ShellSort.sort(arr);  
            case MERGE -> MergeSort.sort(arr);  
            case QUICK -> QuickSort.sort(arr);  
            case HEAP -> HeapSort.sort(arr);  
            default -> {  
                System.out.println("未知排序算法");  
                return;  
            }  
        }
        print(sort, arr);  
    }  
}
```
在使用时直接通过 SortUtil 调用 SortEnum 即可：
```java
public static void main(String[] args) {  
    SortUtil.sort(SortEnum.SELECT);  
}
```
# ⭐冒泡排序
从头开始比较相邻元素，如果第一个元素比第二个元素大，就交换它们两个，直到最后一个元素，这样最后一个就是整个数组中最大的数。
```java
public class BubbleSort {  
    public static void sort(int[] arr) {  
        int len = arr.length;  
        // 遍历次数  
        for (int i = 0; i < len - 1; i++) {  
            // 最大的数在arr[len - i - 1]位置  
            for (int j = 0; j < len - i - 1; j++) {  
                if (arr[j] > arr[j + 1]) {  
                    SortUtil.swap(arr, j, j + 1);  
                }  
            }
        }
    }
}
```
# ⭐选择排序
在序列中找到最小/最大的元素，存放到序列的起始位置，然后再继续找到最小/最大的元素，放到已排序好的序列结尾。
```java
public class SelectionSort {  
    public static void sort(int[] arr) {  
        int len = arr.length;  
        for (int i = 0; i < len; i++) {  
            // 初始化最小元素下标为i  
            int minIndex = i;  
            for (int j = i + 1; j < len; j++) {  
                // 找到比arr[i]更小的元素  
                if(arr[j] < arr[minIndex]){  
                    minIndex = j;  
                }  
            }
            // 如果不是i本身的话，交换他们  
            if(minIndex!= i) {  
                SortUtil.swap(arr, i, minIndex);  
            }  
        }
    }
}
```
# ⭐插入排序
将第一个元素视为已排序好的序列。选择下一个元素，并在已排序好的序列中从后往前扫描，直到找到比该元素小的元素，将该元素插入到其之后。
```java
public class InsertionSort {  
    public static void sort(int[] arr) {  
        int len = arr.length;  
        for (int i = 1; i < len; i++) {  
            int temp = arr[i];  
            int j;  
            // 从后往前遍历已排序的数组  
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {  
                arr[j + 1] = arr[j];  
            }  
            arr[j + 1] = temp;  
        }  
    }
}
```
# 🔋希尔排序
设置一个增量gap（一般是数组长度/2），将整个序列分为gap个子序列，分别对子序列进行插入排序。然后将增量设置为gap=gap/2，再对排序了一次的序列分割成gap个子序列，继续进行插入排序。直到gap=1时再进行一次插入排序即可完成。
```java
public class ShellSort {  
    public static void sort(int[] arr) {  
        int len = arr.length;  
        // 增量  
        for(int gap = len / 2; gap > 0; gap /= 2){  
            for (int i = gap; i < len; i++) {  
                int temp = arr[i];  
                int j;  
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {  
                    arr[j + gap] = arr[j];  
                }  
                arr[j + gap] = temp;  
            }  
        }
    }
}
```
# 🔋归并排序
对序列进行递归再合并，即为归并。将长度为n序列持续递归分割为两个长度为n/2的子序列，直到子序列中只有一个元素。然后在递归的返回过程中，将子序列两两合并，并在合并的过程中完成子序列的排序。
```java
public class MergeSort {  
    public static void sort(int[] arr) {  
        if (arr == null || arr.length < 2) {  
            return;  
        }  
        mergeSort(arr, 0, arr.length - 1);  
    }  
  
    private static void mergeSort(int[] arr, int left, int right) {  
        // 只有一个元素，不需要排序  
        if (left == right) {  
            return;  
        }  
        int mid = left + (right - left) / 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);  
    }  
}
```
# ⭐快速排序
选择一个基准pivot。将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面。该操作结束之后，该基准就处于数列的中间位置(分区partition)。然后递归的进行上述操作即可。
```java
public class QuickSort {  
    public static void sort(int[] arr) {  
        if (arr == null || arr.length <= 1) {  
            return;  
        }  
        quickSort(arr, 0, arr.length - 1);  
    }  
  
    private static void quickSort(int[] arr, int left, int right) {  
        if (left < right) {  
            int pivot = partition(arr, left, right);  
            // 对基准值左边排序  
            quickSort(arr, 0, pivot - 1);  
            // 对基准值右边排序  
            quickSort(arr, pivot + 1, right);  
        }  
    }  
    private static int partition(int[] arr, int left, int right) {  
        // 基准  
        int pivot = arr[left];  
        int i = left + 1;  
        // 当前元素小于基准，交换他们  
        for (int j = i; j <= right && arr[j] < pivot; j++) {  
            SortUtil.swap(arr, i++, j);  
        }  
        // 交换基准值元素和小于基准值元素数组的最后一个元素  
        SortUtil.swap(arr, left, i - 1);  
        return i - 1;  
    }  
}
```
# 🔋堆排序
首先构建一个大根堆或小根堆，然后将堆顶元素和堆的最后一个元素进行交换。交换完成后，需要再次调整堆，使其满足大根堆或小根堆的特性。
```java
public class HeapSort {  
    private static int len;  
  
    public static void sort(int[] arr) {  
        len = arr.length;  
        // 构建大顶堆  
        for (int i = len / 2 - 1; i >= 0; i--) {  
            modifyHeap(arr, i);  
        }  
        // 堆排序  
        for (int i = len - 1; i > 0; i--) {  
            // 交换堆顶元素和最后一个元素  
            SortUtil.swap(arr, 0, len - 1);  
            len--;  
            // 调整堆  
            modifyHeap(arr, 0);  
        }  
    }  
    private static void modifyHeap(int[] arr, int index) {  
        // index节点的左孩子和右孩子  
        int left = index * 2 + 1;  
        int right = index * 2 + 2;  
        // 较大的节点  
        int largest = index;  
        // 找出左右孩子中较大的节点  
        if (left < len && arr[left] > arr[largest]) {  
            largest = left;  
        }  
        if (right < len && arr[right] > arr[largest]) {  
            largest = right;  
        }  
        // 如果largest不是index节点，则交换  
        if (largest!= index) {  
            SortUtil.swap(arr, index, largest);  
            // 继续调整子树  
            modifyHeap(arr, largest);  
        }  
    }
}
```
# 计数排序
首先，我们需要找出数组中的最大值 max 或者最小值 min，然后创建一个计数数组 countArray，数组长度为 `max - min + 1`，元素默认值为0。通过遍历原数组 arr，以 `arr[i] - min`作为 countArray 的索引，`arr[i]`在 arr 出现的次数作为对应的值。最后遍历 countArray，只要索引不为0，将对应的 value 加上`min`输出返回到原数组即可。
```java
public class CountingSort {  
    public static void sort(int[] arr) {  
        if (arr.length < 2) return;  
        int min = arr[0], max = arr[0];  
        // 计算 min 和 max        for (int value : arr) {  
            if (value < min) {  
                min = value;  
            } else if (value > max) {  
                max = value;  
            }  
        }  
        // 计算计数数组  
        int[] countArray = new int[max - min + 1];  
        // 计算索引和出现次数  
        for (int i : arr) {  
            countArray[i - min]++;  
        }  
        // 将计数数组输出返回到原数组  
        for (int arrIndex = 0, countIndex = 0; countIndex < countArray.length; countIndex++) {  
            // 毫无可读性(╯°□°）╯︵ ┻━┻
            while (countArray[countIndex]-- > 0) {  
                arr[arrIndex++] = countIndex + min;  
            }  
        }
    }
}
```
# 桶排序
首先需要设置一个 bucketSize，决定每个 bucket 能放置多少数值。然后遍历数组，将值放到对应的 bucket 里面。接着对每个非空的 bucket 进行排序，最后将 bucket 拼接即可完成排序。
*bucketSize 的大小至关重要，性能最好时每个桶都能均匀放置所有数值。*
```java
// bucket 的大小  
private static final int BUCKET_SIZE = 20;  
  
// 为了统一调用才使用 int[] arr，建议换成 List
public static void sort(int[] arr) {  
    if (arr.length < 2) return;  
    List<Integer> list = new ArrayList<>();  
    for (int value : arr) {  
        list.add(value);  
    }  
    list = sort(list, BUCKET_SIZE);  
    for (int i = 0; i < arr.length; i++) {  
        arr[i] = list.get(i);  
    }  
}  
  
private static List<Integer> sort(List<Integer> list, int bucketSize) {  
    if (list.size() < 2 || bucketSize == 0) {  
        return list;  
    }  
    int min = list.get(0), max = list.get(0);  
    for (Integer integer : list) {  
        if (integer < min) {  
            min = integer;  
        } else if (integer > max) {  
            max = integer;  
        }  
    }    // 计算 bucket 的数量  
    int bucketCount = (max - min) / bucketSize + 1;  
    List<List<Integer>> buckets = new ArrayList<>();  
    for (int i = 0; i < bucketCount; i++) {  
        buckets.add(new ArrayList<>());  
    }  
    // 将元素放入 bucket 中  
    for (Integer integer : list) {  
        int index = (integer - min) / bucketSize;  
        buckets.get(index).add(integer);  
    }  
    // 对每个 bucket 进行排序  
    for (int i = 0; i < bucketCount; i++) {  
        if (!buckets.get(i).isEmpty()) {  
            // 此处排序算法可以换成其他排序算法，本项目大部分都使用 int[] 作为参数， 不好更换  
            buckets.set(i, sort(buckets.get(i), bucketSize / 2));  
        }  
    }    // 将 bucket 中的元素放回原数组  
    List<Integer> result = new ArrayList<>();  
    for (List<Integer> bucket : buckets) {  
        result.addAll(bucket);  
    }  
    return result;  
}
```
# 基数排序
基数排序需要先获取数组中的最大值 max，然后计算出max的位数，即为迭代次数 n。然后新建一个二维数组 radix，其一维长度为 10，然后遍历数组，根据数组每一位的值放入 radix。最后将 radix遍历并赋值给原数组，重复 n 次即可。
```java
public static void sort(int[] arr) {  
    if (arr.length < 2) return;  
    int max = 0;  
    // 获取最大值  
    for (int value : arr) {  
        if (value > max) {  
            max = value;  
        }  
    }    // 计算位数  
    int n = 0;  
    while (max != 0) {  
        max /= 10;  
        n++;  
    }  
    // 基数排序  
    for (int i = 0; i < n; i++) {  
        List<List<Integer>> radix = new ArrayList<>();  
        // 初始化  
        for (int j = 0; j < 10; j++) {  
            radix.add(new ArrayList<>());  
        }  
        // 按位分组添加到radix  
        for (int value : arr) {  
            int digit = (value / (int) Math.pow(10, i)) % 10;  
            radix.get(digit).add(value);  
        }  
        // 按位排序，输出返回到原数组  
        int index = 0;  
        for (List<Integer> list : radix) {  
            for (int value : list) {  
                arr[index++] = value;  
            }  
        }
    }
}
```
# 总结
以下是在不同数据量的情况下合适的排序算法：
- 低数据量：插入排序或选择排序。插入排序具有稳定性，选择排序的效率高于插入排序。
- 中数据量：希尔排序。
- 高数据量：快速排序、归并排序或堆排序。快速排序适合元素分布随机，归并排序具有稳定性，堆排序适合元素分布接近排序好的情况。