Java实现十大排序算法

文章目录

1 相关概念
2 算法实现
3 算法执行效率

1 相关概念

算法的稳定性
假设在数组中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的。
算法的稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。
在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类:
- 内部排序，是指在排序期间元素全部存放在内存中的排序
- 外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。

2 算法实现

工具类

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Random;

public class MySortUtils {
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void swap2(int[] a, int i, int j) {
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }

    /**
     * 获取一个包含10个整数的数组，数组每个元素为[0,100]内的随机数
     *
     * @return
     */
    public static int[] getArr() {
        int arrLen = 10;
        Random random = new Random();
        int[] a = new int[arrLen];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(100) + 1;
        }
        return a;
    }

    /**
     * 获取一个长度为 length 的int[]，数组中每个元素为[start, end]之间的随机数
     *
     * @param start
     * @param end
     * @return
     */
    public static int[] getArr(int start, int end, int length) {
        Random random = new Random();
        int[] a = new int[length];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(end - start) + start + 1;
        }
        return a;
    }

    /**
     * @param clazz
     * @param methodName
     */
    public static void printArrayBeforeAndAfterSorting(Class<?> clazz, String methodName, int[] arr) {
        try {
            Method method = clazz.getMethod(methodName, int[].class);

            System.out.println(clazz.getSimpleName() + "." + method.getName() + ":");
            System.out.printf("排序前：%s\n", Arrays.toString(arr));

            Object obj = clazz.getDeclaredConstructor().newInstance();
            method.invoke(obj, arr);

            System.out.printf("排序后：%s\n", Arrays.toString(arr));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * @param clazz
     * @param methodName
     */
    public static void printArrayBeforeAndAfterSorting2(Class<?> clazz, String methodName) {
        try {
            Method method = clazz.getMethod(methodName, int[].class);
            int[] arr = getArr();

            System.out.println(clazz.getSimpleName() + "." + method.getName() + ":");
            System.out.printf("排序前：%s\n", Arrays.toString(arr));

            Object obj = clazz.getDeclaredConstructor().newInstance();
            method.invoke(obj, arr);

            System.out.printf("排序后：%s\n", Arrays.toString(arr));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void printArrayBeforeAndAfterSorting3(Class<?> clazz, String methodName) {
        try {
            Method method = clazz.getMethod(methodName, int[].class, int.class, int.class);

            System.out.println(clazz.getSimpleName() + "." + method.getName() + ":");

            int[] arr = getArr();
            System.out.printf("排序前：%s\n", Arrays.toString(arr));

            Object obj = clazz.getDeclaredConstructor().newInstance();
            method.invoke(obj, arr, 0, arr.length - 1);

            System.out.printf("排序后：%s\n", Arrays.toString(arr));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

1 冒泡排序

a 算法原理

从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称之为一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”（或关键字最大的元素如石头一般下沉至水底）。

下一趟冒泡时，前一趟确定的最小元素不再参与比较，每一趟冒泡，序列中的最小元素（或最大元素）放到了序列的最前端（最后端），因此，每一趟冒泡都至少有一个元素的最终位置被确定，最多做 n-1 趟冒泡就能把所有元素排好序。

为增进算法性能，可设置一个标志变量 flag，在每一趟冒泡前，置其值为 false，若有元素发生交换，则置其值为 true，每一趟冒泡结束，检测其值是否改变，若没有改变，则元素已有序，直接退出排序，否则进行新一轮冒泡。否则的话每次排序都要进行 n-1 趟冒泡，在对元素基本有序的元素进行排序时就会浪费时间。

b 性能分析

空间效率：仅使用常数个辅助单元，空间复杂度为 $O (1)$
时间效率
- 最好情况：元素已经有序，只需进行 n-1 次比较即可，没有元素移动，时间复杂度为 $O (n)$
- 最坏情况：元素顺序与排序结果逆序，要进行 n-1 趟排序，第 i 趟排序要比较 n-i 次，且每次比较都需要交换元素，且每次交换操作次数为3（temp = a; a = b; b = temp;），共移动 3(n-i)次，故总次数为 $\displaystyle \sum_{i=1}^{n-1}(n-i)+3*(n-i)=2n(n-1)$ ，故时间复杂度为 $O(n^2)$
稳定性：假设升序排序，只有后一个元素大于前一个元素才会发生交换，相同关键字元素相对位置不变，因此冒泡排序是稳定的排序算法

// https://www.cnblogs.com/skywang12345/p/3596232.html
public class A_BubbleSort extends MySortUtils {
    public void bubbleSort(int[] a) {
        int n = a.length;
        for (int i = n - 1; i > 0; i--) {
            // 将a[0...i]中最大的数据放在末尾
            for (int j = 0; j < i; j++) {
                //若前一个数 < 后一个数，则交换位置
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }

    /**
     * 冒泡排序（改进版）
     * 对冒泡排序进行优化，使它效率更高一些：添加一个标记，如果一趟遍历中发生了交换，则标记为true，否则为false。
     * 如果某一趟没有发生交换，说明排序已经完成！
     *
     * @param a
     */
    public void bubbleSortImprove(int[] a) {
        boolean flag;//若一趟排序中有元素发生交换，则为true；否则为false

        int n = a.length;
        for (int i = n - 1; i > 0; i--) {
            flag = false;
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                    flag = true;
                }
            }
            if (!flag) {
                break; // 若没发生交换，则说明数列已有序
            }
        }
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(A_BubbleSort.class, "bubbleSort");
        printArrayBeforeAndAfterSorting2(A_BubbleSort.class, "bubbleSortImprove");
    }
}

A_BubbleSort.bubbleSort:
排序前：[18, 10, 18, 77, 72, 60, 15, 46, 76, 55]
排序后：[10, 15, 18, 18, 46, 55, 60, 72, 76, 77]
A_BubbleSort.bubbleSortImprove:
排序前：[63, 19, 40, 75, 42, 72, 33, 48, 68, 26]
排序后：[19, 26, 33, 40, 42, 48, 63, 68, 72, 75]

2 快速排序

a 算法原理

快速排序(Quick Sort)使用分治法策略。
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：

从数列中挑出一个基准值。
将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

①排序方法一

假设有一个由若干数据组成的序列，

取第一个数据为基准数据 base，指针 i 指向base后第一个数据，指针 j 指向最后一个数据；
当 i < j 时：先递减 j，从后向前搜索小于 base 的数据，再递增 i ，从前向后搜索大于 base 的数据，若找到，则交换；继续递减 j，递增 i 进行同样的操作，直至 i == j
当 i == j 时：交换 base 和 array[i]，则 base 左侧的数据都小于 base，base 右侧的数据都大于base，此时一次排序结束，序列被分成两个子序列
对每个序列重复使用步骤1、2、3

array[10] = { 150 107 182 178 183 154 141 138 182 169 }
在这里插入图片描述

①排序方法二

假设有一个由若干数据组成的序列，

取第一个数据为基准数据 base，指针 i 指向 base，指针 j 指向最后一个数据；
当 i < j 时：
先递减 j，从后向前搜索小于 base 的数据，若找到，则交换 array[i]、array[j]；
再递增 i ，从前向后搜索大于 base 的数据，若找到，则交换 array[i]、array[j]；
继续递减 j，递增 i 进行同样的操作，直至 i == j
当 i == j 时：将 array[i] 的值置为 base，则 base 左侧的数据都小于 base，base 右侧的数据都大于base，此时一次排序结束，序列被分成两个子序列
对每个序列重复使用步骤1、2、3

array[10] = { 150 107 182 178 183 154 141 138 182 169 }
在这里插入图片描述
b 性能分析

快速排序的性能与子序列划分的对称程度有关，越趋于对称（元素越无序），则性能越好，否则越差（元素越有序）。最坏情况下，一个子序列含有 n-1 个元素，另一个子序列含有 0 个元素，而且每次划分都是此种情况，则递归调用次数最多，运行时间最长。理想情况下，每次划分都是对称的，即左右子序列元素个数基本相同。

空间效率：需要使用递归工作栈来保存函数调用，栈容量与递归调用的最大深度一致。最好情况下为 $O(log_2n)$ ，最坏情况下为 $O (n)$
时间效率：元素越有序，性能越差，最差的时间复杂度为 $O(n^2)$
稳定性：两个子序列元素交换可能使相同关键字元素相对位置改变，因此快速排序是不稳定的排序算法。

快速排序算法是所有内部排序算法中平均性能最好的。

c 适用范围

元素无序程度越高越适用。

public class F_QuickSort extends MySortUtils { 
    public void quickSort1(int[] a, int left, int right) {
        if (left < right) {
            int i = left;
            int j = right;
            int base = a[i];

            while (i != j) {
                // 从右向左搜寻小于 base 的数据
                while (i < j && a[j] >= base) {
                    j--;
                }
                // 从左向右搜寻大于 base 的数据
                while (i < j && a[i] <= base) {
                    i++;
                }
                swap(a, i, j); // 交换搜寻到的数据
            }

            swap(a, i, left);//此时i==j

            quickSort1(a, left, i - 1);//快排 base 左侧数据
            quickSort1(a, i + 1, right);//快排 base 右侧数据
        }
    }

    public void quickSort2(int[] a, int left, int right) {
        if (left < right) {
            int i = left, j = right, base = a[i];

            while (i < j) {
                // 从右向左搜寻小于 base 的数据
                while (i < j && a[j] >= base) {
                    j--;
                }
                if (i < j) {
                    a[i] = a[j];
                    i++;
                }
                // 从左向右搜寻大于 base 的数据
                while (i < j && a[i] <= base) {
                    i++;
                }
                if (i < j) {
                    a[j] = a[i];
                    j--;
                }
            }

            a[i] = base;//此时i==j
            quickSort2(a, left, i - 1);
            quickSort2(a, i + 1, right);
        }
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting3(F_QuickSort.class, "quickSort1");
        printArrayBeforeAndAfterSorting3(F_QuickSort.class, "quickSort2");
    }
}

F_QuickSort.quickSort1:
排序前：[17, 52, 26, 31, 65, 1, 26, 52, 92, 28]
排序后：[1, 17, 26, 26, 28, 31, 52, 52, 65, 92]
F_QuickSort.quickSort2:
排序前：[75, 32, 6, 33, 25, 66, 65, 7, 65, 69]
排序后：[6, 7, 25, 32, 33, 65, 65, 66, 69, 75]

3 插入排序

直接插入排序

a 算法原理

设有 n 个元素的顺序表 $L[1\dots n]$ ，假设下标从 1 开始，按升序排序：

有序列表 $L [1... i]$	无序列表 $L [i + 1... n]$

将一组数据分成两组，分别为有序组、无序组（第一次取首元素为有序组，剩余 n-1 个元素为无序组）
取出无序组第一个元素 $L [i + 1]$ ，按从后向前的顺序，与有序组的元素逐个比较：
①若 $L[x]，1\leq x\leq i$ ，则将 $L [x]$ 后移一位
②若 $\geq L[x]，1\leq x\leq i$ ，则停止比较，将 $L [i + 1]$ 插入到 $L [x]$ 后
重复步骤 2，直至无序组元素为空，则元素最终有序

b 性能分析

空间效率：仅使用常数个辅助单元，空间复杂度为 $O (1)$
时间效率
- 最好情况
  元素顺序与排序结果相同，每插入一个元素仅需比较一次而不需移动，且比较次数为 n-1，故时间复杂度为 $O (n)$
- 最坏情况
  元素顺序与排序结果相反，则第 i+1 个元素需向前比较 i 次，且前 i 个元素每个都要移动一次，则总比较次数、总移动次数均为 $\displaystyle \sum_{i=2}^n(i-1)，结果为2 * \displaystyle \sum_{i=2}^n(i-1) = 2 * (1+2+...+(n-1)) =2*\frac{n(n-1)}{2}=n^2-n$ ，故时间复杂度为 $O(n^2)$
稳定性：每次都是从后向前先比较再移动，待插入元素不会插入到值相等元素前面，元素间相对位置不变，因此直接插入排序是稳定的排序算法

c 适用范围

元素顺序越接近有序，比较次数、移动次数越少，越接近逆序比较次数、移动次数越多。可见，直接插入排序适用于元素基本有序的情况

// https://www.runoob.com/w3cnote/insertion-sort.html
// https://www.cnblogs.com/skywang12345/p/3596881.html
public class C_InsertSort extends MySortUtils {
    public void insertSort(int[] a) {
        //初始状态：a[0]已有序，无序表第一个元素为a[1]
        for (int i = 1; i < a.length; i++) {
            //记录要插入的数据
            int temp = a[i];

            //要插入位置的索引
            int j = i;
            //若a[0..i-1]中有大于a[i]的数，则将其后移
            while (j > 0 && temp < a[j - 1]) {
                a[j] = a[j - 1];
                j--;
                // a[j] = a[j--];
            }

            //将a[i]插入到合适位置
            if (j != i) {
                a[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(C_InsertSort.class, "insertSort");
    }
}

C_InsertSort.insertSort:
排序前：[69, 78, 90, 76, 6, 52, 60, 42, 60, 67]
排序后：[6, 42, 52, 60, 60, 67, 69, 76, 78, 90]

折半插入排序

有序列表 $L [1... i - 1]$	$L [i]$	无序列表 $L [i + 1.. n]$

折半插入是对直接插入的改进，唯一不同的是插入元素时比较元素的方法。

直接插入排序：比较元素是从后向前逐个比较，以确定插入位置
折半插入排序：先在有序表中使用折半查找确定元素 $L [i]$ 在有序表中的位置，然后再将 $L [i]$ 插入到合适位置

由于使用了折半查找，元素的比较次数减少，约为 $O(nlog_2n)$ ，元素的比较次数与初始状态无关，仅取决于元素个数 n，而元素的移动次数没有改变，和初始状态有关。因此，折半插入排序时间复杂度为 $O(n^2)$ ，是稳定的排序算法，适用于元素个数不多的排序

void InsertSort(int A[], int arrayLength)
{
    int i, j, low, mid, high;
    for(i = 2; i <= arrayLength; i++)
    {
        A[0] = A[i];	//A[0]用来暂存元素L[i]
        low = 1;
        high = i-1;
        while(low <= high)
        {
            mid = (high + low) / 2;
            if(A[0] < A[mid]) high = mid - 1;
            else low = mid + 1;
        }
        for(j = i-1; j >= high+1; j--)
            A[j+1] = A[j];
        A[high+1] = A[0];
    }
}

4 希尔排序（shell排序/缩小增量排序）

a 算法原理

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），对每个子序列进行直接插入排序。然后缩减增量对子序列进行排序…，直至增量为 1 时，将整个元素序列变为有序。

先取小于元素个数 n 的增量 gap，表中所有距离为 gap 的元素归为一组，对分好组的子序列进行直接插入排序；不断缩小 gap ，重复进行分组、排序的过程，直到 gap 为1，最终整个序列有序。

gap的一般取法：首先取 $gap=\lfloor n/2 \rfloor，然后取gap=\lfloor gap/2 \rfloor$

b 性能分析

空间效率：仅使用常数个辅助单元，空间复杂度为 $O (1)$
时间效率：取决于所选用的增量函数，这属于数学上尚未解决的难题。一般来说时间复杂度为 $O(n^{1.3})$ ，最坏情况下为 $O(n^2)$
稳定性：相同关键字的元素可能划分到不同子序列，各个子序列排序后关键字相同的元素相对位置可能改变，因此希尔排序是不稳定的排序算法

c 适用范围

直接插入排序适用于元素基本有序和数据量不大的顺序表，希尔排序是基于此两点对直接插入排序的改进，当数据量较多时可选用希尔排序，且它仅适用与线性表为顺序存储的情况。

array[10] = {198, 104, 146, 153, 198, 132, 103, 170, 185, 184}

gap = 10 / 2 = 5
gap = 5 / 2 = 2
gap = 2 / 2 = 1

在这里插入图片描述
希尔排序适用于大规模且无序的数据

/*
https://www.runoob.com/w3cnote/shell-sort.html
https://www.cnblogs.com/skywang12345/p/3597597.html
 */
public class D_ShellSort extends MySortUtils {
 public void shellSort(int[] a) {
        int n = a.length;
        for (int gap = n / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = a[i];//无序区第一个元素
                int j = i - gap;
                while (j >= 0 && temp < a[j]) {
                    a[j + gap] = a[j];
                    j -= gap;
                }
                a[j + gap] = temp;
                /*
                int j = i;
                while (j > 0 && temp < a[j - gap]) {
                    a[j] = a[j - gap];
                    j -= gap;
                }
                a[j] = temp;
                 */
            }
        }
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(D_ShellSort.class, "shellSort");
    }
}

D_ShellSort.shellSort:
排序前：[8, 99, 36, 91, 36, 51, 1, 28, 60, 80]
排序后：[1, 8, 28, 36, 36, 51, 60, 80, 91, 99]

5 选择排序

此算法与直接插入排序有异曲同工之处。

a 算法原理

理解方式一：

设有 n 个元素的顺序表 $L[1\dots n]$ ，假设下标从 1 开始，按升序排序：

$L [1... n]$

第 $i(1\leq i\leq n)$ 趟排序，从后 n-i+1 个元素中选取最小元素，将其与 $L [i]$ 交换位置。

理解方式二：

$有序列表 L [1... i]$	$无序列表 L [i + 1... n]$

将一组数据分成两组，分别为有序组、无序组（第一次有序组无元素，无序组元素个数为n）
选出无序组中最小元素 $L[min]，i+1\leq min\leq n$ ，将其与有序组尾元素 $L [i]$ 后一个元素交换位置
重复第 2 步 n-1 次

b 性能分析

空间效率：仅使用常数个辅助单元，空间复杂度为 $O (1)$
时间效率：元素的比较次数与数组初始状态无关，因为挑选最小元素时，需要与无序组每个元素进行比较，固定次数为 $\displaystyle \sum_{i=1}^{n-1}=n(n-1)/2$ 。最坏情况下（元素顺序与排序结果逆序），每个元素都需要交换，则最多交换次数为 $3 (n - 1)$ ，故时间复杂度为 $O(n^2)$
稳定性：元素交换时可能会使相同关键字的元素交换，因此不稳定

c 适用范围
元素越有序越适用，只需比较，无需交换。元素逆序，最不适用，每次都要交换元素。

/*
https://www.runoob.com/w3cnote/selection-sort.html
https://www.cnblogs.com/skywang12345/p/3597641.html
 */
public class B_SelectionSrot extends MySortUtils {
    /**
     * 选择排序：
     * 首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；
     * 接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。
     * 以此类推，直到所有元素均排序完毕。
     */
    public void selectionSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            if (min != i) {
                swap(a, i, min);
            }
        }
    }


    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(B_SelectionSrot.class, "selectionSort");
    }
}

B_SelectionSrot.selectionSort:
排序前：[33, 87, 13, 48, 12, 29, 70, 98, 4, 16]
排序后：[4, 12, 13, 16, 29, 33, 48, 70, 87, 98]

6 堆排序

堆排序的关键是首先构造堆结构。堆结构是一种树结构,准确地说是一个完全二叉树。在这个树中每个结点对应于原始数据的一个记录,并且每个结点应满足以下条件:

大顶堆	小顶堆
非叶结点的数据 >= 其左、右子结点的数据	非叶结点的数据 <= 其左、右子结点的数据
下标从1开始： $L[i]\geq L[2i]\&L[i]\geq L[2i+1]$ 下标从0开始： $L[i]\geq L[2i+1]\&L[i]\geq L[2i+2]$	下标从1开始： $L[i]\leq L[2i]\&L[i]\leq L[2i+1]$ 下标从0开始： $L[i]\leq L[2i+1]\&L[i]\leq L[2i+2]$

a 算法原理

将表中元素构造成一个大顶堆，将堆顶元素(最大元素)与堆底元素交换，此时最大元素送到末尾。由于堆顶元素与堆底元素交换，堆结构被破坏，再重新构造堆，再交换…重复构造堆、交换元素的过程，则最后元素有序。

此算法中有两个关键点，一是构造初始堆，而是交换元素后调整堆。

从根节点开始，从左到右、从上到下对每个节点编号，起始序号为 0 或 1，下面以 1 开始

构造堆：从最后一个非叶节点开始到第一个非叶节点结束构造堆（从右到左，从下到上）
调整堆

在这里插入图片描述

b 性能分析

空间效率：仅使用常数个辅助单元，空间复杂度为 $O (1)$
时间效率：建堆时间为 $O (n)$ ，之后有 n-1 次向下调整，每次调整次数为树的高度 h( $O(h)=O(log_2n)$ )，故时间复杂度为 $O(log_2n)*O(n-1)=O(nlog_2n)$
稳定性：元素交换时可能会使相同关键字的元素交换，因此不稳定

c 适用范围
元素越有序越适用，只需比较，无需交换。元素逆序，最不适用，每次都要交换元素。

/*
https://www.cnblogs.com/skywang12345/p/3602162.html
https://www.runoob.com/w3cnote/heap-sort.html
 */
public class G_HeapSort extends MySortUtils {
    /**
     * 大顶堆（升序排序）
     * <p>
     * 最大堆进行升序排序的基本思想：
     * ① 初始化堆：将数列a[1...n]构造成最大堆。
     * ② 交换数据：将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为最大堆。
     * 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1...n-1]中的最大值；然后将a[1...n-2]重新调整为最大值。
     * 依次类推，直到整个数列都是有序的。
     *
     * @param a 待排序的数组
     */
    public void heapSortAsc(int[] a) {
        int n = a.length;
        // i 初始化值为最后一个非叶节点序号
        for (int i = n / 2 - 1; i >= 0; i--) {
            //从最后一个非叶结点开始，从下到上，从右到左调整堆结构（初始化堆：将数组构造成最大堆）
            maxHeapDown(a, i, n - 1);
        }

        for (int i = n - 1; i > 0; i--) {
            // 将堆顶元素放到数组尾部
            swap(a, 0, i);
            // 将堆中剩余元素调整为最大堆
            maxHeapDown(a, 0, i - 1);
        }
    }

    /**
     * 大顶堆的向下调整算法
     * 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
     *
     * @param a     待排序的数组
     * @param start 被下调节点的起始位置(一般为0，表示从第1个开始)
     * @param end   截至范围(一般为数组中最后一个元素的索引)
     */
    public void maxHeapDown(int[] a, int start, int end) {
        // 从 dad 开始调整堆，然后调整 dad 的左子树
        // son 起始为 dad 左子树，son 下一次变化为 dad 的左子树，以此类推
        for (int dad = start, son = 2 * dad + 1; son <= end; dad = son, son = 2 * dad + 1) {
            // 若 dad 有右子树：挑选子节点中较大的那个元素
            if (son + 1 <= end && a[son] < a[son + 1]) {
                son++;
            }

            //若孩子节点的值 > 父节点的值：则交换
            if (a[son] > a[dad]) {
                swap(a, dad, son);
            }
            //如果父节点 > 子节点代表调整完毕，直接跳出函数
            else {
                break;
            }
        }
    }


    /**
     * 小顶堆（降序排序）
     *
     * @param a 待排序的数组
     */
    public void heapSortDesc(int[] a) {
        int n = a.length;
        // i 初始化值为最后一个非叶节点序号
        for (int i = n / 2 - 1; i >= 0; i--) {
            //从最后一个非叶结点开始，从下到上，从右到左调整堆结构
            minHeapDown(a, i, n - 1);
        }

        for (int i = n - 1; i > 0; i--) {
            // 将堆顶元素放到数组尾部
            swap(a, 0, i);
            // 对堆中剩余元素进行调整
            minHeapDown(a, 0, i - 1);
        }
    }

    /**
     * 小顶堆的向下调整算法
     * 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
     *
     * @param a     待排序的数组
     * @param start 被下调节点的起始位置(一般为0，表示从第1个开始)
     * @param end   截至范围(一般为数组中最后一个元素的索引)
     */
    public void minHeapDown(int[] a, int start, int end) {
        // 从 dad 开始调整堆，然后调整 dad 的左子树
        // son 起始为 dad 左子树，son 下一次变化为 dad 的左子树，以此类推
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end) {//此处的while循环等价于上述for循环
            // 若 dad 有右子树：挑选子节点中较小的那个元素
            if (son + 1 <= end && a[son] > a[son + 1]) {
                son++;
            }

            //若孩子节点的值 < 父节点的值：则交换
            if (a[son] < a[dad]) {
                swap(a, dad, son);
                dad = son;
                son = dad * 2 + 1;
            }
            //如果父节点 < 子节点代表调整完毕，直接跳出函数
            else {
                break;
            }
        }
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(G_HeapSort.class, "heapSortAsc");
        printArrayBeforeAndAfterSorting2(G_HeapSort.class, "heapSortDesc");
    }
}

G_HeapSort.heapSortAsc:
排序前：[70, 49, 76, 56, 4, 44, 75, 57, 17, 91]
排序后：[4, 17, 44, 49, 56, 57, 70, 75, 76, 91]
G_HeapSort.heapSortDesc:
排序前：[70, 3, 20, 16, 92, 19, 64, 80, 64, 97]
排序后：[97, 92, 80, 70, 64, 64, 20, 19, 16, 3]

7 归并排序

在这里插入图片描述

/*
https://www.cnblogs.com/skywang12345/p/3602369.html

将两个的有序数列合并成一个有序数列，我们称之为"归并"。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。

1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；
    得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。(参考下面的图片)

2. 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。
 */
public class E_MergeSort extends MySortUtils {
    /**
     * 归并排序(从上往下)
     *
     * @param a     待排序的数组
     * @param left  数组的起始地址
     * @param right 数组的结束地址
     * @param temp  用于临时存放数据的数组
     */
    public void mergeSortUp2Down(int[] a, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + ((right - left) >> 1);
            mergeSortUp2Down(a, left, mid, temp);
            mergeSortUp2Down(a, mid + 1, right, temp);
            merge(a, left, mid, right, temp);
        }
    }

    /**
     * 将一个数组中的两个相邻有序区间合并成一个
     *
     * @param a     包含两个有序区间的数组
     * @param left  第1个有序区间的起始地址。
     * @param mid   第1个有序区间的结束地址。也是第2个有序区间的起始地址。
     * @param right 第2个有序区间的结束地址。
     * @param temp  用于临时存放数据的数组
     */
    public void merge(int[] a, int left, int mid, int right, int[] temp) {
        int i = left;//第1个有序区间的索引
        int j = mid + 1;//第2个有序区间的索引
        int k = 0;//临时区间的索引

        //将两个有序区间中较小的数放到前面
        while (i <= mid && j <= right) {
            temp[k++] = a[i] < a[j] ? a[i++] : a[j++];
        }
        //若其中一个有序区间还有剩余，则将剩余元素添加到合并后的有序区间末尾
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        while (j <= right) {
            temp[k++] = a[j++];
        }

        //将排序后的元素，整合到原始数组中
        for (i = 0; i < k; i++) {
            a[left + i] = temp[i];
        }
    }

    /**
     * 归并排序(从下往上)
     *
     * @param temp  用于临时存放数据的数组
     */
    public void mergeSortDown2Up(int[] a, int[] temp) {
        if (a == null) {
            return;
        }
        for (int n = 1; n < a.length; n++) {
            mergeGroups(a, a.length, n, temp);
        }
    }

    /**
     * 对数组a做若干次合并：数组a的总长度为len，将它分为若干个长度为gap的子数组；将"每2个相邻的子数组"进行合并排序。
     *
     * @param a     待排序的数组
     * @param len   数组a的长度
     * @param gap   子数组的长度
     * @param temp  用于临时存放数据的数组
     */
    public void mergeGroups(int[] a, int len, int gap, int[] temp) {
        int i;
        int twoLen = 2 * gap;//两个相邻子数组的长度

        //将 每两个相邻子数组 进行合并排序
        for (i = 0; i + twoLen - 1 < len; i += twoLen) {
            merge(a, i, i + gap - 1, i + twoLen - 1, temp);
        }

        // 若 i+gap-1 < len-1，则剩余一个子数组没有配对。
        // 将该子数组合并到已排序的数组中。
        if (i + gap - 1 < len - 1) {
            merge(a, i, i + gap - 1, len - 1, temp);
        }
    }

    public static void main(String[] args) {
        int[] arr = getArr();
        int[] temp = new int[arr.length];

        System.out.printf("排序前：%s\n", Arrays.toString(arr));
        new E_MergeSort().mergeSortUp2Down(arr, 0, arr.length - 1, temp);
        System.out.printf("排序后：%s\n", Arrays.toString(arr));


        System.out.println();
        int[] arr2 = getArr();
        System.out.printf("排序前：%s\n", Arrays.toString(arr2));
        new E_MergeSort().mergeSortDown2Up(arr2, temp);
        System.out.printf("排序后：%s\n", Arrays.toString(arr2));
    }
}

排序前：[67, 9, 61, 91, 19, 87, 96, 70, 46, 42]
排序后：[9, 19, 42, 46, 61, 67, 70, 87, 91, 96]

排序前：[28, 17, 22, 39, 20, 73, 62, 55, 71, 70]
排序后：[17, 20, 22, 28, 39, 55, 62, 70, 71, 73]

8 计数排序

/*
https://www.runoob.com/w3cnote/counting-sort.html
https://zhuanlan.zhihu.com/p/125126086
https://zhuanlan.zhihu.com/p/470179124
 */
public class H_CountingSort extends MySortUtils {
    /*
     计数排序：

     1. 基本思想
     计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
     计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
     用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理：
         ① 分配。扫描一遍原始数组，以 当前值-minValue 作为下标，将该下标的计数器增1。
         ② 收集。扫描一遍计数器数组，按顺序把值收集起来。

     2. 实现逻辑
     ① 找出待排序的数组中最大和最小的元素
     ② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项【C[i] = freq(i)】
     ③ 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
     ④ 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
     */
    public void countingSortUnstable(int[] a) {
        // ① 找出待排序的数组中最大和最小的元素
        int minValue = a[0], maxValue = a[0];
        for (int i = 1; i < a.length; i++) {
            minValue = Math.min(minValue, a[i]);
            maxValue = Math.max(maxValue, a[i]);
        }
        // ②统计数组中每个值为val的元素出现的次数，存入数组C的第val项【C[val] = freq(val)】
        int[] C = new int[maxValue - minValue + 1];
        for (int val : a) {
            C[val - minValue]++;//数组a中元素val，在数组C中对应的下标为val-minValue
        }
        //从头遍历C，根据C中元素下标（每个下标对应原数组一个元素）、以及C每个元素的频数，对原数组排序
        int j = 0;
        for (int i = 0; i < C.length; i++) {
            while (C[i] > 0) {
                a[j++] = i + minValue;
                C[i]--;
            }
        }
    }

    /**
     * 上述计数排序仍存在一个稳定性缺陷，即通过计数来排序，当遍历到C[i]时，只是连续地输出C[i]次i + min，稳定性得不到保证。
     * 要保证稳定，必须使先记录的先输出。可以通过对C进行变形来满足稳定性，使得遍历到同一个数字，例如k时，能够将不同位置的k按他们
     * 在a中出现的顺序放入到输出数组中。具体做法是在得到C后，遍历一次C，使得每一个C[i]的值都是从C[0]到C[i]中值不为0的项的值之和：
     * for(int i = 1; i < n; i++) {
     * C[i] += C[i-1];
     * }
     * 例如对于待排序数组{5, 5, 4, 4, 1, 1}，得到大小为5-1+1=5的C，具体为{2, 0, 0, 2, 2}，表示有两个1，0个2，0个3，2个4，2个5。
     * 按照前述方法将其变形为{2, 0, 0, 4, 6}，表示1的最大位置为第2位(下标为1)，4的最大位置为4(下标为3)，5的最大位置为6(下标为5)。
     * 在输出排序结果时，新建一个大小等于a的sortedArr数组，于是C[a[i] - min] - 1即为a[i]这个数应当放入sortedArr的位置(下标)，
     * 即sortedArr[C[a[i] - min] - 1] = a[i]，以倒序从a.length遍历到0，每次向sortedArr填入一个数字后，令C[a[i] - min]--。
     * 遍历结束后得到的sortedArr即为a的稳定排序结果。
     *
     * @param a 待排序数组
     */
    public int[] countingSortStable(int[] a) {
        // ① 找出待排序的数组中最大和最小的元素
        int minValue = a[0], maxValue = a[0];
        for (int i = 1; i < a.length; i++) {
            minValue = Math.min(minValue, a[i]);
            maxValue = Math.max(maxValue, a[i]);
        }
        // ②统计数组中每个值为val的元素出现的次数，存入数组C的第val项【C[val] = freq(val)】
        int[] C = new int[maxValue - minValue + 1];
        for (int val : a) {
            C[val - minValue]++;//数组a中元素val，在数组C中对应的下标为val-minValue
        }

        // 将数组C变形
        for (int i = 1; i < C.length; i++) {
            C[i] += C[i - 1];
        }

        int[] sortedArr = new int[a.length];
        for (int i = a.length - 1; i >= 0; i--) {
            sortedArr[C[a[i] - minValue] - 1] = a[i];
            C[a[i] - minValue]--;
        }

        return sortedArr;
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(H_CountingSort.class, "countingSortUnstable");

        System.out.println("H_CountingSort.countingSortStable:");
        int[] arr = getArr();
        System.out.println("排序前：" + Arrays.toString(arr));
        int[] sortedArr = new H_CountingSort().countingSortStable(arr);
        System.out.println("排序后：" + Arrays.toString(sortedArr));
    }
}

H_CountingSort.countingSortUnstable:
排序前：[50, 9, 18, 55, 74, 41, 85, 17, 13, 38]
排序后：[9, 13, 17, 18, 38, 41, 50, 55, 74, 85]
H_CountingSort.countingSortStable:
排序前：[37, 81, 66, 19, 59, 54, 53, 42, 73, 27]
排序后：[19, 27, 37, 42, 53, 54, 59, 66, 73, 81]

9 桶排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
https://juejin.cn/post/7058920744603893767
https://www.cnblogs.com/bigsai/p/13396391.html
https://www.runoob.com/w3cnote/bucket-sort.html
看这个：
https://www.cnblogs.com/distance66/p/15145758.html
 */
public class I_BucketSort extends MySortUtils {
    public void bucketSort(int[] a) {
        int i;
        int n = a.length;
        int minValue = a[0], maxValue = a[0];
        for (i = 1; i < n; i++) {
            minValue = Math.min(minValue, a[i]);
            maxValue = Math.max(maxValue, a[i]);
        }

        //确定桶的数量，并初始化桶
        int bucketNum = (maxValue - minValue) / n + 1;
        ArrayList<List<Integer>> buckets = new ArrayList<>(bucketNum);
        for (i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<Integer>());
        }

        //将每个元素放入对应的桶内
        for (i = 0; i < n; i++) {
            int index = (a[i] - minValue) / n;
            buckets.get(index).add(a[i]);
        }

        //对每个桶排序。桶内的排序算法可自定义，由于此处使用了ArrayList，因此直接使用库函数内置的排序算法
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        //将每个桶内元素放入原数组
        i = 0;
        for (List<Integer> bucket : buckets) {
            for (int j = 0; j < bucket.size(); j++) {
                a[i++] = bucket.get(j);
            }
        }
    }

    public static void main(String[] args) {
        printArrayBeforeAndAfterSorting2(I_BucketSort.class, "bucketSort");
    }
}

I_BucketSort.bucketSort:
排序前：[50, 74, 47, 82, 92, 1, 53, 88, 25, 63]
排序后：[1, 25, 47, 50, 53, 63, 74, 82, 88, 92]

10 基数排序

/*
https://zhuanlan.zhihu.com/p/470179156
https://www.cnblogs.com/skywang12345/p/3603669.html
https://blog.csdn.net/weixin_43757333/article/details/112207811
 */
public class J_RadixSort extends MySortUtils {
    /**
     * 基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
     * <p>
     * 具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
     * 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
     * <p>
     * 以计数排序为基础的基数排序
     *
     * @param a
     */
    public void radixSortImplByCountingSort(int[] a) {
        int n = a.length;
        int[] sortedArr = new int[n];//按exp排序一次后的暂存数组
        int[] buckets = new int[19]; //为应对有负数的情况，buckets为范围为[-9, 9]

        //由于考虑数组中包含负数的情况，此处寻找数组中绝对值最大的数(位数最多)
        int maxDigit = Math.abs(a[0]);
        int i;
        for (i = 1; i < n; i++) {
            maxDigit = Math.max(maxDigit, Math.abs(a[i]));
        }

        /*
         按照 个位、十位、百位... 的顺序，每一轮都对当前位(基数)执行一次计数排序：
         (1) 当exp=1表示按照"个位"对数组a进行排序
         (2) 当exp=10表示按照"十位"对数组a进行排序
         (3) 当exp=100表示按照"百位"对数组a进行排序
         ...
         */
        for (int exp = 1; maxDigit / exp > 0; exp *= 10) {
            //将数据出现的次数存储在buckets[]中
            for (i = 0; i < n; i++) {
                //索引偏移9以处理负数
                int bucketIdx = (a[i] / exp) % 10 + 9;
                buckets[bucketIdx]++;
            }

            // buckets变形，目的是让更改后的buckets[i]的值，是该数据在sortedArr[]中的位置。参考计数排序稳定版(countingSortStable)
            for (i = 1; i < buckets.length; i++) {
                buckets[i] += buckets[i - 1];
            }

            // 将一趟排序后的结果存储到临时数组sortedArr[]中，逆序输出保持稳定性
            for (i = n - 1; i >= 0; i--) {
                int bucketIdx = (a[i] / exp) % 10 + 9;
                // buckets[bucketIdx]得到的从1开始计算的位置，转成下标要-1
                sortedArr[buckets[bucketIdx] - 1] = a[i];
                buckets[bucketIdx]--;
            }

            //完成当前位的计数排序后将排序结果拷贝回原数组
            System.arraycopy(sortedArr, 0, a, 0, n);
            Arrays.fill(buckets, 0);//buckets一定要清空
        }
    }

    //不以计数排序为基础的基数排序：用数组作为桶的实现
    public void radixSortImplByArray(int[] a) {
        int n = a.length;

        //由于考虑数组中包含负数的情况，此处寻找数组中绝对值最大的数(位数最多)
        int maxDigit = Math.abs(a[0]);
        int i;
        for (i = 1; i < n; i++) {
            maxDigit = Math.max(maxDigit, Math.abs(a[i]));
        }

        //n+1的数组：每个桶最后一个元素保存该桶中元素个数(currentBucketSize)
        int[][] buckets = new int[19][n + 1];
        for (int exp = 1; maxDigit / exp > 0; exp *= 10) {
            for (i = 0; i < n; i++) {
                //将元素放入其对应桶中
                int bucketIdx = (a[i] / exp) % 10 + 9;
                int currentBucketSize = buckets[bucketIdx][n];
                buckets[bucketIdx][currentBucketSize] = a[i];
                //桶中元素数量 +1
                buckets[bucketIdx][n]++;
            }

            //将当前所有桶的数按桶序，桶内按低到高输出为本轮排序结果
            i = 0;
            for (int j = 0; j < buckets.length; j++) {
                for (int k = 0; k < buckets[j][n]; k++) {
                    a[i++] = buckets[j][k];
                }
                //每一轮过后将桶计数归零
                buckets[j][n] = 0;
            }
        }
    }


    //不以计数排序为基础的基数排序：用链表作为桶的实现
    public void radixSortImplByLinkedList(int[] a) {
        int n = a.length;

        //由于考虑数组中包含负数的情况，此处寻找数组中绝对值最大的数(位数最多)
        int maxDigit = Math.abs(a[0]);
        int i;
        for (i = 1; i < n; i++) {
            maxDigit = Math.max(maxDigit, Math.abs(a[i]));
        }

        int bucketNum = 19;
        List<LinkedList<Integer>> buckets = new ArrayList<>(bucketNum);
        for (i = 0; i < bucketNum; i++) {
            buckets.add(new LinkedList<>());
        }
        for (int exp = 1; maxDigit / exp > 0; exp *= 10) {
            for (i = 0; i < n; i++) {
                //将元素放入其对应桶中
                int bucketIdx = (a[i] / exp) % 10 + 9;
                buckets.get(bucketIdx).add(a[i]);
            }

            //将当前所有桶的数按桶序，桶内按低到高输出为本轮排序结果
            i = 0;
            for (LinkedList<Integer> bucket : buckets) {
                Iterator<Integer> it = bucket.iterator();
                while (it.hasNext()) {
                    a[i++] = it.next();
                    it.remove();
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = getArr(-20000, 3000, 10);
        printArrayBeforeAndAfterSorting(J_RadixSort.class,"radixSortImplByCountingSort", arr);


        int[] arr2 = getArr(0, 20000, 10);
        printArrayBeforeAndAfterSorting(J_RadixSort.class,"radixSortImplByArray", arr2);


        int[] arr3 = getArr(-2000, 20000, 10);
        printArrayBeforeAndAfterSorting(J_RadixSort.class,"radixSortImplByLinkedList", arr3);
    }
}

J_RadixSort.radixSortImplByCountingSort:
排序前：[-6560, -4907, -9917, -11770, -4287, -10097, 2565, -6728, -17807, -18023]
排序后：[-18023, -17807, -11770, -10097, -9917, -6728, -6560, -4907, -4287, 2565]
J_RadixSort.radixSortImplByArray:
排序前：[8568, 2739, 10321, 10543, 5340, 12079, 19101, 15190, 2275, 12831]
排序后：[2275, 2739, 5340, 8568, 10321, 10543, 12079, 12831, 15190, 19101]
J_RadixSort.radixSortImplByLinkedList:
排序前：[12048, 9537, -1466, 15104, 1783, 10817, 9873, 6808, 19663, 11848]
排序后：[-1466, 1783, 6808, 9537, 9873, 10817, 11848, 12048, 15104, 19663]

3 算法执行效率

在排序算法中还有一个特殊的概念,即稳定排序算法。稳定排序算法主要依照相等的关键字维持记录的相对次序来进行排序。通俗地讲,对于两个有相等关键字的数据 D1 和 D2,在待排序的数据中 D1 出现在 D2 之前,在排序过后的数据中 D1 也在 D2 之前,那么这就是一个稳定排序算法。

冒泡排序算法、插入排序算法、合并排序算法都是稳定排序算法
选择排序算法、Shell排序算法、快速排序算法、堆排序算法都不是稳定排序算法。

没有一种排序算法是绝对好的,不同的排序算法各有优劣。在实际应用中,需要根据实际的问题来选择合适的排序算法。

如果数据量 n 较小,可采用插入排序法、选择排序法;
如果数据量 n 较大时,应采用时间复杂度为 O( $nlog_2n$ ) 的排序方法,如快速排序、堆排序、合并排序。
如果待排序的原始数据呈随机分布,那么快速排序算法的平均时间最短。

算法种类	时间复杂度(最好)	时间复杂度(平均)	时间复杂度(最坏)	空间复杂度	是否稳定
直接插入排序	$O (n)$	$O(n^2)$	$O(n^2)$	$O (1)$	√
冒泡排序	$O (n)$	$O(n^2)$	$O(n^2)$	$O (1)$	√
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	×
希尔排序	取决于	所选用的	增量函数	$O (1)$	×
快速排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$	$O(log_2n)$	×
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O (1)$	×
2路归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O (1)$	√
基数排序	$O (d (n + r))$	$O (d (n + r))$	$O (d (n + r))$	$O (r)$	√