数据排序-恶意代码分析实战英文原版pdf
134 ｜第五章自定义函数
[x, y]= polar2rect(5,143.1301)
x = -4.0000 y = 3.0000
[x, y]= polar2rect(5,-36.8699)
x = 4.0000 y = -3.0000
在笛卡尔坐标的四个象限内得到的结果均是正确的。
例5.2 数据排序
在许多科研和工程应用中，随机输入一组数据并对它进行由低到高排序或由高到低进行排序是十分必要的。假设你是一个动物学家，正在研究大量的动物，并想要鉴定这些动物最大的5%。解决这个问题的最直接的方法是对这些动物的大小按照降序进行排列，取其前5%。
对数据进行升序或降序排列似乎是一件非常容易的工作。毕竟，我们经常做这样的事。有一个简单的例子，把数据（10，3，6，4，9）按升序排列成（3，4，6，9，10）。我们应当怎样做呢？我们首先应当浏览整个输入数据列表（10，3，6，4，9），找出其中的最小值（3），然后浏览剩下的输入数据（10，6，4，9）并找到下一个最小值（4），然后继续重复上面的步骤，直到所有的列表中的所有数都能排完。
实际上，排序是一个非常困难的工作。当值的个数增加时，用上面简单的排序方法进行运算所消耗的时间将会迅速增加，因为每排一个数就要浏览一个遍输入值。对于大的数据集合，这个方法因太耗时，而不用。更糟糕的是，如果有大量的数据占有计算机的大部分内存，我们将如何排序？开发大数据集合的高效排序技术是一个相当活跃的研究领域，它已经成为了一个新的科目。
在这个例子中，我们将尽可能简单的算法来说明排序的内容。这个最简单的算法叫做选择性排序（selection sort）。它只是对应上面描述方法的计算机执行。选择性排序的基本算法如下：
-
浏览被排序数的列表，并找出其中的最小值。把最小值与排在最前面的数进行交换。如要排在最前面的数就是这个数表最小值，什么也不用做。
-
从这个数据列表的第二个数开始浏览找到第二个最小的数。把这个数与当前排在第二个数进行交换。如果当前排在第二位的数就是下一个最小值，那么什么也不用做。
-
从数据列表的第三个数开始找到第三个最小的数。把这个数与当前排在第三个数进行交换。如果当前排在第三位的数就是第三个最小值，那么什么也不用做。
-
重复以上步骤直至最后一位置排完。当最后一个位置排完后，排序结束。
注意: 如果我们要对N个数进行排序，这个排序算法要进行N-1次浏览才能完成排序。这个步骤的说明如图5.4所示。因为有5个数进行排序，所以要对数据进行4次浏览。首先对整个数据列表进行浏览，得到最小值3，把3置于第一位，故与10进行交换。从第二位开始浏览，得到第二个最小值4，与10交换。从第三位进行浏览，得到最小值6，6恰在第三位上，不用交换。从第四位开始浏览，得到最小值9，与排在第4位的10交换。排序结束。
性能提示
选择性排序算法是一种极易理解的编程算法，但它的效率是极低的。我们绝不能用它进行大数据集合的排序（例如含有1000个元素的数组）。这些年来，计算机专家已经发展了许多高效的排序算法。MATLAB中的sort函数和sortrows函数就是非常高效的，在实际工作中广泛使用。你是否好奇其他的排序算法如何实现？看看这个选择性排序的实现吧，也许会有更多的发现！
使用这些高效的排序算法，你不仅能提高工作效率，还能更快地处理大量数据。科学的进步和工程的发展，正是依赖于这些基础算法的不断优化与创新。谁能想到，看似简单的排序问题背后竟隐藏着如此多的学问呢！
