8.1 互换类排序
排序就是把一组无序的记录按其关键字的某种次序排列起来，使其具有一定的顺序，便于进行数据查找。排序是数据处理中经常使用的一种重要操作，其方法很多，应用也很广泛。排序的方式可以分成两种：（1）如果记录是在主存储器（Main Memory）中进行分类，则称为内部排序（Internal Sort）；（2）假如记录太多，以致无法全部存于主存储器中，需借助辅助内存（如磁盘或磁带）来进行分类，此种称为外部排序（External Sort）。
除了上述内部排序和外部排序的区别外，也可以分成下列两类：（1）如果排序方式是比较整个键值（Key Value）则称为比较排序（Comparative Sort）；（2）假如是一次只比较键值的某一位数，则称为分配排序（Distributive Sort）。
存于文件（File）中的记录（Record）可能含有相同的键值。对于两个键值相等的记录r(i)和r(j)，如果在源文件中r(i)排在r(j)之前，而在排序后文件中的r(i)仍在r(j)之前，则称此排序具有稳定性（Stable）；反之，如果r(j)在r(i)之前则称此排序为不稳定（Unstable）。即当两个键值一样时不需要互换，称为稳定排序；反之，即使键值相同仍需互换者则称为不稳定排序。
排序可能在记录本身或在一个辅助的指针中进行。排序是对记录本身进行的，这种方式是真正对记录本身做排序。如果文件中的每一条记录含有大量数据，则移动这些数据就会耗费相当多的时间。在这种情况下，最好能使用辅助的指针，利用指针的改变取代原来数据的移动。
本章主要内容
& 各种排序的基本思路及其特点
& 各种排序方法的排序过程
& 各种排序方法的比较和选择
8.1 互换类排序
互换类排序的基本方法是：两两比较待排序记录的关键字，并交换不满足次序要求的那些偶对，直到全部满足为止。本节介绍冒泡排序和快速排序两种交换排序方法。
8.1.1 冒泡排序
冒泡排序的算法思路是：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的记录开始，对每两个相邻记录的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依此类推，一直到所有记录都有序为止。
通常有n个数据时需要做n-1次扫描，一次扫描完后，数据量减少1，当没有对调时，就表示已排好序了。
【例8-1】 已知有10个待排序的记录，它们的关键字序列为{75,87,68,92,88,61,77,96,80,
72}，给出用冒泡排序法进行排序的过程。
解：冒泡排序过程如图8-1所示，方括号[ ]中的元素为本次冒出的元素。
图8-1 冒泡排序过程
冒泡排序的一个完整程序如下：
/*冒泡排序*/
#include <stdio.h>
void bubble_sort(int[ ],int);
void main(void)
{
int data[20];
int size=0,i;
printf("\nPlease enter number to sort(enter 0 when end):\n");
printf("Number : ");
do /*要求输入数字直到输入数字为0*/
{
scanf("%d",&data[size]);
} while(data[size++] !=0);
for(i=0;i<60;i++) printf("-");
printf("\n");
bubble_sort(data,--size); /*--size用于将数据为0者排除*/
for(i=0;i<60;i++) printf("-");
printf("\nSorting: ");
for(i=0;i<size; i++)
printf("%d ",data[i]);
}
void bubble_sort(int data[ ],int size)
{
int i,j,k,temp,flag;
for(i=0;i<size-1;i++) /*让数据两两比较，将小的置于前*/
{
flag=0;
for(j=0;j<size-1;j++)
if(data[j]>data[j+1])
{
flag=1;
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
printf("Access : ");
for(k=0;k<size;k++)
printf("%d ",data[k]);
printf("\n");
if(flag !=1)
break;
}
}
上述程序的输出结果为：
Please enter number to sort(enter 0 when end):
Number : 18 2 20 34 12 0
------------------------------------------------------------
Access : 2 18 20 12 34
Access : 2 18 12 20 34
Access : 2 12 18 20 34
Access : 2 12 18 20 34
------------------------------------------------------------
Sorting: 2 12 18 20 34
冒泡排序的执行时间与n个元素原来的排列顺序有关。排序前，如果n个元素已经从小到大排好，则只要进行一趟起泡，关键字的比较次数最少（n-1次），而且不需要移动元素；如果n个元素是从大到小排列的，则需要进行n-1趟起泡，关键字的比较次数和元素的移动次数都达到最大值，分别为
和3
。因此，冒泡排序的执行时间在最坏情况下是O(n2)。
因为只有在R[j].key<R[j-1].key的情况下，才交换R[j]和R[j-1]，所以，冒泡排序是稳定的。
8.1.2 快速排序
快速排序是由冒泡排序改进而得的，它的基本思路是：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，整个数据区间被此记录分割成两个子区间。所有关键字比该记录关键字小的放置在前子区间中，所有比它大的放置在后子区间中，并把该记录排在这两个子区间的中间，这个过程称做一趟快速排序。之后对所有的两个子区间分别重复上述过程，直至每个子区间内只有一个记录为止。简而言之，每趟排序使表的第一个元素入终位，将数据区间一分为二，对于子区间按递归方式继续这种划分，直至划分的子区间长为1。
一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。具体做法是：设两个指示器i和j，它们的初值分别为指向无序区中第一个和最后一个记录。假设无序区中记录为R[s..t]，则i的初值为s，j的初值为t，首先将R[s]移至临时变量tmp中作为基准，令j自t起向左扫描直至R[j].key<tmp.key时，将R[j]移至i所指的位置上，然后令i自i+1起向右扫描直至R[i].key>tmp.key时，将R[i]移至j所指的位置上，依次重复直至i=j，此时所有R[k]（k=s，s+1，…，j-1）的关键字都小于tmp.key，而所有R[k]（k=j+1，j+2，…，t）的关键字必大于tmp.key，则可将tmp中的记录移至i所指位置R[i]，它将无序中记录分割成R[s..j-1]和R[j+1..t]，以便分别进行排序。
快速排序算法如下：
void QuickSort(LineList R[],int s,int t) /*对R[s]至R[t]的元素进行快速排序*/
{
int i=s,j=t;
LineList tmp;
if(s<t) /*区间内至少存在一个元素的情况*/
{
tmp=R[s]; /*用区间的第1个记录作为基准*/
while(i!=j) /*从区间两端交替向中间扫描，直至i=j为止*/
{
while(j>i && R[j].key>tmp.key)
j--; /*从右向左扫描，找第1个关键字小于tmp.key的R[j]*/
R[i]=R[j]; /*找到这样的R[j]，则R[i]和R[j]交换*/
while(i<j && R[i].key<tmp.key)
i++; /*从左向右扫描，找第1个关键字大于tmp.key的R[i]*/
R[j]=R[i]; /*找到这样的R[i]，则R[i]和R[j]交换*/
}
R[i]=tmp;
QuickSort(R,s,i-1); /*对左区间递归排序*/
QuickSort(R,i+1,t); /*对右区间递归排序*/
}
}
例如，给定待排序记录序列的关键字分别为46，55，13，42，94，05，17，70，第一次划分如图8-2所示。
图8-2 快速排序的划分
从图8-2可以看出，通过一次划分，将一个待排序的记录序列以基准记录的关键字分成左右两个子序列，左子序列记录的关键字小于或等于基准记录的关键字，右子序列记录的关键字大于基准记录的关键字。对剩下的左右子序列重复此划分步骤，则可以得到快速排序的结果。
快速排序算法的时间复杂度是O(nlog2n)，而且快速排序是不稳定的。