选择排序

基本思想

以第一个元素为基准,与后面的元素进行对比.选择最值(最大值/最小值)与当前位置进行交换。对每个元素都为基准比较,这就是排序过程了.

实现过程

代码实现

int *select_sort(int *a, int length) {
    for (int i = 0; i < length; i++) {
        int min_value_index = i;
        for (int j = i + 1; j < length; j++) {
            // select the min value index and record it
            if (a[min_value_index] > a[j]) {
                min_value_index = j;
            }
        }
        if (min_value_index != i) {
            int temp = a[min_value_index];
            a[min_value_index] = a[i];
            a[i] = temp;
        }
       // print(a, length);
    }
    return a;
}

排序算法的评估

• 基于比较,交换的排序算法.
• 空间复杂度为$O(1)$,是一种原地排序算法.
• 最好情况,最坏情况,平均情况,的时间复杂度都是 $O(n^2)$.
• 是不是稳定的排序算法? 主要取决于: if (a[min_value_index] > a[j]) {min_value_index = j;} 如果是 a[min_value_index] >= a[j] 就是不稳定的排序算法.

最后

期望与你一起遇见更好的自己