编程中递归与排序分别是什么

这篇文章主要介绍"编程中递归与排序分别是什么"，在日常操作中，相信很多人在编程中递归与排序分别是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"编程中递归与排序分别是什么"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

递归

递归需要满足的三个条件

• 一个问题的解可以分为几个子问题的解

• 此问题与子问题，除了数据规模不一样，求解思路完全一样

• 存在递归终止条件

怎么写递归代码

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归注意事项

警惕堆栈溢出

如果递归调用层很深，则有可能会出现堆栈溢出；可通过限制最大深度解决此问题：超过一定的深度直接返回报错。

避免重复计算

通过散列表保存已求解过的表达式；当递归调用到此表达式时，先判断是够已求解过。

排序

最常见的排序：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

如何分析一个算法

排序算法的执行效率

• 最好、最坏、平均情况时间复杂度

• 时间复杂度的系数、常数、低阶

• 比较次数和交换(或移动)次数

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量；原地排序特指空间复杂度为O(1)的排序算法

排序算法的稳定性

待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
稳定的排序算法可以保持相同的两个对象，在排序之后的前后顺序不变。

冒泡排序

冒泡排序只操作相邻的两个元素，每次操作时比较相邻的两个元素判断是否满足大小关系要求，不满足时就交换位置。

• 从执行效率上看：冒泡排序的最好情况时间复杂度为O(n),最坏情况时间复杂度为O(n^2 ),平均情况时间复杂度为O(n^2 )。

• 从内存消耗上看：冒泡排序只涉及相邻元素交换操作，所以空间复杂度为O(1),是一个原地排序算法。

• 从稳定性上看：相邻两个元素大小相等时我们不做交换，所以大小相等的两个元素在排序后顺序不会改变，属于稳定的排序算法。

代码实现

public static  T[] bubbleSort(T[] arrays) {    for (int i = 0; i < arrays.length; i++) {        boolean unUse = true;        for (int j = 1; j < arrays.length - i; j++) {            //如果前一个元素大于当前元素 就交换双方位置            if (arrays[j - 1].compareTo(arrays[j]) > 0) {                T t = arrays[j - 1];                arrays[j - 1] = arrays[j];                arrays[j] = t;                unUse = false;            }        }        //如果整轮下来没有交换动作，说明排序已完成        if (unUse) break;    }    return arrays;}

插入排序

插入排序将数组分为已排序区和未排序区，核心思想是取未排序区的元素在已排序区中找到合适的位置插入，保证已排序区的数据一直是有序的。

• 从执行效率上看，插入排序的最好情况时间复杂度为O(n),最坏情况时间复杂度为O(n^2 ),平均情况时间复杂度为O(n^2 )。

• 从内存消耗上看：插入排序也不需要额外的存储空间，所以空间复杂度为O(1),是一个原地排序算法。

• 从稳定性上看：对于值相同的元素，后面出现的元素插入到前面出现元素的后面，所以两个元素在排序后顺序不会改变，属于稳定的排序算法。

代码实现

public static  T[] insertionSort(T[] arrays) {    if (arrays.length < 2) return arrays;    for (int i = 1; i < arrays.length; i++) {        T t = arrays[i];        for (int j = 0; j < i; j++) {            if (t.compareTo(arrays[j]) < 0) {                System.arraycopy(arrays, j, arrays, j + 1, i - j);                arrays[j] = t;                break;            }        }    }    return arrays;}

选择排序

选择排序也是将数据分为已排序区和未排序区，和插入排序不同的是：每次将未排序区中最小的元素放入到已排序区的尾部。

• 从执行效率上看，插入排序的最好情况时间复杂度为O(n^2 ),最坏情况时间复杂度为O(n^2 ),平均情况时间复杂度也为O(n^2 )。

• 从内存消耗上看：选择排序也不需要额外的存储空间，所以空间复杂度为O(1),是一个原地排序算法。

• 从稳定性上看：未排序区最小元素与首元素交换位置时，可能会改变相同值的两个元素的顺序，所以选择排序属于不稳定的排序算法。

代码实现

public static  T[] selectionSort(T[] arrays) {    if (arrays.length < 2) return arrays;    for (int i = 0; i < arrays.length; i++) {        int minIndex = i;//定义最小值索引        T min = arrays[minIndex];//默认第一个是最小值        for (int j = i + 1; j < arrays.length; j++) {            if (arrays[j].compareTo(min) < 0) {                minIndex = j;                min = arrays[minIndex];            }        }        //交换值        arrays[minIndex] = arrays[i];        arrays[i] = min;    }    return arrays;}

总结

我们从执行效率、内存消耗和稳定性三个方面分析了三种时间复杂度为O(n^2 )的排序算法：

到此，关于"编程中递归与排序分别是什么"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！