选择排序

废话不多说先上代码

void SelectionSort(int arr[], int length) {
    int temp;
    int max = 0;
    for(int x = 1; x < length; ++x) {
        for(int i = 1; i <= length - x; ++i) {
            if(arr[i] > arr[max]) {
                max = i;
            }
        }
        temp = arr[length - x];
        arr[length - x] = arr[max];
        arr[max] = temp;
        max = 0;
    }
}

时间复杂度

O(n²)

空间复杂度

O(1) 原地排序

稳定排序

不是是稳定排序

算法核心思想

从带排序数组中选择一个最大的数移动到数组最末尾，再从剩下的数中选择出一个最大的数放到倒数第二的位置以此类推。循环这个过程，直至待排序数组只剩下一个元素。这时数组已经有序。
一轮循环多少次？答：要选出最大的就要从头开始选，我们可以假设第一个最大，所以一共要进行length - 1 次比较。
一共要进行多少轮？答：每轮能将一个最大的数选出来放到最后，所以一共需要length - 1轮

一步一步实现选择排序

内层循环，选出一个最大的数和最后的数交换位置。

void selectionSort(int arr[], int length) {
    int temp;
    //假设最大元素的下标为0
    int max = 0;
    //找出最大元素的下标
    for(int i = 1; i < length; ++i) {
        //如果当前元素大于目前最大的元素就把最大的元素设为当前元素。
        if(arr[i] > arr[max]) {
            max = i;
        }
    }
    //交换元素
    temp = arr[max];
    arr[max] = arr[length - 1];
    arr[length - 1] = temp;
}

外层循环
内层循环每次将一个最大的数放到最后，所以要执行length - 1 次内层循环

void selectionSort(int arr[], int length) {
    int temp;
    int max;
    //循环length - 1次内循环
    for(int x = 1; x < length; ++x) {
        //假设最大元素的下标为0
        max = 0;
        //找出最大元素的下标
        //第一轮过后，最大的数已经在最后了，这时我们就不能再次和最后的数进行比较了。因为他一定是最大的数。
        for(int i = 1; i <= length - x; ++i) {
            //如果当前元素大于目前最大的元素就把最大的元素设为当前元素。
            if(arr[i] > arr[max]) {
                max = i;
            }
        }
        //交换元素
        temp = arr[max];
        //每经过一轮循环，就有一个最大的数在最后，这时就需要和他前一个数替换。
        arr[max] = arr[length - x];
        arr[length - x] = temp;
    }
}

选择排序就已经结束了，再次讲讲他的原理吧。

如果数组中只有一个数，这个数组就是有序数组。
我们可以规划一个有序区间，最开始这个有区间没有数。
我们取出要排序数组中最大的元素插入到有序区间的头部。
再从剩下的元素中取出最大的元素插入到有序区间的头部。
循环这个过程，直至没有元素。这时有序区间就是排序后的数组。