选择排序（Selection Sort）

  • 平均时间复杂度：O(n)
  • 最好情况：O(n)
  • 最坏情况：O(n)
  • 空间复杂度：O(1)
  • 排序方式：内部

  • 稳定性：不稳

    C++代码实现

    1. void selectionSort(vector<int>& arr) {
    2.   int len=arr.size();
    3.   int lhs = 0;
    4.   int rhs = len - 1;
    5.   while (lhs < rhs)
    6.   {
    7.       int max = lhs;
    8.       int min = lhs;
    9.       int j = 0;
    10.       for (j = lhs + 1; j <= rhs; j++) {
    11.           min = arr[j] < arr[min] ? j : min; 
    12.           max = arr[j]>=arr[max] ? j : max;
    14.       }
    15.       if (min != lhs) {
    16.           swap(arr[lhs], arr[min]);
    17.       }
    18.       //这里很重要，如果最大元素下标是lhs,
    19.       //前面已经和最小元素交换了，
    20.       //此时最大元素下标应该是min
    21.       if (max == lhs) {
    22.           max = min;
    23.       }
    24.       if (max != rhs) {
    25.           swap(arr[rhs], arr[max]);
    26.       }
    27.       lhs    ++;
    28.       rhs--;
    29.   }
    30. }

1. 算法步骤

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

    优化步骤

    ① 每一次遍历同时排序两个值，一个最大值，一个最小值，减少遍历次数

    2. 动图演示（无优化）

    selectionSort.gif