希尔排序的完整算法如下： void shellsort(DataType a,int n) { for(d=n/2;d>=1;d=d/2)
{ for(i=1+d;i<=n;i++) //将a[i]插入到所属组的有序列段中 { a[0]=a[i]; j=i-d;
while(j>0&&a[0].key
a[j+d]=a[0]; } }
在希尔排序中，由于开始将n个待排序的记录分成了d组，所以每组中的记录数目将会减少。在数据量较少时，利用直接插入排序的效率较高。随着反复分组排序，d值逐渐变小，每个分组中的待排序记录数目将会增多，但此时记录的排列顺序将更接近有序，所以利用直接插入排序不会降低排序的时间效率。
希尔排序适用于待排序的记录数目较大时，在此情况下，希尔排序方法一般要比直接插入排序方法快。同直接插入排序一样，希尔排序也只需要一个记录大小的辅助空间，用于暂存当前待插入的记录。
希尔排序是一种不稳定的排序方法。
9.3 交换排序
交换排序是指在排序过程中，主要是通过待排序记录序列中元素间关键字的比较，与存储位置的交换来达到排序目的一类排序方法。 9.3.1 冒泡排序 1. 冒泡排序的基本思想
冒泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序化。其处理过程为： （1）
将整个待排序的记录序列划分成有序区和无序区，初始状态有序区
为空，无序区包括所有待排序的记录。
（2） 对无序区从前向后依次将相邻记录的关键字进行比较，若逆序将其交
换，从而使得关键字值小的记录向上\飘浮\（左移），关键字值大的记录好像石块，向下\堕落\（右移）。每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。
2. 冒泡排序算法
原始的冒泡排序算法：对由n个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以使记录序列成为有序序列，第一趟定位第n个记录，此时有序区只有一个记录；第二趟定位第n-1个记录，此时有序区有两个记录；以此类推，算法框架为：
for（i=n；i>1；i--） { 定位第i个记录； }
若定位第i个记录，需要从前向后对无序区中的相邻记录进行关键字的比较，它可以用如下所示的语句实现。
for（j=1；j< =i-1；j++） if (a[j].key>a.[j+1].key）
{ temp=a[j]；a[j]=a[j+1]；a[j+1]=temp； } 完整的冒泡排序算法：
void BubbleSort1 (DataType a,int n) { for (i=n；i>1；i--） { for (j=1;j<=i-1;j++)
if（a[j].key>a.[j+1].key）
{ temp=a[j]；a[j]=a[j+1]；a[j+1]=temp； } } }
改进的冒泡排序算法： 在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。
改进的冒泡排序算法：
void BubbleSort2 (DataType a,int n) { for (i=n;i>1;i--)
{ exchange=0；
for (j=1;j<=i-1;j++)
if (a[j].key>a.[j+1].key)
{ temp=a[j]；a[j]=a[j+1]；a[j+1]=temp；
exchange=1； }
if (exchange==0) break； } }
进一步地改进冒泡排序算法。
在原始给出的冒泡排序算法的基础上，如果我们同时记录第i趟冒泡排序中最后一次发生交换操作的位置m（m<=n-i），就会发现从此位置以后的记录均已经有序，即无序区范围缩小在a[1]~a[m]之间，所以在进行下一趟排序操作时，就不必考虑a[m+1]~a[n]范围内的记录了，而只在a[1]~a[m]范围内进行。
完整的算法：
void BubbleSort3 (DataType a,int n) { last=n-1; for (i=n;i>1;i--) { exchange=0；
m=last; //初始将最后进行记录交换的位置设置成i-1 for (j=1;j<=m;j++)
if （a[j].key>a.[j+1].key）
{ temp=a[j]；a[j]=a[j+1]；a[j+1]=temp； exchange=1；
last=j； //记录每一次发生记录交换的位置 }
if （exchange==0）break； } }
冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低；其次冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元；冒泡排序是一种稳定的排序方法。
9.3．2 快速排序 1. 快速排序的基本思想
快速排序又称为分区交换排序。其基本思想是：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（比如，第一个记录），并以该记录的关键字值为基准，从位于待排序记录序列左右两端开始，逐渐向中间靠拢，交替与基准记录的关键字进行比较、交换，每次比较，若遇左侧记录的关键字值大于基准记录的关键字，则将其与基准记录交换，使其移到基准记录的右侧，若遇右侧记录的关键字值小于基准值，则将其与基准记录交换，使其移至基准记录的左侧，最后让基准记录到达它的最终位置，此时，基准记录将待排序记录分成了左右两个区域，位于基准记录左侧的记录都小于或等于基准记录的关键字，位于基准记录右侧的所有记录的关键字都大于或等于基准记录的关键字，这就是一趟快速排序；然后分别对左右两个新的待排序区域，重复上述一趟快速排
