这篇文章主要介绍“编程中递归与排序分别是什么”，在日常操作中，相信很多人在编程中递归与排序分别是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”编程中递归与排序分别是什么”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
一个问题的解可以分为几个子问题的解
此问题与子问题，除了数据规模不一样，求解思路完全一样
存在递归终止条件
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
如果递归调用层很深，则有可能会出现堆栈溢出；可通过限制最大深度解决此问题：超过一定的深度直接返回报错。
通过散列表保存已求解过的表达式；当递归调用到此表达式时，先判断是够已求解过。
最常见的排序：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。
最好、最坏、平均情况时间复杂度
时间复杂度的系数、常数、低阶
比较次数和交换(或移动)次数
算法的内存消耗可以通过空间复杂度来衡量；原地排序特指空间复杂度为O(1)的排序算法
待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
稳定的排序算法可以保持相同的两个对象，在排序之后的前后顺序不变。
冒泡排序只操作相邻的两个元素，每次操作时比较相邻的两个元素判断是否满足大小关系要求，不满足时就交换位置。
从执行效率上看：冒泡排序的最好情况时间复杂度为O(n),最坏情况时间复杂度为O(n^2 ),平均情况时间复杂度为O(n^2 )。
从内存消耗上看：冒泡排序只涉及相邻元素交换操作，所以空间复杂度为O(1),是一个原地排序算法。
从稳定性上看：相邻两个元素大小相等时我们不做交换，所以大小相等的两个元素在排序后顺序不会改变，属于稳定的排序算法。
public static <T extends Comparable> 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 extends Comparable> 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 extends Comparable> 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 )的排序算法：
到此，关于“编程中递归与排序分别是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
