排序-选择排序(交换类型-循环嵌套)

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤：

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕

时间复杂度和空间复杂度

时间复杂度：
(1)最好： O(n2）
（2)最坏：O(n2)
(3)平均： O(n2）

空间复杂度：
O（1）

参考代码

C语言

#include <stdio.h>

void swap(int a[],int i,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void sort(int a[],int length){
    for (int i = 0; i<length; i++) {
        int minIndx = i;
        for (int j = i+1; j<length; j++) {
            if (a[minIndx] > a[j]) {
                minIndx = j;
            }
        }
        if (i != minIndx) {
            swap(a, i, minIndx);
        }
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int a[] = {1,6,4,8,7,5,3,2};
    sort(a,8);
    for (int i = 0; i<8; i++) {
        printf("%d ",a[i]);
    }
    return 0;
}