簡單選擇排序

選擇類排序的主要動作是“選擇”，簡單選擇排序采用最簡單的選擇方式，從頭至尾順序掃描序列，找出最小的一個關(guān)鍵字，和第一個關(guān)鍵字交換，接著從剩下的關(guān)鍵字中繼續(xù)這種選擇和交換，最終使序列有序。

代碼：

#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. 時間復雜度：
兩層循環(huán)，時間復雜度為O(n^2).

2. 空間復雜度：
空間復雜度常量級別，為O(1).