第7章 排序
随着信息科技的逐渐普及与全球国际化的影响，企业所拥有的数据量成倍数的增长。无论是庞大的商业应用软件，还是小至个人的文字处理软件，每项工作的核心都与数据库有着莫大的关系，而数据库中最常见且重要的功能就是排序与查找，如图7.1所示。
图7.1 现在每项工作的核心都与数据库关系密切
“排序”（sorting）是指将一组数据，按特定规则调换位置，使数据具有某种顺序关系（递增或递减）。例如数据库内可针对某一字段进行排序，而此字段称为“键（key）”，字段里面的值我们称之为“键值（key value）”。
7.1 排序简介
在排序的过程中，数据的移动方式可分为“直接移动”和“逻辑移动”两种。“直接移动”是直接交换存储数据的位置，而“逻辑移动”并不会移动数据存储的位置，仅改变指向这些数据的辅助指针的值。如图7.2和图7.3所示。
图7.2 直接移动排序
图7.3 逻辑移动排序
两者间的优劣在于直接移动会浪费许多时间进行数据的移动，而逻辑移动只要改变辅助指针指向的位置就能轻易达到排序的目的。例如在数据库中，可在报表中可显示多项记录，也可以针对这些字段的特性来分组并进行排序与汇总，这就是属于逻辑移动，而不是去实际移动改变数据在数据文件中的位置，如图7.4所示。
图7.4 数据库使用的是逻辑移动排序
7.1.1 排序的分类
排序通常按照数据量的多寡和所使用的内存可分为“内部排序”（internal sort）和“外部排序”（external sort），数据量小则可以全部加载到内存（如RAM）来进行的排序就称为内部排序，大部分排序属于此类。数据量大无法全部一次性加载到内存，必须借助磁带、磁盘等辅助存储器进行排序则称为外部排序。
以上只是粗略的区分，其实随着数据结构科学的进步，陆续提出了如冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序法、堆积排序法、希尔排序法、基数排序法、直接合并排序法等等，各有其特色与应用场合。
就排序法的选择来说，当数据量相当大时，排序算法所花费的时间就显得相当重要；一个排序法是否为一种有效率（efficiency）的排序法，取决于其时间复杂度，而时间复杂度的决定因素则是排序过程中数据的交换次数及其比较次数的多少。
排序前：21 34 45 56 77 81
排序后：81 77 56 45 34 21
【这种排序的时间复杂度就是最坏情况】
时间复杂度可分为最好情况（best case）、最坏情况（worst case）及平均情况（average case）。最好情况就是数据已完成排序，例如原本数据已经完成升序了，如果再进行一次升序所使用的时间复杂度就是最好情况。最坏情况是指每一个键值均须重新排列，简单的例子就如原本为升序现在要重新排序成为降序，就是最坏情况。而空间复杂度就是指算法在执行过程所需占用的额外内存空间，排序法所使用到的额外空间越少，它的空间复杂度就越佳，例如冒泡法在排序过程中仅会用到一个额外的空间，在所有的排序算法中，这样的空间复杂度就算是最好的。
7.2 内部排序法
在正式讨论排序法之前，还要来讨论排序的稳定度，因为并非所有排序法都是稳定排序法。所谓稳定的排序是指数据在经过排序后，两个相同键值的记录仍然保持原来的顺序，如下例中30左的原始位置在30右的左边（所谓30左和30右是指相同键值一个在左而一个在右），稳定的排序（Stable Sort）后30左仍应在30右的左边，不稳定排序则有可能30左会跑到30右的右边去：
原始数据顺序： 30左 10 65 30右 21
稳定的排序： 10 21 30左 30右 65
不稳定的排序： 10 21 30右 30左 65
事实上，每一种排序方法都有其适用的情况与数据种类。建议大家要充分了解排序算法的过程及其所花费的时间与空间复杂度。
7.2.1 冒泡排序法
冒泡排序法又称为交换排序法，是从观察水中气泡变化构思而成，原理是从第一个元素开始，比较相邻元素的大小，若大小顺序有误，则对调后再进行下一个元素的比较，就仿佛气泡逐渐从水底逐渐冒升到水面上一样。如此扫描过一次之后就可确保最后一个元素是位于正确的顺序。接着再逐步进行第二次扫描，直到完成所有元素的排序关系为止。
以下使用55、23、87、62、16数列的演示排序过程，这样大家可以清楚地知道冒泡排序法的具体流程。图7.5为原始顺序，图7.6到7.9为排序的具体过程。
从小到大排序：
图7.5 排序前的原始位置
图7.6 冒泡排序的第一次扫描
第一次扫描会先拿第一个元素55和第二个元素23进行比较，如果第二个元素小于第一个元素，则进行互换。接着拿55和87进行比较，就这样一直比较并互换，到第4次比较完后即可确定最大值在数组的最后面。
图7.7 冒泡排序的第二次扫描
第二次扫描也是从头比较，但因为最后一个元素在第一次扫描就已确定是数组中的最大值，故只需比较3次即可把剩余数组元素的最大值排到剩余数组的最后面。
第三次扫描完，完成3个值的排序，如图7.8所示。
图7.8 冒泡排序的第三次扫描
第四次扫描完，即可完成所有排序，如图7.9所示。
图7.9 冒泡排序的第四次扫描
由此可知5个元素的冒泡排序法必须执行5-1次扫描，第一次扫描需比较5-1次，共比较4+3+2+1=10次
7.2.1
数列(43, 35, 12, 9, 3, 99) 用冒泡排序法（Bubble Sort）进行从小到大排序，在执行时前3次（Swap，互换）的结果各是什么？
第一次互换的结果为(35, 43, 12, 9, 3, 99)
第二次互换的结果为(35, 12, 43, 9, 3, 99)
第三次交换的结果为(35, 12, 9, 43, 3, 99)
冒泡排序法的C++算法：
for (int i=5;i>0;i--)// 扫描次数
{
for (int j=0;j<i;j++)//比较、互换次数
{
if (data[j]>data[j+1])// 比较相邻两数，如第一个数较大则互换
{
int tmp;
tmp=data[j];
data[j]=data[j+1];
data[j+1]=tmp;
}
}
cout<<"第 "<<6-i<<" 次排序后的结果是："; //把各次扫描后的结果打印出来
for (int j=0;j<6;j++)
cout<<setw(3)<<data[j];
cout<<endl;
}
从以上算法可知，n个元素的冒泡排序法必须执行n-1次扫描，最坏情况和平均情况均需比较：(n-1) + (n-2) + (n-3) +…+ 3 + 2 + 1 = 次，时间复杂度为O(n2)，最好情况只需完成一次扫描，发现没有进行互换的操作则表示已经排序完成，所以只做了n-1次比较，时间复杂度为O(n)。此排序法适用于数据量小或有部分数据已经过排序，而且过程中为相邻两者相互比较和对调，并不会更改其原本排列的顺序，所以是稳定排序法。
7.2.2
请设计一个C++程序，并使用冒泡排序法来将以下的数列排序：6、5、9、7、2、8。
请参考程序CH07_01.cpp，本范例程序的运行结果如图7.10所示。
图7.10 使用冒泡排序的范例程序的运行结果
7.2.3
从上面的程序可以看出冒泡排序法有个缺点，就是不管数据是否已排序完成都固定会执行n(n-1)/2次。请设计一个C++程序，让我们可以通过在程序中加入一个判断语句来判断何时可以提前结束程序，既可得到正确的排序结果，又提高了程序执行的效率。
请参考程序CH07_02.cpp，本范例程序的运行结果如图7.11所示。
图7.11 改进后的冒泡排序范例程序的运行结果
7.2.2 选择排序法
选择排序法（selection sort）可使用两种方式排序，一种为在所有的数据中，当从大到小排序，则将最大值放入第一个位置；若从小到大排序时，则将最大值放入最后一个位置。例如，一开始在所有的数据中挑选一个最小项放在第一个位置（假设是从小到大排序），再从第二项开始挑选一个最小项放在第2个位置，以此重复，直到完成排序为止。
下面仍然用55、23、87、62、16数列的从小到大的排序过程，来说明选择排序法的演算流程。
1. 首先找到此数列中最小值后与第一个值交换，如图7.12所示。
图7.12 选择排序的第一次扫描
2. 从第二个值开始找，找到此数列中（不包含第一个）的最小值，再和第二个值交换，如图7.13所示。
图7.13 选择排序的第二次扫描
3. 从第三个值开始找，找到此数列中（不包含第一、二个）的最小值，再和第三个值交换，如图7.14所示。
图7.14 选择排序的第三次扫描
4. 从第四个值开始找，找到此数列中（不包含第一、第二、第三个）的最小值，再和第四个值交换，则此排序完成，如图7.15所示。
图7.15 选择排序的第四次扫描，在此例中即完成了排序
选择排序法的C++算法如下所示。
void select (int data[])
{
for(int i=0;i<5;i++) //扫描5次
{
for(int j=i+1;j<6;j++) //由i+1比较起，比较5次
{
if(data[i]>data[j]) //比较第i和第j个元素
{
int tmp;
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
}
cout<<"第 "<<i+1<<" 次排序结果：";
for (int k=0;k<6;k++)
cout<<setw(3)<<data[k]; //打印排序结果
cout<<endl;
}
cout<<endl;
}
由以上算法可知，无论是最坏情况、最好情况和平均情况都需要找到最大值（或最小值），因此其比较次数为：(n-1) + (n-2) + (n-3) +…+ 3 + 2 + 1 = 次；时间复杂度为O(n2)。此外，由于选择排序是以最大或最小值直接与最前方未排序的键值交换，数据排列顺序很有可能被改变，所以它不是稳定排序，比较适用于数据量小或有部分数据已经做过排序的情况。
7.2.4
请设计一个C++程序，并使用选择排序法来将以下的数列排序：9、7、5、3、4、6。
请参考程序CH07_03.cpp，本范例程序的运行结果如图7.16所示。
图7.16 选择排序范例程序的运行结果
7.2.3 插入排序法
插入排序法（insert sort）是将数组中的元素，逐一与已排序好的数据进行比较，前两个元素先排好，再将第三个元素插入适当的位置，所以这3个元素仍然是已排序好的，接着再将第四个元素加入，重复此步骤，直到排序完成为止。可以看作是在一串有序的记录R1、R2、…、Ri，插入新的记录R，使得i+1个记录排序妥当。
下面仍然用55、23、87、62、16数列的从小到大排序过程，来说明插入排序法的演算流程。在图7.17中，在步骤二，以23为基准与其他元素比较后，放到适当位置（55的前面），步骤三则拿87与其他两个元素比较，接着62在比较完前3个数后插入87的前面，将最后一个元素比较完后即完成排序。
图7.17 插入排序的步骤
插入排序法的C++算法：
void inser(int data[])
{
int i; //i为扫描次数
int j; //以j来定位比较的元素
for (i=1;i<SIZE;i++) //扫描循环次数为SIZE-1
{
int tmp; //tmp用来暂存数据
tmp=data[i];
j=i-1;
while (j>=0 && tmp<data[j]) //如果第二元素小于第一元素
{
data[j+1]=data[j]; //就把所有元素往后推一个位置
j--;
}
data[j+1]=tmp; //最小的元素放到第一个元素
cout<<"第 "<<i<<" 次扫描：";
showdata(data);
}
}
此排序法适用于大部分数据已经过排序或已排序的数据库在新增数据后再进行排序，是一种稳定排序法。
由以上算法可知，最坏和平均情况需比较(n-1)+(n-2)+(n-3)+…+3+2+1= 次；时间复杂度为O(n2)，最好情况时间复杂度为O(n)。
7.2.5
请设计一个C++程序，并使用插入排序法来将以下的数列排序：4、6、1、8、10、32。
请参考程序CH07_04.cpp，本范例程序的运行结果如图7.18所示。
图7.18 插入排序范例程序的运行结果
7.2.4 希尔排序法
当原始记录的键值大部分已排好序的情况下，插入排序法会非常有效率，因为它不需要执行太多的数据搬移操作。“希尔排序法”是D. L. Shell 在1959年7月所发明的一种排序法，可以减少插入排序法中数据搬移的次数，以加速排序的进行。排序的原则是将数据区分成特定间隔的几个小区块，以插入排序法排完区块内的数据后再渐渐减少间隔的距离。
下面仍然用63、92、27、36、45、71、58、7数列的从小到大排序过程，来说明希尔排序法的演算流程。
首先，将所有数据分成Y：(8 div 2)，即Y=4，称为划分数。请注意！划分数不一定要是2，质数最好。但为了算法方便，所以习惯选2。因而一开始的间隔设置为 8/2，于是分成：
如此一来可得到4个区块分别是：(63，45)(92，71)(27，58)(36，7)，再分别用插入排序法排序成为：(45，63)(71，92)(27，58)(7，36)
接着再缩小间隔为 (8/2)/2，于是分成：
(45，27，63，58)(71，7，92，36)，再分别用插入排序法后得到：
最后再以 ((8/2)/2)/2的间距进行插入排序，也就是每一个元素进行排序，于是得到最后的结果。
希尔排序法的C++算法如下所示。
……
展开
