交换排序——选择排序和冒泡排序的区别是什么？

今天重温一下算法，其实刚开始我觉得冒泡排序和选择排序是一样的，因为他们排序过程中都是通过相邻的数据比较找到最小/最大的数据，通过不断思考和学习才明白，两者还是有区别的。

冒泡排序

概念

冒泡排序(Bubble Sort)，可以说是知名度最高也是特别特别重要的经典排序算法。

冒泡排序和选择排序都属于交换排序算法的一种。所谓交换排序算法，是指在排序过程中，要发生数组元素的交换。

之所以要把该算法称为“冒泡算法”，这是因为每个大的元素，每次经过交换都会慢慢“浮”到数组的顶端，故名“冒泡排序”。

冒泡排序的核心思想，是把相邻的元素进行两两比较，当一个元素大于右侧相邻的元素时，就交换它们的位置；当一个元素小于或等于右侧相邻的元素时，则保持位置不变。

注意：冒泡排序只会操作相邻的两个数据。每次冒泡操作都是对相邻的两个元素进行比较，看是否满足大小关系。

实现步骤

接下来我们就以一个数值型的数组为例，向大家介绍冒泡排序的整个排序过程。

我们现在定义一个数组，其数组元素值依次为[5，8，6，3，9，2，1，7]。

如果我们采用冒泡排序算法，按从小到大的规则对其排序，其详细过程会如下所示：

1. 将5和8进行比较，因为满足左小右大的规则，不需要交换，保持元素位次不变；
2. 将8和6进行比较，因不满足左小右大的规则，则需要交换。将8和6位置互换，互换位置后，元素6在下标1这个位置上，元素8在下标2这个位置上；
3. 接着将8和3进行比较，不满足左小右大规则，需要交换。将8和3位置互换，互换位置后，元素3在下标2的位置上，元素8在下标3的位置上；
4. 继续将8和9进行比较，满足左小右大规则，不需要交换，保持元素位次不变；
5. 将9和2进行比较，不满足左小右大的规则，需要交换。将9和2位置互换，互换位置后，元素2在下标4的位置上，元素9在下标5的位置上；
6. 将9和1进行比较，不满足左小右大的规则，需要交换。将9和1位置互换，互换位置后，元素1在下标5的位置上，元素9在下标6的位置上。
7. 继续将9和7进行比较，不满足左小右大的规则，需要交换。互换位置后，元素7在下标6的位置上，元素9在下标7的位置上。

如果我们把上述的文字描述，转换为图片，则会如下图所示：

这样就完成了第一轮的交换比较。经过第一轮交换后，元素9作为数列中最大的元素，就像是汽水里的气泡一样浮到了最右侧。接着我们继续如此重复上述的比较过程，每一轮结束后，都会有一个本轮最大的元素被移到了最右侧，如下所示：

每一轮的排序结果最终会如上图所示，所以最终的排序结果就是最后一排的数值结果。

最后我们来总结下，冒泡排序算法的3个核心步骤：

• 比较相邻的元素。如果第一个元素比第二个元素大，就将两者交换；

• 对每一对相邻的两个元素进行同样的操作。从开始第一对到结尾的最后一对，最后的元素就是最大的数。

• 针对所有元素重复以上步骤。每重复一轮上述步骤，需要操作的元素就会越来越少，直到没有任何一对元素需要比较。

代码实现

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。代码如下所示：

Array.prototype.bubble_sort = function() {var i, j, temp;for (i = 0; i < this.length - 1; i++)for (j = 0; j < this.length - 1 - i; j++)if (this[j] > this[j + 1]) {temp = this[j];this[j] = this[j + 1];this[j + 1] = temp;}return this;
}

选择排序

概念

选择排序(Selection Sort) 是一种最简单直观的排序算法。即使在我们的日常生活中，大家可能都会经常无意地进行选择排序。

例如：我们去超市买西红柿，拿了一个袋子，从众多的西红柿中挑了一个最大好的放入袋中，然后又从剩下的西红柿中挑了一个最大的放入袋子。这样如此反复，直到挑够了需要的西红柿去结账。这其实就是选择排序的实现思想，就是不断地从未排序的元素中选择最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素为空。

基于上述实现思想，我们就可以提取出选择排序的实现原理：

将一个数组分成有序的区间和无序的区间两部分，初始时有序区间为空，每次从无序区间中选出最小的元素，并放到有序区间的末尾，直到无序区间为空。

实现步骤

假如我们现在有一个待排序的数组[5，8，6，3，9，2，1，7]

若采用选择排序算法进行排序，其实现步骤如下：

1. 初始化待排序数组[5，8，6，3，9，2，1，7]；
2. 从待排序数组中，选出最小值1，和第一个元素5进行交换，即将最小的元素放在下标0的位置上；
3. 在剩下的无序区间的元素中，选择最小的元素2，并将最小的元素2与无序区间的第一个元素8进行交换。交换后，有序区间的元素变为2个，分别是1和2，剩余的为无序区间。
4. 依次类推，将所有的元素通过不断选择的方式，按有序的方式放到有序区间，最终把整个数组全部排好顺序。

我们把上述选择排序的文字描述内容，变成对应的图片，会如下图所示：

代码实现

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。代码如下：

function selectionSort(arr) {var len = arr.length;var minIndex, temp;for (var i = 0; i < len - 1; i++) {minIndex = i;for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {     // 寻找最小的数minIndex = j;                 // 将最小数的索引保存}}temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}return arr;
}

总结

• 冒泡排序属于交换排序算法的一种；

• 选择排序算法是原地排序算法的一种；

• 冒泡排序的核心思想是把相邻的元素进行两两比较，当一个元素大于右侧相邻的元素时，就交换它们的位置；当一个元素小于或等于右侧相邻的元素时，则保持位置不变。

• 选择排序的实现思想，就是不断地从未排序的元素中选择最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素为空。

两者的区别简单了说就是冒泡排序在比较的过程中待排序的数据会发生位置改变，而选择排序法在比较过程中，是记录较大/较小数据的索引，只有在找到最大/最小数据的时候才会发生交换。