算法之排序

假定，你要为你的生日聚会邀请你的朋友和亲戚。对此，你需要给他们打电话。你正在拥有10,000条记录的电话本中查找名为Steve的电话号码。然而，电话本中的记录是以随意顺序存储的。要在这样一个目录中查找你朋友的电话号码，你需要按顺序在目录中浏览每个条目。这将非常耗时，你如何解决此问题呢？
    

节省时间和高效搜索数据的简单解决方案是排序。
排序是按照某些预定义的顺序或序列排列数据的过程。此顺序可以是升序或降序。
如果数据被排序，则可以直接转到存储以‘S’开头的姓名部分，因此减少了要遍历的记录数。

选择排序算法

通过使用一算法实现在程序中排序。
一些排序算法有：
冒泡（Bubble）排序
选择排序
插入排序
壳（Shell）排序
合并排序
快速排序
堆排序
要选择合适的算法，你需要考虑以下方面：
执行时间
存储空间
编程工作

冒泡排序算法：
是最简单的排序算法之一
此算法具有二次方程增长阶，因此适合仅排序小列表
通过列表重复扫描、比较相邻元素和按错误顺序交换，此算法会有作用.

编写一算法以实现冒泡排序。
冒泡排序的算法是：
1.设置通道(圈数) = 1。
2.重复步骤3  区分0到n – 1通道中的j。
1.如果索引j处的元素大于索引j + 1处的元素，则交换这两个元素。
3.按1递增通道;圈数加1
4.如果通道 <= n-1，则转到第2步。

排序算法的效率按照比较次数来测量。
在冒泡排序中，通道1内有n– 1 次比较，通道2中有n– 2次比较，依此类推。
比较总数= (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1= n(n– 1)/2。
n(n – 1)/2是O(n2)阶的级数。因此，冒泡排序算法是阶O(n2)的算法。

什么是冒泡排序算法的增长阶？
答案：
n – 1 次比较

答案：
冒泡排序算法具有二次方增长阶

当实现冒泡排序算法时，在通道1中将执行多少次比较？
答案：
n –1次比较

使用选择排序来排序数据

选择排序算法：
选择排序还具有二次方程增长阶，且因此仅适用于排序小的列表。
选择排序通过列表反复扫描，每次扫描选择一项，然后将这一项移动到列表中正确的位置。

要理解选择排序算法的实现，考虑数组中存储的未排序的数字列表。每次都寻找最小值，将最小值往前放

编写一算法以实现选择排序。
选择排序的算法：
1.重复步骤2和3区分0到n -2通道中的j
2.找出arr[j]到arr[n– 1]中的最小值：
a.设置min_index = j
b.重复步骤c区分j + 1到n – 1的i
c.如果arr[i] < arr[min_index]:
  i.   min_index = i
3.将arr[j]与arr[min_index]交换

在选择排序中，在查找最小元素的通道1中有n– 1次比较。在查找第二个最小元素的通道2中有n -2次比较，依此类推。
比较总数 = (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1 =n(n– 1)/2
n(n – 1)/2是O(n2)阶的级数。因此，选择排序算法是阶O(n2)的算法。

插入排序算法：
具有二次方程增长阶，且因此仅用于排序小列表。
如果需要排序的列表几乎已经排序，则插入排序比冒泡排序和选择排序更有效率。

要理解插入排序算法的实现，考虑数组中存储的未排序的数字列表。

要使用插入排序算法排序此列表：
你需要将列表分为两个子列表，即排序和未排序。

若要通过使用插入排序排序大小为n的列表，您需要执行(n– 1) 次通道。
最佳用例效率：
当列表已经被排序时产生最佳用例。
在这种情况下，您必须在每个通道中仅做一次比较。
在n– 1次通道中，您将需要做n– 1次比较。
插入排序的最佳用例效率是O(n)阶的。
最糟用例效率：
当列表按反向顺序排序时产生最糟用例效率。
在这种情况下，您需要在第1个通道中做1次比较，在第二个通道中做2次比较，在第3个通道中做3次比较，在第n– 1 个通道中做n – 1次比较。
插入排序的最糟用例效率是O(n2)阶的。

销售经理对2004-2006念市场上最佳冷饮销售员进行调查。David是一名软件开发人员，他有一个冷饮品牌及其销售数据的文件。 David 必须向销售经理提供排序好的数据。文件总的数据或多或少都要进行排序。存储此数据最有效率的排序算法是哪个？为什么？
记录是以随意顺序存储的。    

答案：
当列表部分排序时，插入排序提供了比泡泡排序和选择排序更好的有效。因此David应使用插入排序算法。

壳排序算法：
只要此列表已经部分排序且造成平均用例中的无效解决方案，则插入算法是高效算法。
为了克服此限制，计算机科学家D.L. Shell提议改进插入排序算法。
新的算法称为壳（Shell）排序，是按照他的姓名命名的。

壳排序：
通过按若干位置的距离形成多个子列表分隔元素并进行比较来改进插入排序算法
对每个子列表应用插入排序使元素朝着其正确的位置移动
帮助元素快速靠近正确的位置，因此减少了比较的次数

小结

在本章中，你已经学到：
排序是按照某些预定义的顺序或关键值排列数据的过程。此顺序可以是升序或降序。
用于排序数据有各种排序算法。其中一些如下：
冒泡排序
选择排序
插入排序
壳排序
合并排序
快速排序
堆排序

若要选择合适的算法，您需要考虑以下内容：
执行时间
存储空间
编程工作
冒泡排序和选择排序算法具有二次方程增长阶，且因此仅适用于排序小的列表。
插入排序执行不同次数的比较，这取决于最初的元素分阶。当元素已经处于排序阶，则插入排序需要进行极少比较。
如果需要排序的列表几乎已经排序，则插入排序比冒泡排序和选择排序更有效率。

通过比较按若干位置的距离分隔的元素，壳排序改善了插入排序。这帮助元素快速靠近正确的位置，因此减少了比较的次数。