排序算法-选择排序

选择排序

选择排序是一种简单的基于交换的排序算法，但是易于实现。

1.思想

以升序排序为例
从待排序的序列中找到最小的一个元素，然后与待排序序列中的第一个元素进行交换，此时待排序列已经从第二个元素开始；
然后从待排序的序列中找到最小的一个元素，然后与待排序序列中的第一个元素进行交换，此时待排序列已经从第三个元素开始。
以此类推，最终得到一个有序的序列。

实现

template<typename T>
vector<T> selectScort(vector<T> data)
{
      for (int i = 0; i<data.size(); ++i)
{
      int min = data[i]; //记录最小值
      int minIndex = i; //最小值的索引
      for (int j = i; j<data.size(); ++j)
{
      //碰到更小的就更新
      if(data[j] <min)
{
      min = data[j];
      minIndex = j;
}
}
      swap(data[i],data[minIndex]);
}
      return data;
}

分析

每趟排序完成后，数据位置都是最终值，并且时间复杂度为O(n^2).

排序算法-选择排序

原文：https://www.cnblogs.com/kinfe/p/14210335.html