山东公务员考试网计算机常识-交换类排队序法

所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。

1、冒泡排序法

基本过程如下：

首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。放最大值

然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素大于前面的元素，则将它们互换，这样就又消去了一个逆序。放最小值。

重复上述过程，直到剩下的线性有变空为止，此时的线性表已经变为有序。

假设线性表的长为n，则在最坏情况下，冒泡排序需要经过n/2遍的葱馨往后的扫描和n/2遍的从后往前的扫描，需要的比较的次数为n(n-1)/2。

2、 快速排序法

快速排序法也是种互换类的排序法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。

基本思想如下：

从线性表中选取一个元素，设T，将线性表后面小于T的元素移到前，而前大于T的元素移支后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。

如此反复，则此时的线性表就变成了有序表。

步骤：首先，在表的第一个，中间一个与最后一个元素中选取中项，设为P（K），并将P（K）赋给T，再将表中的第一个元素移到P（K）的位置上。

然后设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步：

（4） 将j逐渐减小，并逐次比较P（j）与T，直到发现一个P(j)<T为止，将P(j)移到P(i)位置上。

（5） 将i逐渐减小，并逐次比较P（i）与T，直到发现一个P(i)>T为止，将P(i)移到P(j)位置上。

上述两个操作交替进行，直到指针i与j 指向同一个位置（即i=j）为止，此时将P(i)的位置上。

分割需要记忆，用栈来实现。

更多精彩资讯请关注查字典资讯网，我们将持续为您更新最新资讯!