论文部分内容阅读
有一些基础的同学,一定学过一些排序的算法,如冒泡 法、插入法。这些算法很容易掌握,用它们排序通常需要两 重循环,对于n个数据,算法的时间复杂度为0(n2),效率 是比较低的。当n达到几万甚至十几万时,程序会运行得相 当缓慢。 下面介绍一种效率较高的算法。排序的过程是:取出待 排序数据之一(称为基准数据),并将数据分为两部分,使 得基准数据一侧的数据皆小于基准数据,另一侧的数据皆大于 基准数据,如果某一侧的数据至少有2个,则对这一侧的数 据递归地进行同样操作。 问题的难点在于,如何完成“将数据分为两部分”这 一步。我们以下面的数据为例(需要对其进行升序排列), 介绍一种较好的方法:
There are some basic students who must have learned some sort of algorithm, such as bubbling method, insert method. These algorithms are easy to grasp. Sorting them often requires two cycles. For n data, the time complexity of the algorithm is 0 (n2) and the efficiency is relatively low. When n reaches tens or even tens of thousands, the program will run slowly. The following introduces a more efficient algorithm. The sorting process is: taking out one of the data to be sorted (referred to as reference data), and dividing the data into two parts, so that the data on the side of the reference data is all less than the reference data, and the data on the other side is larger than the reference data, if If there is at least two data on one side, the same operation is performed recursively on the data on this side. The difficulty of the problem lies in how to complete the “divide the data into two parts” step. We use the following data as an example (you need to sort them in ascending order) to introduce a better method: