java 实现排序算法系列
继冒泡排序算法之后，选择排序终于和大家见面了。为什么冒泡排序之后要说选择排序呢，是因为它俩是最相似的两种排序算法，血缘关系最为接近。
还是那句话，本人能力拙劣，有不当之处还请不吝赐教，可关注我公号后台留言，见底部二维码。
选择排序
选择排序（Selection sort）是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度。可以把它看做是冒泡排序算法的一种改进算法。
算法思路
假设要给有 n 个元素的数组 arr[] 排序。注意，在数组中第一个元素的下标为 0
n = 1:
无需排序
n > 1:
- 将第一个元素和第二个元素进行比较，如果 arr[0] 大于 arr[1]，那么 arr[0] 一定不是最小元素。这里我们暂时不交换元素，而是设置临时变量 a，用来存储较小变量 arr[1] 的下标。然后将目前较小元素 arr[a] 继续和第三个元素比较，如果 arr[a] 大于 arr[2]，则修改 a 的值为 arr[2] 的下标，再接着往下比较；如果不大于 arr[2]，则将 arr[a] 和第四个元素比较，如前者大，则修改 a 的值为 arr[3] 的下标。以此类推，直到与最后一个元素比较，则 a 的值肯定是最小值的下标。
- 如果 a 的值不为 0（即不是元素 arr[0] 的下标)，则交换下标为 0 和 a 的元素，即将 arr[a] 和 arr[0] 进行交换。
- 至此，第一趟排序完成，将最小值找出来了，然后进行第二趟排序。重复上述过程，从第二个元素（即 arr[1]）开始比较。第一个元素已经是最小元素了，不参与比较。
- 重复步骤直到剩下最后一个元素，即 arr[n-1]，可以肯定这个值为最大值。
- 排序完成，不够直观？见下面示例动画。
注: 红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
需要注意的是，上述过程只是每次找最小值的办法。实际上也可以每次找最大值，思路是一样的。
选择排序的示意图（图片来自维基百科）：
代码实现
设要给数组 arr[] 排序，它有 n 个元素。
public static void selectionSort(int[] arr) {
int min, temp, len = arr.length;
for (int i = 0; i < len - 1; i++) {
min = i;//未排序序列中最小数据数组下标
for (int j = i + 1; j < len; j++) { //在未排序元素中继续寻找最小元素，并保存其下标
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[min]; //将最小元素放到已排序序列的末尾
arr[min] = arr[i];
arr[i] = temp;
}
}
}
算法复杂度
选择排序需要进行 n-1 轮比较。很显然，比较次数 O(n^2)，比较次数与关键字的初始状态无关，总的比较次数 N = (n-1) + (n-2) + ... + 1 = n x (n-1) / 2。
交换次数 O(n)，最好情况是，已经有序，交换 0 次；最坏情况是，逆序，交换 n-1 次。交换次数比冒泡排序较少，由于交换所需 CPU 时间比比较所需的 CPU 时间多，n 值较小时，选择排序比冒泡排序快。
选择排序的赋值次数：最坏情形下需要交换 n-1 次，对于上面的代码，需要赋值 3(n-1) 次。而最佳情况下，则需要 0 次。如果假定平均分布，大约需要 3n/2。
冒泡排序可以在最佳情况下有 O(n) 复杂度，那么选择排序行不行呢？ 很遗憾，不行。选择排序每次只找最小值，但它并不能知道其他值是否有序排列。因此，选择排序在最优、最坏、平均情况下的时间复杂度均为 O(n^2)，空间复杂度（额外空间）为 O(1).
算法稳定性
对于选择排序的稳定性是存在一定争议的。但在本例中，最小值和另一个值相同的时候我们并不需要交换它们，选择排序是稳定排序。其实排序算法中，有些稳定算法可以变换成不稳定算法，而不稳定排序算法又有很多办法可以变成稳定的，这在《算法》第四版中有所提及。所以，没有严格意义上的稳定与不稳定排序。
算法适用场景
选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的 O(n^2) 复杂度，选择排序在数据量较大的时候显得力不从心。因此，它适用于简单数据排序。
ikook
2017.08.11
网友评论