一、排序算法系列目录说明

  • 冒泡排序（Bubble Sort）
  • 插入排序（Insertion Sort）
  • 希尔排序（Shell Sort）
  • 选择排序（Selection Sort）
  • 快速排序（Quick Sort）
  • 归并排序（Merge Sort）
  • 堆排序（Heap Sort）
  • 计数排序（Counting Sort）
  • 桶排序（Bucket Sort）
  • 基数排序（Radix Sort）

二、选择排序（Selection Sort）

选择排序(Selection sort)是一种简单直观的排序算法。

1. 基本思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。

2. 实现逻辑

① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换③ 依次类推下去……

3. 动图演示

排序算法之选择排序 - 图1
选择排序
注：红色表示当前最小值，黄色表示已排序序列，绿色表示当前位置。
具体的我们以一组无序数列｛20，40，30，10，60，50｝为例分解说明，如下图所示：
排序算法之选择排序 - 图2
4. 复杂度分析 平均时间复杂度：O(N^2)最佳时间复杂度：O(N^2)最差时间复杂度：O(N^2)空间复杂度：O(1)排序方式：In-place稳定性：不稳定 选择排序的交换操作介于和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。
比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N = (n-1) + (n-2) +…+ 1 = n x (n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。

5. 代码实现

C版本：

  1. // 选择排序（C）
  2. void selection_sort(int arr[], int len) {
  3.     int i, j, min, temp;
  4.     for (i = 0; i < len - 1; i++) {
  5.         min = i;
  6.         for (j = i + 1; j < len; j++)
  7.             if (arr[min] > arr[j])
  8.                 min = j;
  9.         temp = arr[min];
  10.         arr[min] = arr[i];
  11.         arr[i] = temp;
  12.     }
  13. }

C++版本：

  1. // 选择排序（C++）
  2. template<typename T>
  3. void selection_sort(T arr[], int len) {
  4.     int i, j, min;
  5.     for (i = 0; i < len - 1; i++) {
  6.         min = i;
  7.         for (j = i + 1; j < len; j++)
  8.             if (arr[min] > arr[j])
  9.                 min = j;
  10.         swap(arr[i], arr[min]);
  11.     }
  12. }

Java版本：

  1. // 选择排序（Java）
  2. public static void selection_sort(int[] arr) {
  3.     int i, j, min, temp, len = arr.length;
  4.     for (i = 0; i < len - 1; i++) {
  5.         min = i;
  6.         for (j = i + 1; j < len; j++)
  7.             if (arr[min] > arr[j])
  8.                 min = j;
  9.         temp = arr[min];
  10.         arr[min] = arr[i];
  11.         arr[i] = temp;
  12.     }
  13. }

6. 优化改进

①二元选择排序
改进思路： 简单选择排序，每趟循环只能确定一个元素排序后的定位。根据之前冒泡排序的经验，我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
②堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。具体的分析我们留到后面讲堆排序时再详细说明。

三、总结

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。