递归排序算法与非递归排序算法

Question

有人能用英语解释一下排序算法的非递归实现和递归实现有什么不同吗？

Answer 1

递归排序算法的工作原理是将输入拆分为两个或多个较小的输入，然后对这些输入进行排序，然后合并结果。Merge sort和quick sort是递归排序算法的示例。

非递归技术是指任何不使用递归的技术。Insertion sort是一个非递归排序算法的简单示例。

Answer 2

它们有什么不同，在什么意义上？请记住:任何递归算法都可以作为迭代算法实现，反之亦然(请查看此post)。迭代或递归-这只是一个实现细节；尽管它可以根据选择对性能产生重大影响，但算法将是相同的。

Answer 3

递归排序算法调用自身对数组的较小部分进行排序，然后组合部分排序的结果。快速排序就是一个例子。

非递归算法一次完成所有排序，而不调用自身。冒泡排序是一个非递归算法的例子。