9.3 交换排序

南山隐士 2022年07月31日 40 0

要求掌握冒泡排序、快速排序的基本思想和算法实现,针对给定的输入实例,写出冒泡排序、快速排序的排序过程。

交换排序是一类在排序过程中按照某种规则,逐次找到不满足排序要求的两个记录,通过不断交换记录之间的位置,使序列逐步有序或部分符合有序的相关条件而最终完成排序的方法。

1.冒泡排序

(1)冒泡排序的基本思想

直接插入排序(Straight Insertion Sort)算法是一种常用且简单直观的方法。它的基本思想是:设有n个数据的待排序序列,假设前面1到i-1个数据已经有序,是长度为i-1的有序序列,将第i个数据逐次与第i-1个数据、第i-2个数据……进行比较,直到找到第i个数据的插入位置,并插入得到一个新的长度为i的有序数列。这一过程称为一趟插入,对第i个元素的插入称为第i趟插入。

(2)冒泡排序的步骤

逐次进行相邻记录关键字的比较和必要的换位。首先比较第一个和第二个记录的关键字,将较小的一个放在前面,即第一个位置,较大的放在后面,即第二个位置。然后以同样的方式比较第二个和第三个……,直至完成第n-1个和第n个记录的关键字比较。共进行了n-1次比较,其结果是最大关键字的记录排序到位,并占据了第n个位置,称上述过程为第一趟冒泡。第二趟冒泡对第一个记录到第n-1个记录实施与第一趟冒泡相同的处理。共进行n-2次比较,使次大的关键字记录占据了第n-1个位置。一般的第i趟冒泡从第一个记录到第n-i+1个记录进行两两比较,共进行n-i次比较,直到第n-1趟冒泡,进行第一个记录与第二个记录的一次比较,完成排序。

例如,一组记录的关键字序列为{ 81, 63,45,72 },冒泡过程如下:

初始状态 81 63 45 72

第一趟冒泡后 63 45 72 [81] 比较了3次

第二趟冒泡后 45 63 [72] [81] 比较了2次

第三趟冒泡后 [45] [63] [72] [81] 比较了1次

一般规则

n个元素,要进行n-1趟冒泡

第j趟冒泡要进行 n-j 次元素间的比较

(3)冒泡排序的算法实现

【算法9-3】冒泡排序算法

void bsort(NODE a[],int n)

/* 对存放在a[1],a[2],…,a[n]中的序列进行冒泡排序 */

{

NODE temp;

int i,j,flag;

for(j=1;j<=n-1;j++) /共进行n-1趟冒泡/

{

flag=0;

for(i=1;i<=n-j;i++)              /*第j趟共进行n-j次比较*/

  if(a[i].key>a[i+1].key)

  {

    flag=1;                  /*说明本趟有元素交换*/

    temp=a[i];

    a[i]=a[i+1];

    a[i+1]=temp;

}

if(flag==0)break;               /*没有元素交换,说明已排好序*/

}

}

上述算法中外层循环控制冒泡趟数,内层循环控制每趟冒泡时记录关键字的比较次数。在每趟冒泡中,用flag标志量记录是否出现过记录的交换,如果没有出现过交换,说明记录序列已经有序,结束冒泡,这样可避免不必要的计算过程。例如在最好情况下,待排序的记录序列已经有序,程序只需要一趟冒泡,进行n-1次元素的比较。最坏情况下,待排的记录序列为逆序,则程序要完成双重循环的全过程。显然冒泡排序的时间复杂度为O(n2), 并且是稳定的。

想一想:如何理解冒泡排序?

解题分析:

冒泡排序是待排序序列中的元素相邻的两个数据进行比较,满足条件时进行交换,每一趟完成,序列中最大(最小)的数据被调整到最上面的位置,类似水中的冒泡,因此称作冒泡排序。

2.快速排序

(1)快速排序的基本思想

冒泡排序算法经一趟冒泡只能使一个记录排序到位,快速排序(Quick Sort)是对冒泡法的改进,算法中经一趟操作后,不仅使某个记录排序到位,同时以该记录的关键字为划分标准(称它为划分记录),把记录序列划分为两个子序列。所有关键字比划分记录小的排放到它的前面,大的排放到它的后面。在原序列中除去划分记录后的两个子序列可以分别进行相同的操作,把每个序列再分成两个更小的子序列,直到序列的长度为1,完成排序。整个排序过程可以通过递归来实现。

(2)冒泡排序的步骤

设待排序的记录序列存放在a数组中,一趟快速排序的步骤如下:

1.选取划分记录,通常设定序列中第一个为划分记录,用变量mid暂存划分记录。另外设置序列的起、止下标,不妨设为start和end。

2.设置两个指示记录下标的变量i、j,初值分别指向序列的起、止位置。

3.j从当前位置开始,从后向前扫描,直到a[j].key

4.i 从当前位置开始从前向后扫描,直到a[i].key>=mid.key , 然后使a[i]置于a[j]的位置,使j减1,前移一个位置。

5.重复步骤3、4,直到i和j 相等,然后把划分记录置于a[i]中,这样划分记录排序到位,且把原序列划分为要求的两个子序列。称上述过程为一次划分。

例如,一组记录的关键字序列为{ 40,35,60,38,30,90 },一趟划分的过程如图9‑1所示,其中划分关键字mid=40。


图9‑­­­1 一趟划分的过程

图中方框内表示其中数据已移走,可以被其他数据覆盖。

(3)快速排序的算法实现

【算法9-4】 快速排序算法

void quicksort(NODE a[],int start,int end)

/对a[start]到a[end]的记录按关键字进行快速排序/

{

int i,j;

NODE mid;

if(start>=end)

return;

i=start;

j=end;

mid=a[i];

while(i

{

while(imid.key)

  j--;

if(i

{

  a[i]=a[j];              /*把a[j]置于a[i]的位置*/

  i++;                  /*后移一个位置*/

}

while(i

  i++;                  /*从前向后扫描,等于划分关键字的记录也跳过*/

if(i

{

  a[j]=a[i];              /*把a[i]置于a[j]的位置*/

  j--;                  /*前移一个位置*/

}

}

a[i]=mid; /划分记录到位,一次划分结束/

quicksort(a,start,i-1); /递归调用对前一子序列划分/

quicksort(a,i+1,end); /递归调用对后一子序列划分/

}

快速排序的时间复杂度取决于所选划分记录,最坏情况是每次划分记录的关键字正好是记录序列中的最大值或最小值,此时它类似于冒泡法,时间复杂度为O(n2),在平均情况下快速排序时间复杂度为O(nlog2n),是目前认为较好的一种内部排序方法。快速排序是不稳定的排序。

Last Updated: 2022/07/31 23:26:23
9.4 选择排序 9.2 插入排序