请阐述一下冒泡排序与选择排序的原理?

1.冒泡排序

在冒泡排序的过程中,以升序排列为例,不断地比较数组中相邻的两个元素,较小者向上浮,较大者往下沉,整个过程和水中气泡上升的原理相似。接下来分步骤讲解冒泡排序的整个过程,具体如下。

第1步:从第1个元素开始,将相邻的两个元素依次进行比较,如果前一个元素比后一个元素大,则交换它们的位置,直到最后两个元素完成比较。整个过程完成后,数组中最后一个元素自然就是最大值,这样也就完成了第1轮的比较。

第2步:除了最后一个元素,将剩余的元素继续进行两两比较,过程与第1步相似,这样就可以将数组中第2大的元素放在倒数第2个位置。

第3步:以此类推,对剩余元素重复以上步骤。

根据上述步骤,冒泡排序的流程可使用图1描述。

图1 冒泡排序流程图(以升序排列为例)

定义一个数组:int arr[5]={9,8,3,5,2},以数组arr为例,使用冒泡排序调整数组顺序的过程如图2所示。

图2 冒泡排序过程(以升序排列为例)

下面结合图6-10介绍数组arr排序过程。

第1轮比较中,第1个元素9为最大值,因此它在每次比较时都会发生位置的交换,最终被放到最后1个位置。

第2轮比较与第1轮过程相似,元素8被放到倒数第2个位置。

第3轮比较中,第1次比较没有发生位置的交换,在第2次比较时才发生位置交换,元素5被放到倒数第3个位置。

第4轮比较仅需比较最后两个值3和2,由于3比2大,3与2交换位置。

至此,数组中所有元素完成排序,获得排序结果{2,3,5,8,9}。

值得一提的是,当在程序中进行元素交换时,会通过一个中间变量temp实现元素交换,首先使用temp记录arr[j],然后将arr[j+1]赋给arr[j],最后再将temp赋给arr[j+1]。例如,交换数组元素8和3,其交换过程如图3所示。

图3 元素8与元素3交换过程

通过上面的分析可知,可以使用for循环遍历数组元素,因为每一轮数组元素都需要两两比较,所以需要嵌套for循环完成排序过程。其中,外层循环用来控制进行多少轮比较,每一轮比较都可以确定1个元素的位置;内层循环的循环变量用于控制每轮比较的次数,在每次比较时,如果前者小于后者,就交换两个元素的位置。需要注意的是,由于最后1个元素不需要进行比较,外层循环的次数为数组的长度-1。

2.选择排序

选择排序的原理与冒泡排序不同,它是指通过每一趟排序过程,从待排序记录中选择出最大(小)的元素,将其依次放在数组的最前或最后端,最终实现数组的排序。接下来,以升序排列为例分步骤讲解选择排序的整个过程,具体如下。

第1步:在数组中选择出最小的元素,将它与0索引元素交换,即放在开头第1位。

第2步:除0索引元素外,在剩下的待排序元素中选择出最小的元素,将它与1索引元素交换,即放在第2位。

第3步:以此类推,直到完成最后两个元素的排序交换,就完成了升序排列。

根据上述步骤,选择排序的流程可使用图4描述。

图4 选择排序流程图(以升序排列为例)

同样以数组{9,8,3,5,2}为例,使用选择排序调整数组顺序的过程如图5所示。

>图5 选择排序过程

在图5中,一共经历四轮循环完成数组的排序,每一轮循环的作用如下。

第1轮:循环找出最小值2,将它与第一个元素9进行交换。

第2轮:循环找出剩下的4个元素中的最小值3,将它与第二个元素8交换。

第3轮:循环找出剩下的3个元素中的最小值5,将它与第三个元素8交换。

第4轮:对最后两个元素进行比较,比较后发现不需要交换,则排序完成。

点击此处
隐藏目录