【排序算法】冒泡排序、选择排序、插入排序

依次比较相邻的两个元素，将比较小的数放在前面，比较大的数放在后面，直到所有元素排列完。

对一个数组的个整型数据进行趟排序，每趟排序都尝试将较大值放到数组右侧。
每趟排序比较两个相邻的数据，由于个数据有个间隔，所以每趟需要比较次。
代码如下：

Java

C/C++

上述代码存在优化空间：
在第一趟排序结束后，数组最右端已是当前的最大值。剩余元素均小于，后续排序无需再与进行比较。
在第二趟排序结束后，数组最右侧是，剩余元素均小于，后续排序无需再对进行比较。
即对于内层循环：

• 在第趟排序中，只需要比较次（从开始）。
• 如果外层循环是从开始计数的，那么需要每轮需要比较次。

---

对于外层循环，在执行第趟排序时，内层循环只比较了第个元素和第个元素。
此时已经排列完成，不需要再执行下一趟排序。
即对于外层循环：

• 只需要排序趟。
• 对于给定的数组，的结果也是确定的。因此无论外层循环的计数器从几开始，需要比较的次数都是。

1. 定义一个标记并初始化为。
2. 在每趟比较开始前，通过检查是否发生元素交换。
3. 在每趟比较开始时，将置为。
4. 当发生元素交换时，将置为。

在第2步中，如果值为，则表明发生交换，继续下一步。
如果值为，则表明没有发生交换，即已经排序完成，结束即可。

• 初始值为，可以正常进入第一趟排序。
• 中类型不能赋值为或，将对应的和改为和即可。

• 外层循环控制轮数，总共执行轮。
• 内层循环控制每轮的比较次数，第轮比较次（从开始）。
• 通过标记判断是否已经排序完成。

C/C++

Java

需要注意的是，内层循环的结束条件与无关。

分别从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序算法，即对于值相同的数据元素，彼此的前后顺序可能会发生改变。

与冒泡排序不同：

• 冒泡排序是逐趟选出未排序序列中的最大值，置于右侧。
• 选择排序是逐趟选出未排序序列中的最小值，置于左侧。
• 冒泡排序会两两比较相邻元素，将较大值通过多次交换移动到数列右侧，第趟最多交换次。
• 选择排序会通过多次比较记录最小元素的下标，在这一趟结束时才发生交换，每趟最多交换次。

---

即重复这两个步骤：

1. 遍历无序序列，记录无序数列的最小值的下标。
2. 将下标对应的元素与无序数列的最左端元素交换位置。

Java

C/C++

需要注意：

• 对于个元素，需要排序的趟数仍然是。
• 不同于冒泡排序，选择排序每趟排序最多只会改变两个元素的位置。不能设置检查是否排序完成，也无法通过检查。
• 选择排序需要遍历剩余所有元素，内层循环不能同冒泡循环一样修改右边界。并且要保证能访问到数列的最后一个元素。

C/C++

Java

要点如下：

• 如果数据结构是数组，那么每次插入都需要将插入位置以后的元素向后移动，移动元素会覆盖该元素的下一个元素。会导致被覆盖，因此必须要使用临时变量存储每趟排序中的的值。
• 我们需要对数组的每个元素都进行遍历，以保证每个元素都被取出并插入到合适位置。因此外重循环的结束条件为元素个数而不是。
• 在第一趟插入中，我们将原数列的第个元素取出作为有序数列，将第个元素取出作为新元素插入，对应的下标从1开始。虽然结束条件是，外重循环的次数仍然是。
• 在插入元素时，已经内层循环的结束条件，此时小于零，或者已经指向合适位置的前一个位置。因此需要对进行赋值，而非。

交换两个变量的值，除了可以使用第三个变量tmp，也可以使用加减法的方式处理，仅适用于数字类型。

三种排序方法每趟都只能确保一个数据加入有序数列后仍有序，外层循环执行的趟数都为，即元素个数。但由于计数器开始位置不同，可能为，也可能为，或者其它计数方式，不需要死记硬背，只需要保证能执行趟即可。
对于内层循环，还是由于三种排序方法每趟都只能确保一个数据加入有序数列后仍有序。有序序列每趟排序后长度都在增加，我们不需要对有序序列的元素再取出排序。我们只需要保证能遍历到无序序列中的每一个元素即可。

• 对于冒泡排序，有序序列默认在右端，左侧为无序序列，我们采取的方式是调整右边界。而内层循环每次从0开始，是为了能够遍历到左侧的无序序列的每一个元素。
• 对于选择排序，有序序列默认在左端，右侧为无序序列，我们采取的方式是调整左边界。内层循环的计数器初始值随趟数改变而改变，是为了保证每趟都指向无序序列的第一个元素，并能够遍历无序序列的每一个元素。
• 对于插入排序，有序序列默认在左端，我们需要取出无序序列中的元素之后遍历有序序列，寻找合适位置。由于有序序列是有序的，我们可以选择一个方向，寻找介于两个元素之间的位置插入。在有序序列寻找合适位置时需要考虑数组边界。