选择排序

选择排序（Selection Sort）

有了冒泡排序为什么还要发明选择排序？冒泡排序有个很大的弊端，就是元素交换次数太多了。

想象一个场景，假设你是一名体育老师，正在指挥一群小学生按照个头从矮到高的顺序排队。采用冒泡排序的方法需要频繁交换相邻学生的位置，同学们心里恐怕会想：“这体育老师是不是有毛病啊？”

在程序运行的世界里，虽然计算机并不会产生什么负面情绪，但是频繁的数组元素交换意味着更多的内存读写操作，严重影响了代码运行效率。

有一个简单的办法，就是每一次找到个子最矮的学生，直接交换到队伍的前面。

例如一个有8个数字组成的无序序列，进行升序排序。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

算法分析

算法每一轮选出最小值，再交换到左侧的时间复杂度是 $O(n)$ ，一共迭代n - 1轮，总的时间复杂度是 $O(n^2)$ 。

由于算法所做的是原地排序，并没有利用额外的数据结构，所以空间复杂度是 $O(1)$ 。

时间复杂度	空间复杂度	稳定性	设计思想
$O(n^2)$	$O(1)$	不稳定	减治法

选择排序

#include <stdio.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

/**
 * Selection Sort (original v1.0)
 */
T *selection_sort(T *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }

    return arr;
}

int main() {
    int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

选择排序优化

选择排序的整体思想是在一个序列当中选出一个最小的元素，和第一个元素交换，然后在剩下的找最小的，和第二个元素交换。这样最终就可以得到一个有序序列。但是为了更加高效，可以每次选择出一个最小值和一个最大值，分别放在序列的最左和最右边。

选择排序优化

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

/**
 * Selection Sort (original v1.0)
 */
T *selection_sort(T *arr, int n) {
    for (int i = 0; i < n / 2; i++) {
        int minIndex = i;
        int maxIndex = n - i - 1;

        for (int j = i; j < n - i; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }

        swap(arr[i], arr[minIndex]);

        // In case of i == maxIndex before swap(arr[i], arr[minIndex]), it's now at minIndex.
        if (i == maxIndex) {
            maxIndex = minIndex;
        }

        swap(arr[n - i - 1], arr[maxIndex]);
    }

    return arr;
}

int main() {
    int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

题目

选择排序扫描剩余元素时，发现更小值应该立刻做什么？

题目

[2a,2b,1]执行一轮普通选择排序后是什么？

对[7,2,5,1]执行普通选择排序。每轮写出min下标的变化，以及扫描结束后的数组。统计比较次数和非自身交换次数。

选择排序

选择排序（Selection Sort）

有了冒泡排序为什么还要发明选择排序？冒泡排序有个很大的弊端，就是元素交换次数太多了。

在程序运行的世界里，虽然计算机并不会产生什么负面情绪，但是频繁的数组元素交换意味着更多的内存读写操作，严重影响了代码运行效率。

有一个简单的办法，就是每一次找到个子最矮的学生，直接交换到队伍的前面。

例如一个有8个数字组成的无序序列，进行升序排序。

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

算法分析

算法每一轮选出最小值，再交换到左侧的时间复杂度是 $O(n)$ ，一共迭代n - 1轮，总的时间复杂度是 $O(n^2)$ 。

由于算法所做的是原地排序，并没有利用额外的数据结构，所以空间复杂度是 $O(1)$ 。

时间复杂度	空间复杂度	稳定性	设计思想
$O(n^2)$	$O(1)$	不稳定	减治法

选择排序

#include <stdio.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

/**
 * Selection Sort (original v1.0)
 */
T *selection_sort(T *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }

    return arr;
}

int main() {
    int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

选择排序优化

选择排序优化

PRO EXCLUSIVE探索不止于此

解锁完整互动实验、进阶解析与精选参考答案。

尊享 Pro 权益

#include <stdio.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

/**
 * Selection Sort (original v1.0)
 */
T *selection_sort(T *arr, int n) {
    for (int i = 0; i < n / 2; i++) {
        int minIndex = i;
        int maxIndex = n - i - 1;

        for (int j = i; j < n - i; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }

        swap(arr[i], arr[minIndex]);

        // In case of i == maxIndex before swap(arr[i], arr[minIndex]), it's now at minIndex.
        if (i == maxIndex) {
            maxIndex = minIndex;
        }

        swap(arr[n - i - 1], arr[maxIndex]);
    }

    return arr;
}

int main() {
    int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

题目

选择排序扫描剩余元素时，发现更小值应该立刻做什么？

题目

[2a,2b,1]执行一轮普通选择排序后是什么？

对[7,2,5,1]执行普通选择排序。每轮写出min下标的变化，以及扫描结束后的数组。统计比较次数和非自身交换次数。

选择排序

选择排序

选择排序（Selection Sort）

选择排序：逐步扫描，再交换最小值

算法分析

选择排序优化

优化选择排序：每轮选出最小值与最大值

知识测验

知识测验

区分更新min与交换

选择排序

选择排序

选择排序（Selection Sort）

选择排序：逐步扫描，再交换最小值

算法分析

选择排序优化

优化选择排序：每轮选出最小值与最大值

知识测验

知识测验

区分更新min与交换