扫码获取更多资源

●快速排序

快速排序(Quick Sort)又称划分交换排序，是对冒泡排序的改进。在冒泡排序中，记录 的比较和移动是在相邻位置进行的，记录每次交换只能前移或后移一个位置，因而总的比较 次数和移动次数较多。在快速排序中，记录的比较和移动是从两端向中间进行的，关键字较 大的记录一次就能从前面移动到后面，关键字较小的记录一次就能从后面移动到前面，记录 移动的距离较远，从而减少了总的比较次数和移动次数。其基本思想是：首先选一个轴值 （即比较基准），将待排序记录分割成独立的两部分，左侧记录关键字均小于或等于轴值，右 侧记录关键字均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

将n个待排序记录序列站，『 …，琮｝划分成有序区和无序区，初始时有序区为空，无 序区包括所有待排序的记录。设有序区右边界为bound,存储有序区最后一个记录的位置， 即有序区记录为. rbound ；无序区中每趟待排序记录为rbound+1.. rno

快速排序需要解决三个关键问题：一是如何选择轴值；二是在待排序记录序列中如何 进行分区（通常叫作一次划分）；三是如何处理分区得到的两个待排序记录子序列以及如何 判别快速排序的结束。

在待排序记录序列中进行分区。

初始化：设置两个参数low和high,分别用来指示将要与轴记录关键字进行比较的

左侧记录位置和右侧记录位置，也就是本次划分的区间。

•右扫描：将轴记录关键字与high指向记录关键字进行比较，如果high指向记录的 关键字大，则high前移一个记录位置；重复右侧扫描过程，直到右侧的记录关键字 小（即反序），如果lowVhigh,则将轴记录与high指向的记录进行交换。

•左扫描：将轴记录关键字与low指向记录关键字进行比较，如果low指向记录的关 键字小，则low后移一个记录位置；重复左侧扫描过程，直到左侧的记录关键字大 （即反序），如果lowVhigh,则将轴记录与low指向的记录交换。

重复右扫描和左扫描，直到low与high指向同一个位置，即轴记录最终的位置，此时将 待排序记录序列以轴记录为基准分成左侧和右侧两个子区间。

快速排序的时间主要耗费在划分操作上。从上述快速排序的执行过程可以看岀，快速 排序的趟数取决于递归的深度。 在最好的情况下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长 度相同。在具有n个记录的序列中，对一个记录定位要对整个待划分序列扫描一遍，则所需 时间为O(n)。设T(n)是对n个待排序记录序列进行排序的时间，每次划分后，正好把待划 分区间划分为长度相等的两个子序列，则有

通常，快速排序认为是在所有同数量级(O(nlog2n))的排序方法中，其平均性能最好。 但如果待排序记录序列按关键字有序或基本有序时，快速排序就将蜕化为冒泡排序，其时间 复杂度为。

由于快速排序是递归的，因此需要一个栈来存放每一层递归调用的必要信息，其最大容 量应与递归调用的深度一致。最好情况下栈的深度为O(lo&n);最坏情况下，要进行n—1 次递归调用，栈的深度为O(n)；平均情况下栈的深度为O(log2n)。

联系我们：