{
a[j]=a[i]; /*把a[i]置于a[j]的位置*/
j--; /*前移一个位置*/
}
}
a[i]=mid; /*划分记录到位,一次划分结束*/
quicksort(a,start,i-1); /*递归调用对前一子序列划分*/
quicksort(a,i+1,end); /*递归调用对后一子序列划分*/
{
flag=0;
for(i=1;i<=n-j;i++) /*第j趟共进行n-j次比较*/
if(a[i].key>a[i+1].key)
{
flag=1; /*说明本趟有元素交换*/
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
if(flag==0)break; /*没有元素交换，说明已排好序*/
}
}
快速排序算法
void quicksort(NODE a[],int start,int end)
/*对a[start]到a[end]的记录按关键字进行快速排序*/
{
int i,j;
NODE mid;
if(start>=end)
return;
i=start;
j=end;
mid=a[i];
while(i<j) /*一次划分直到i等于j*/
图中方框内表示其中数据已移走，可以被其他数据覆盖。
实验过程（实验中涉及的记录、数据、分析）：
冒泡排序算法
void bsort(NODE a[],int n)
/* 对存放在a[1],a[2],…,a[n]中的序列进行冒泡排序 */
{
NODE temp;
int i,j,flag;
for(j=1;j<=n-1;j++) /*共进行n-1趟冒泡*/
}
实验结果：
冒泡算法中外层循环控制冒泡趟数，内层循环控制每趟冒泡时记录关键字的比较次数。在每趟冒泡中，用flag标志量记录是否出现过记录的交换，如果没有出现过交换，说明记录序列已经有序，结束冒泡，这样可避免不必要的计算过程。例如在最好情况下，待排序的记录序列已经有序，程序只需要一趟冒泡，进行n-1次元素的比较。最坏情况下，待排的记录序列为逆序，则程序要完成双重循环的全过程。显然冒泡排序的时间复杂度为O(n2), 并且是稳定的。
例如，一组记录的关键字序列为{ 81，63，45，72 }，冒泡过程如下：
初始状态81 63 45 72
第一趟冒泡后63 45 72 [81]比较了3次
第二趟冒泡后45 63 [72] [81]比较了2次
第三趟冒泡后[45] [63] [72] [81]比较了1次
快速排序的步骤
设待排序的记录序列存放在a数组中，一趟快速排序的步骤如下：
数据结构课程实验报告
学生姓名
学 号
班 级
指导老师
实验名称
交换排序
实验成绩
实验报告
实
验
概
述
实验目的：
掌握冒泡排序和快速排序的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。
实验要求：
实现冒泡排序和快速排序，比较两种算法的优缺点以及实际应用
实验基本原理：
快速排序的时间复杂度取决于所选划分记录，最坏情况是每次划分记录的关键字正好是记录序列中的最大值或最小值，此时它类似于冒泡法,时间复杂度为O(n2)，在平均情况下快速排序时间复杂度为O(nlog2n)，是目前认为较好的一种内部排序方法。快速排序是不稳定的排序。
实
验
小
结
实
验
内
容
实验设计思路、步骤和方法等：
冒泡排序的步骤
逐次进行相邻记录关键字的比较和必要的换位。首先比较第一个和第二个记录的关键字，将较小的一个放在前面，即第一个位置，较大的放在后面，即第二个位置。然后以同样的方式比较第二个和第三个……，直至完成第n-1个和第n个记录的关键字比较。共进行了n-1次比较，其结果是最大关键字的记录排序到位，并占据了第n个位置，称上述过程为第一趟冒泡。第二趟冒泡对第一个记录到第n-1个记录实施与第一趟冒泡相同的处理。共进行n-2次比较，使次大的关键字记录占据了第n-1个位置。一般的第i趟冒泡从第一个记录到第n-i+1个记录进行两两比较，共进行n-i次比较，直到第n-1趟冒泡，进行第一个记录与第二个记录的一次比较，完成排序。
4.i从当前位置开始从前向后扫描，直到a[i].key>=mid.key ,然后使a[i]置于a[j]直到i和j相等，然后把划分记录置于a[i]中，这样划分记录排序到位，且把原序列划分为要求的两个子序列。称上述过程为一次划分。
例如，一组记录的关键字序列为{ 40，35，60，38，30，90 }，一趟划分的过程如图91所示，其中划分关键字mid=40。
1.选取划分记录，通常设定序列中第一个为划分记录，用变量mid暂存划分记录。另外设置序列的起、止下标，不妨设为start和end。
2.设置两个指示记录下标的变量i、j，初值分别指向序列的起、止位置。
3.j从当前位置开始，从后向前扫描，直到a[j].key<mid.key,然后使a[j]置于a[i]的位置，使i增1，后移一个位置。
冒泡排序是设有n个数据的待排序序列，假设前面1到i-1个数据已经有序，是长度为i-1的有序序列，将第i个数据逐次与第i-1个数据、第i-2个数据……进行比较，直到找到第i个数据的插入位置，并插入得到一个新的长度为i的有序数列。这一过程称为一趟插入，对第i个元素的插入称为第i趟插入
快速排序（Quick Sort）是对冒泡法的改进，算法中经一趟操作后，不仅使某个记录排序到位，同时以该记录的关键字为划分标准（称它为划分记录），把记录序列划分为两个子序列。所有关键字比划分记录小的排放到它的前面，大的排放到它的后面。在原序列中除去划分记录后的两个子序列可以分别进行相同的操作，把每个序列再分成两个更小的子序列，直到序列的长度为1，完成排序。整个排序过程可以通过递归来实现
{
while(i<j &&a[j].key>mid.key)
j--;
if(i<j)
{
a[i]=a[j]; /*把a[j]置于a[i]的位置*/
i++; /*后移一个位置*/
}
while(i<j&&a[i].key<=mid.key)
i++; /*从前向后扫描，等于划分关键字的记录也跳过*/
if(i<j)