定义

简单选择排序法（Simple Selection Sort） 就是通过 n-i 次关键字间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i（1≤i≤n）个记录交换之。

实现思路

1. 确定排序区间：从第一个元素开始，依次将未排序区间中的最小值选出来。
2. 查找最小值：每次在未排序区间（从当前位置到末尾）遍历，找到最小元素的下标。
3. 交换位置：将找到的最小元素与当前排序区间的第一个元素交换。
4. 重复步骤：每次确定一个元素的位置，直到所有元素有序。

代码实现

#include <stdio.h>

#define MAXSIZE 5
#define OK 1
#define ERROR 0

typedef struct {
  int array[MAXSIZE + 1]; /* 排序数组， array[0] 用作哨兵或临时变量 */
  int length;
} SqList;

void swap(SqList *L, int i, int j) {
  int temp = L->array[i];
  L->array[i] = L->array[j];
  L->array[j] = temp;
}
void SelectSort(SqList *L) {
  int i, j, minIndex;
  for (i = 1; i < L->length; i++) {
    minIndex = i;
    for (j = i + 1; j <= L->length; j++) {
      if (L->array[j] < L->array[minIndex])
        minIndex = j;
    }
    if (minIndex != i)
      swap(L, i, minIndex);
  }
}

int main(void) {
  SqList L;
  L.length = 5;
  L.array[1] = 5;
  L.array[2] = 4;
  L.array[3] = 3;
  L.array[4] = 2;
  L.array[5] = 1;

  printf("排序前：\n");
  for (int i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");

  SelectSort(&L);

  printf("排序后：\n");
  for (int i = 1; i <= L.length; i++) {
    printf("%d ", L.array[i]);
  }
  printf("\n");
  return 0;
}

排序前：
5 4 3 2 1 
排序后：
1 2 3 4 5 

[Done] exited with code=0 in 0.368 seconds

复杂度分析

第 i 次排序需要进行 n – i 次关键字的比较，需要比较 n-1 + n-2 +…+1 = n(n-1)/2 次。
对于交换次数而言，当最好的时候，交换为 0 次，最差的时候，也就初始降序时，交换次数为 n-1 次，加上比较时间，复杂度是O(n^2).