Recursive Sorting Algorithms

欢迎回来！

现在，我们知道递归，我们可以谈论编程中的一个重要主题 - 递归分类算法！

如果您查看pointers博客文章，我们介绍泡沫排序，这是一种迭代排序算法。气泡排序的问题在于它具有O（n^2）的平均时间复杂性，这意味着对于每个n个项目，都需要n^2操作。

Today, we’re going to go over quick-sort and merge-sort, both of which have an average time complexity of O(n*log(n)). What’s the difference between O(n^2) and O(n*log(n))? Let’s make a small chart to show the differences.

右边的时间部分假设我们的计算机可以每千分之一秒钟进行一次操作（按照现代标准，这很慢，但仍然很好地显示出差异）。当“ n”非常大（例如一百万）时，o（n^2）算法将花费大约31年才能完成（或直到2046年），而0（n*log（n））将花费大约100分钟，这对于对一百万个项目进行排序非常合理。

So why even bother with bubble-sort if there are sorting algorithms that are so much more efficient? Bubble-sort does have advantages, especially if space is an issue. But today we aren’t really going to worry about that.
Merge-Sort

信用Wikimedia Commons.

Mergesort is a divide-and-conquer algorithm that divides an array of lengthnintonsubarrays, and then recombines them using merge. Our Mergesort has two main functions:mergesort和merge.
mergesort

Mergesort is our recursive call, we take our array that has been passed into mergesort, then wedividethe array into two halves and call mergesort recursively. This continues until each array has a size of 1. Then we return and merge (conquer). If we check out the code before we call mergesort again, you can see that there is the base case, and after that, the array list is being divided and moved into two smaller arrays.

Merge takes two arrays, and combines them. The two arrays have both been sorted by a previous call (except arrays with size 1, which can’t really be sorted). Then the arrays are sorted by checking the lowest value and moving them into a third array. The mergesort gif above is a really good way to show how merge sort works.

Mergesort Code

Here we have a small main that calls mergesort!

QuickSort

信用Wikipedia.

QuickSort没有将数组分为Mergesort等n个细分，而是使用分区将数组分为子阵列。子阵列的划分由枢轴点决定，该枢轴点由算法决定（如数组中的第一个或最后一个变量），然后将所有值小于枢轴点移动到一侧，然后将较高的值移至另一边。我们的QuickSort实施中有四个功能：交换，分区和两个QuickSorts（一个只是为了易于使用）。

Swap is a small function that switches to values of a list using the input parametersleft和right.

分区是QuickSort的“肉”，我们的QuickSort实施将低点的首个值作为枢轴点，并将基于该点的数组分配。

Our quicksort functions are not too difficult, most of the work is done in partition. Here we call partition to divide list, and then call Quicksort recursively until we reach our base case. If you check out our main for Mergesort main, we call mergesort(B, N). We’ve changed this in quicksort by using function overloading, now in our main we can either callquickSort(list, 0, N-1), which will start partitioning at 0 and N-1, orquickSort(list), which then calls quickSort with the partition calls.

QuickSort代码
Here’s an example of us calling quicksort!

比较代码
这是QuickSort和Bubblesort之间的效率比较。使用50000个随机生成的值，我们可以花费每个函数来分类相同数组的时间。时间在几秒钟内显示，因此您可以自己尝试一下！

(Note: You can change N to more or less, and this will make change the amount of values to be sorted. 50000 was a good number to show the differences.)