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

第五章 数据结构的应用

for(int i=0;i<n;i++) //需要进行n-1趟排序
{
for(int j=0;j<n-i;j++) //每一趟排序需要比较n-i次

if(r[j].key>r[j+1].key)
{
t=r[j];r[j]=r[j+1];r[j+1]=t; //交换r[j]和r[j+1]
}

}
}

广东教育出版社
5.3.3 快速排序

快速排序是平均排序次数最少的排序算法之一，也是目前平均速度最快的排序，故称

快速排序（Quick Sort），特别适合于数据量较多的排序。
1．快速排序的基本思想

快速排序采用分治法的策略：将原问题划分成规模更小但与原问题相似的小问题，然
后用递归法解决这些小问题，最后将它们组合形成原问题的解。

快速排序的基本思想是：从待排序元素序列中选取一个元素（通常是第一个元素）作

为基准元素，其关键字设为key，然后将其余关键字小于key的元素移至key前面，而将关键
字大于key的元素移至key后面，实现将待排序元素序列分为两个子表，最后将关键字key
的元素插入其分界线的位置上，这个过程称为一趟快速排序；通过这一趟划分后，以关键

字key的元素为界，待排序列被分为两个子表，且前面子表中所有元素的关键字均不大于

key，而后面子表中所有元素的关键字均大于key。继续对分割后的子表按上述原则进行划
分，直到所有子表的表长不超过1为止，此时的元素序列就成了一个有序序列。
2．快速排序算法的步骤

以关键字升序排列为例，设待排序列存放在数组a[1..n]中，n为元素个数， i、j分别是

待排序列首尾关键字的下标，初值分别为1和n，令a[1]作为基准元素赋给pivotkey：
（1）j从右往左扫描，若i<j且a[j].key >= pivotkey，j=j-1，否则将a[j]与a[i]交换。
（2）i从左往右扫描，若i<j且a[i].key < pivotkey，i=i+1，否则将a[i] 与a[j] 交换。

（3）重复执行（1）和（2），直到出现i≥j，则将基准元素pivotkey移动到a[i]中。此

时整个元素序列在位置i被划分成两个部分，前一部分的元素关键字都小于或等于a[i].key，
后一部分元素的关键字都等于或大于a[i].key，即完成了一趟快速排序。
（4）继续对分割后的子表进行上述划分，直至所有子表的表长不超过1为止，此时的

元素序列就成了一个有序序列。

124 124

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