简单选择排序

选择类排序的主要动作是“选择”，简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。

代码：

#include <iostream>
using namespace std;

void print_array(int array[], int n) {
  for (int i = 0; i < n; ++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

void SelectSort(int array[], int n) {
  int i, j, temp, k, min;
  for (i = 0; i < n; ++i) {
    min = array[i];
    for (j = i; j < n; ++j) {
      if (array[j] < min) {
        min = array[j];
        k = j;
      }
    }

    temp = array[i];
    array[i] = array[k];
    array[k] = temp;
  }
}

int main() {
  int array[] = {49, 38, 65, 97, 76, 13, 27};
  print_array(array, 7);
  SelectSort(array, 7);
  print_array(array, 7);

  return 0;
}

复杂度分析：

1. 时间复杂度：
两层循环，时间复杂度为O(n^2).

2. 空间复杂度：
空间复杂度常量级别，为O(1).