软考之排序算法（三）——交换排序_软考 排序算法

前两篇文章中介绍了选择排序和插入排序，今天我们继续往下来介绍其他的排序算法，介绍交换排序中的冒泡排序和快速排序。
1、交换排序：冒泡排序

定义：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推直至第n-1个记录和第n个记录的关键字比较过为止。

做法：上述过程称为第一趟冒泡排序。其结果是关键字最大的记录被交换到第n个记录的位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个记录的位置上。最多进行n-1趟这样的排序，若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。

举例：下面我们来举个例子说明，假设待排序列为8,2,6,7,3,9,4 按照从大到小的顺序排序。

上述操作是第一趟冒泡排序，然后按照上述方法进行第二次冒泡排序，然后进行第三次、第四次.....直至若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，则可结束排序过程。好了，下面说快速排序。

2、交换排序：快速排序

定义：快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排的记录划分为独立的两个部分，其中一部分记录的关键字均不大于另一部分记录的关键字，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序。

做法：附设两个指针i和j，它们的初值分别指向第一个记录和最后一个记录，设枢轴记录（通常是第一个记录）的关键字为pivotkey，则首先从j所指位置起向前搜索，找到第一个关键字小于pivotkey的记录与枢轴记录相互交换，然后从i所指位置向后搜索，找到第一个关键字大于pivotkey的记录与枢轴记录相互交换。重复这两步直至i等于j时为止。

举例：按照我们定义中的这种说法，我们假设待排数列,5,1,6,3,7,9 要设定两个指针i和j，让i和j分别指向这组数据中的第一个记录和第二个记录，设枢轴记录key（设第一个记录为key的值）的值为5，为了直观的显示我们画图来表示，如下：

已经找出i、j和key的对应值之后，然后开始进行排序。首先从j开始向前搜索，找到第一个比key值小的数，在我们这个序列中是下标为3的数值3，所以将key值也就是第一个值5与数值3交换位置，此时j的值由原来的下标5变为下标3。

所以此时序列变为

然后从i开始向后搜索，招待第一个比key值大的数，找到下标为2的数值6，此时将数值6与key值交换位置，此时i的位置由原来的下标0变为现在的下标2.

此时序列变为：

重复上面的步骤，使得j=j-1我们发现i和j数值相同了，它们都指向了下标2，于是结束循环得到结果。值得注意的是快速排序并不能直接得到最终结果，它只是让比key值小和比key值大的数分到key的两边，为了得到最终结果还需要将分到两边比key值大和比key值小的的数再分别重复执行上述的快速排序操作，得到最终结果。

******************************************************************************************************

    下一篇文章我们将介绍归并排序和基数排序，敬请期待！
 

 

 

原文地址：https://blog.csdn.net/gaoying_blogs/article/details/24961445

参考文章：https://zhidao.baidu.com/question/48068982.html