|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，使得整个序列有序。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
快速排序（Quick Sort）的主要思路为：通过对线性表序列的一趟扫描使某个结点移到中间的某个位置，且使其左边序列各结点的关键字都比该结点的关键字小，而其右边序列各结点的关键字都不比该结点的关键字小，常称这样的一次扫描为"划分"。然后，对左、右序列进行同样的处理，直到所有序列均只包含一个结点为止，这样便可将原线性表排好序。
|
|
|
|
快速排序可以看作是冒泡排序的改进，冒泡排序可以看作是快速排序的退化，即每趟划分总是在同一端进行。
|
|
|
|
若设待排序的记录序列{R1，R2，…，Rn}为R[1…n]，则对其按关键值的非递减序列进行快速排序的算法如下：
|
|
|
|
|
|
可见，快速排序可能会破坏两个相等记录的原来次序，因而快速排序算法是不稳定的。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
|
|
|
|
|
|
|
|
|
|
|
|
|
