Page 134 - 高中 信息技术 选择性必修1 数据与数据结构

第五章 数据结构的应用

3．快速排序的算法实现

一趟快速排序（即将元素序列进行一次划分）的算法实现如下：
int Partition(ShangPinType r[],int i,int j)
//对顺序表r[i..j]的元素进行一趟排序，使基准元素前面元素的关键字小于基准

//元素的关键字，基准元素后面元素的关键字大于等于基准元素的关键字，并返回
//基准元素位置
{

ShangPinType t;
广东教育出版社
int pivotkey=r[i].key; //用顺序表的第一个元素作为基准元素
while(i<j)
{

while(i<j&&r[j].key>pivotkey) //从右向左扫描
--j;

t=r[i];r[i]=r[j];r[j]=t; //将比基准元素小的元素交换到左端
while(i<j&&r[i].key<=pivotkey) //从左向右扫描
++i;
t=r[i];r[i]=r[j];r[j]=t; //将比基准元素大的元素交换到右端

}
return i; //返回基准元素所在位置
}

通过多次递归调用一趟快速排序算法，就可完成整个快速排序，其算法实现如下：
void QuickSort(ShangPinType r[],int i,int j)

//对顺序表r[i..j]作快速排序
{
int pivotloc; //pivotloc是基准元素所在位置
if(i<j) //顺序表的元素个数大于1

{
pivotloc=Partition(r,i,j); //将r[i..j]一分为二
QuickSort(r,i,pivotloc-1); //对左子表递归排序

QuickSort(r,pivotloc+1,j); //对右子表递归排序
}
}

126 126

21X2204.indd 126 2019/9/26 13:53:44