简单排序

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

基本思想

从待排序序列中，找到关键字最小的元素；交换到序列的最前面(有序子序列的最后面)。下次循环，再从剩余的待排序元素中继续寻找最小的元素，放到有序子序列的最后面。以此类推，直到全部待排序的数据元素排完。

int arr = {9,1,2,5,7,4,8,6,3,5};

//第一躺简单排序 扫描数组中最小的值 与第一个元素交换位置
int arr = {1,9,2,5,7,4,8,6,3,5};

//第二躺简单排序 因为第一个元素已经是最小的了 所以从第二个元素开始扫描 找到最小的值 与第二个元素交换位置

//... 依次类推

//代码实现

void selectSort(int *arr, int length) {
    int i, j, min, temp;
    // 循环比较的次数
    for (i = 0; i < length - 1; ++i) {
        // 保存当前循环的下标
        min = i;
        // 从当前元素的下一个元素开始，依次和当前元素比较，如果比当前元素小，那么就将该元素的下标保存到min中
        for (j = i + 1; j < length; ++j) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        // 如果min不等于i，那么就说明找到了比当前元素更小的元素，那么就将这两个元素交换位置
        if (min != i) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

算法分析

空间复杂度

O(1)

时间复杂度

无论是否有序，都需要进行 n(n-1)/2 次比较，时间复杂度为 O(n^2) O(n^2)