数据结构与算法之ACM Fellow-算法 2.1 初级排序算法
数据结构与算法之ACM Fellow-算法 2.1 初级排序算法作为对排序算法领域的第一次探索，我们将学习两种初级的排序算法以及其中一种的一个变体。深入学习这些相对简单的算法的原因在于：第一，我们将通过它们熟悉一些术语和简单的技巧；第二，这些简单的算法在某些情况下比我们之后将会讨论的复杂算法更有效；第三，以后你会发现，它们有助于我们改进复杂算法的效率。
2.1.1 游戏规则
我们关注的主要对象是重新排列 数组元素 的算法，其中每个元素都有一个 主键。排序算法的目标就是将所有元素的主键按照某种方式排列（通常是按照大小或是字母顺序）。排序后索引较大的主键大于等于索引较小的主键。元素和主键的具体性质在不同的应用中千差万别。在 Java 中，元素通常都是对象，对主键的抽象描述则是通过一种内置的机制（请见 2.1.1.4 节中的 Comparable 接口）来完成的。
“排序算法类模版”中的 Example 类展示了我们的习惯约定：我们会将排序代码放在类的 sort() 方法中，该类还将包含辅助函数 less() 和 exch()（可能还有其他辅助函数）以及一个示例用例 main()。 Example 类还包含了一些早期调试使用的代码：测试用例 main() 将标准输入得到的字符串排序，并用私有方法 show() 打印字符数组的内容。我们还会在本章中遇到各种用于比较不同算法并研究它们的性能的测试用例。为了区别不同的排序算法，我们为相应的类取了不同的名字，用例可以根据名字调用不同的实现，例如 Insertion.sort()、 Merge.sort()、 Quick.sort() 等。
大多数情况下，我们的排序代码只会通过两个方法操作数据： less() 方法对元素进行比较， exch() 方法将元素交换位置。 exch() 方法的实现很简单，通过 Comparable 接口实现 less() 方法也不困难。将数据操作限制在这两个方法中使得代码的可读性和可移植性更好，更容易验证代码的正确性、分析性能以及排序算法之间的比较。在学习具体的排序算法实现之前，我们先讨论几个对于所有排序算法都很重要的问题。
排序算法类的模板
public class Example
{
public static void sort(Comparable[] a)
{/* 请见算法2.1、算法2.2、算法2.3、算法2.4、算法2.5或算法2.7*/}
private static boolean less(Comparable v, Comparable w)
{return v.compareTo(w) < 0;}
private static void exch(Comparable[] a, int i, int j)
{Comparable t = a; a = a; a = t;}
private static void show(Comparable[] a)
{// 在单行中打印数组
for (int i = 0; i < a.length; i++)
StdOut.print(a + " ");
StdOut.println();
}
public static boolean isSorted(Comparable[] a)
{// 测试数组元素是否有序
for (int i = 1; i < a.length; i++)
if (less(a, a))return false;
return true;
}
public static void main(String[] args)
{// 从标准输入读取字符串，将它们排序并输出
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}% more tiny.txt
S O R T E X A M P L E
% java Example < tiny.txt
A E E L M O P R S T X
% more words3.txt
bed bug dad yes zoo ... all bad yet
% java Example < words.txt
all bad bed bug dad ... yes yet zoo这个类展示的是数组排序实现的框架。对于我们学习的每种排序算法，我们都会为这样一个类实现一个 sort() 方法并将 Example 改为算法的名称。测试用例会将标准输入得到的字符串排序，但是这段代码使我们的排序方法适用于任意实现了 Comparable 接口的数据类型。
2.1.1.1 验证
无论数组的初始状态是什么，排序算法都能成功吗？谨慎起见，我们会在测试代码中添加一条语句 assert isSorted(a); 来确认排序后数组元素都是有序的。尽管一般都会测试代码并从数学上证明算法的正确性，但在实现 每个 排序算法时加上这条语句仍然是必要的。需要注意的是，如果我们只使用 exch() 来交换数组的元素，这个测试就足够了。当我们直接将值存入数组中时，这条语句无法提供足够的保证（例如，把初始输入数组的元素全部置为相同的值也能通过这个测试）。
2.1.1.2 运行时间
我们还要评估算法的 性能。首先，要计算各个排序算法在不同的随机输入下的基本操作的次数（包括比较和交换，或者是读写数组的次数）。然后，我们用这些数据来估计算法的相对性能并介绍在实验中验证这些猜想所使用的工具。对于大多数实现，代码风格一致会使我们更容易作出对性能的合理猜想。
排序成本模型。在研究排序算法时，我们需要计算 比较 和 交换 的数量。对于不交换元素的算法，我们会计算 访问数组的次数。
2.1.1.3 额外的内存使用
排序算法的额外内存开销和运行时间是同等重要的。排序算法可以分为两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的 原地排序算法，以及需要额外内存空间来存储另一份数组副本的其他排序算法。
2.1.1.4 数据类型
我们的排序算法模板适用于任何实现了 Comparable 接口的数据类型。遵守 Java 惯例的好处是很多你希望排序的数据都实现了 Comparable 接口。例如，Java 中封装数字的类型 Integer 和 Double，以及 String 和其他许多高级数据类型（如 File 和 URL）都实现了 Comparable 接口。因此你可以直接用这些类型的数组作为参数调用我们的排序方法。例如，右上方的代码使用了快速排序（请见 2.3 节）来对 N 个随机的 Double 数据进行排序。
Double a[] = new Double;
for (int i = 0; i < N; i++)
a = StdRandom.uniform();
Quick.sort(a);将!(images/740936/image00798个随机值的数组排序
在创建自己的数据类型时，我们只要实现 Comparable 接口就能够保证用例代码可以将其排序。要做到这一点，只需要实现一个 compareTo() 方法来定义目标类型对象的 自然次序，如右侧的 Date 数据类型所示（参见表 1.2.12）。
740936/image01095
定义一个可比较的数据类型
对于 vw 三种情况，Java 的习惯是在 v.compareTo(w) 被调用时分别返回一个负整数、零和一个正整数（一般是 -1、0 和 1）。为了节约篇幅，我们接下来用 v>w 来表示 v.compareTo(w)>0 这样的代码。一般来说，如果 v 和 w 无法比较或者两者之一是 null， v.compareTo(w) 将会抛出一个异常。此外， compareTo() 必须实现一个 全序关系，即：
<ul>自反性，对于所有的 v， v=v；
反对称性，对于所有的 vw，且 v=w 时 w=v；
传递性，对于所有的 v、 w 和 x，如果 v= h && less(a, a); j -= h) exch(a, j, j-h); } h = h/3; }}// less()、exch()、isSorted()和main()方法见“排序算法类模板”}如果我们在插入排序（算法 2.2）中加入一个外循环来将 h 按照递增序列递减，我们就能得到这个简洁的希尔排序。增幅 h 的初始值是数组长度乘以一个常数因子，最小为 1。
public class Selection
{
public static void sort(Comparable[] a)
{// 将a[]按升序排列
int N = a.length; // 数组长度
for (int i = 0; i < N; i++)
{// 将a和a中最小的元素交换
int min = i; // 最小元素的索引
for (int j = i+1; j < N; j++)
if (less(a, a)) min = j;
exch(a, i, min);
}
}
// less()、exch()、isSorted()和main()方法见“排序算法类模板”
}740936/image01106
希尔排序的轨迹（每遍排序后的数组内容）
</blockquote>如何选择递增序列呢？要回答这个问题并不简单。算法的性能不仅取决于 h，还取决于 h 之间的数学性质，比如它们的公因子等。有很多论文研究了各种不同的递增序列，但都无法证明某个序列是“最好的”。算法 2.3 中递增序列的计算和使用都很简单，和复杂递增序列的性能接近。但可以证明复杂的序列在最坏情况下的性能要好于我们所使用的递增序列。更加优秀的递增序列有待我们去发现。
和选择排序以及插入排序形成对比的是，希尔排序也可以用于大型数组。它对任意排序（不一定是随机的）的数组表现也很好。实际上，对于一个给定的递增序列，构造一个使希尔排序运行缓慢的数组并不容易。希尔排序的轨迹如图 2.1.3 所示，可视轨迹如图 2.1.4 所示。
740936/image01107
图 2.1.3 希尔排序的详细轨迹（各种插入）
740936/image01108
图 2.1.4 希尔排序的可视轨迹
通过 SortCompare 可以看到，希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。在继续学习之前，请在你的计算机上用 SortCompare 比较一下希尔排序和插入排序以及选择排序的性能，数组的大小按照 2 的幂次递增（见练习 2.1.27）。你会看到希尔排序能够解决一些初级排序算法无能为力的问题。这个例子是我们第一次用实际应用说明一个贯穿本书的重要理念： 通过提升速度来解决其他方式无法解决的问题是研究算法的设计和性能的主要原因之一。
研究希尔排序性能需要的数学论证超出了本书范围。如果你不相信，可以从证明下面这一点开始： 当一个“h 有序”的数组按照增幅 k 排序之后，它仍然是“h 有序”的。至于算法 2.3 的性能，目前最重要的结论是 它的运行时间达不到平方级别。例如，已知在最坏的情况下算法 2.3 的比较次数和 !(images/740936/image00958 成正比。有意思的是，由插入排序到希尔排序，一个小小的改变就突破了平方级别的运行时间的屏障。这正是许多算法设计问题想要达到的目标。
在输入随机排序数组的情况下，我们在数学上还不知道希尔排序所需要的平均比较次数。人们发明了很多递增序列来渐进式地改进最坏情况下所需的比较次数（!(images/740936/image01109），但这些结论大多只有学术意义，因为对于实际应用中的 !(images/740936/image00798 来说它们的递增序列的生成函数（以及与 !(images/740936/image00798 乘以一个常数因子）之间的区别并不明显。
在实际应用中，使用算法 2.3 中的递增序列基本就足够了（或者是本节最后的练习中提供的一个递增序列，它可能可以将性能改进 20% ～ 40%）。另外，很容易就能验证下面这个猜想。
性质 E。使用递增序列 1, 4, 13, 40, 121, 364… 的希尔排序所需的比较次数不会超出N的若干倍乘以递增序列的长度。
例证。记录算法2.3中比较的数量并将其除以使用的序列长度是一道简单的练习（请见练习 2.1.12）。大量的实验证明平均每个增幅所带来的比较次数约为 !(images/740936/image01110，但只有在N很大的时候这个增长幅度才会变得明显。这个性质似乎也和输入模型无关。
有经验的程序员有时会选择希尔排序，因为对于中等大小的数组它的运行时间是可以接受的。它的代码量很小，且不需要使用额外的内存空间。在下面的几节中我们会看到更加高效的算法，但除了对于很大的 !(images/740936/image00798，它们可能只会比希尔排序快两倍（可能还达不到），而且更复杂。如果你需要解决一个排序问题而又没有系统排序函数可用（例如直接接触硬件或是运行于嵌入式系统中的代码），可以先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。
如果您想了解更多技术资源，课件对应视频地址。欢迎点击这里1查看
如果您想了解更多技术资源，欢迎点击这里2查看
本文由博客一文多发平台 OpenWrite 发布！
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]