排序算法 - 直接选择排序

什么是直接选择排序？

直接选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次在未排序的元素中选择最小（或最大）的元素，把它放到已排序的末尾（或开头）位置，直到所有元素都排好序。直接选择排序是一种不稳定的排序算法。其时间复杂度为 O(N^2)。

算法步骤：

1. 从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
3. 从剩下的 N-1 个元素中，找到关键字最小的元素；
4. 重复步骤2、3，直到排序结束。

例如，对 [5, 3, 8, 6, 4] 进行直接选择排序，排序过程如下：

第一次排序：找到最小元素 3，与第一个元素 5 交换位置，序列变为 [3, 5, 8, 6, 4]；

第二次排序：找到最小元素 4，与第二个元素 5 交换位置，序列变为 [3, 4, 8, 6, 5]；

第三次排序：找到最小元素 5，与第三个元素 8 交换位置，序列变为 [3, 4, 5, 6, 8]；

第四次排序：找到最小元素 6，与第四个元素 8 交换位置，序列变为 [3, 4, 5, 6, 8]；

第五次排序：序列已经有序，排序结束。

最终得到的有序序列为 [3, 4, 5, 6, 8]。

直接选择排序有啥用呢？

虽然直接选择排序并不是最快的排序算法，但它有以下几个优点：

1. 简单直观：直接选择排序的实现非常简单，易于理解和实现。
   
2. 内存消耗小：直接选择排序算法的内存消耗较小，不需要额外的空间。
   
3. 对小规模数据排序效率高：当数据量较小的时候，直接选择排序的效率比较高，因为它只需要比较n-1次（n为数据的个数）。
   
4. 不会损坏原始序列的稳定性：直接选择排序不会改变两个相等元素的相对位置，因此是一种稳定的排序算法。
   

直接选择排序的算法的实现

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
//直接选择排序
void SelectSort(int* arr, int n)
{
  int i=0, j=0,mini=0;
  for (i = 0; i < n - 1; i++)//对n个元素排序，则需要进行n-1次排序
  {
    mini = i;//排完一次后最小值在最前面，最小值的位置随着i的变化而变化
    for (j = i+1; j < n; j++)//开始进行选择排序，因为[0 - i]已经有序了，所以从下标为i+1开始
    {
      if (arr[j] < arr[mini])
      {
        mini = j;//将较小值的下标赋给mini
      }
    }
    Swap(&arr[mini], &arr[i]);//将每次循环的较小值移到i位置，i从0开始，
    //当i=n-1时就结束循环，此时就已经排好序了
  }
}

直接选择排序的总结

综上所述，直接选择排序虽然不是最优秀的排序算法，但它具有简单直观，内存消耗小、对小规模数据排序效率高和不会损坏原始序列的稳定性等优点，因此仍然是一个比较实用的排序算法。