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

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轮：对最后两个元素进行比较，比较后发现不需要交换，则排序完成。