排序算法：简单选择排序

简单选择排序是一种基于比较的排序算法，其基本思想是每次从未排序的元素中选择最小的元素，放到已排序的末尾。

具体步骤如下：

1. 初始化数组，将第一个元素看作已排序的数组，其余元素看作未排序的数组。

2. 遍历未排序的数组，找到最小的元素。

3. 将最小的元素与未排序数组的第一个元素交换位置，即将其放到已排序数组的末尾。

4. 重复 2-3 步骤，直到未排序数组为空。

简单选择排序的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$，并且它是一种不稳定的排序算法。

下面是一个简单选择排序的 C++ 代码实现：

void selectionSort(int 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;
            }
        }
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

在这个实现中，我们使用了两个嵌套的 for 循环，外层循环控制已排序数组的末尾，内层循环遍历未排序数组，并找到最小的元素。一旦找到最小的元素，就将其与未排序数组的第一个元素交换位置。

下面是一个使用简单选择排序对数组进行排序的示例：

int arr[] = { 64, 25, 12, 22, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
}
// 输出结果为：11 12 22 25 64

在这个示例中，我们首先定义了一个待排序的数组 arr，然后计算出数组的长度 n，调用 selectionSort 函数对数组进行排序，最后输出排序后的数组。

假设我们有一个待排序的数组 arr，它的元素依次为：4、1、3、7、5、2、6。下面我们使用简单选择排序对这个数组进行排序，具体过程如下：

1. 第一轮循环，已排序的数组为空，未排序的数组为整个数组，我们首先遍历未排序的数组，找到其中最小的元素 1，然后将其与未排序数组的第一个元素 4 交换位置，此时已排序的数组为 1，未排序的数组为 4、3、7、5、2、6。

2. 第二轮循环，已排序的数组为 1，未排序的数组为 4、3、7、5、2、6，我们遍历未排序的数组，找到其中最小的元素 2，然后将其与未排序数组的第一个元素 4 交换位置，此时已排序的数组为 1、2，未排序的数组为 4、3、7、5、6。

3. 第三轮循环，已排序的数组为 1、2，未排序的数组为 4、3、7、5、6，我们遍历未排序的数组，找到其中最小的元素 3，然后将其与未排序数组的第一个元素 4 交换位置，此时已排序的数组为 1、2、3，未排序的数组为 4、7、5、6。

4. 第四轮循环，已排序的数组为 1、2、3，未排序的数组为 4、7、5、6，我们遍历未排序的数组，找到其中最小的元素 4，然后将其与未排序数组的第一个元素 4 交换位置，此时已排序的数组为 1、2、3、4，未排序的数组为 7、5、6。

5. 第五轮循环，已排序的数组为 1、2、3、4，未排序的数组为 7、5、6，我们遍历未排序的数组，找到其中最小的元素 5，然后将其与未排序数组的第一个元素 7 交换位置，此时已排序的数组为 1、2、3、4、5，未排序的数组为 7、6。

6. 第六轮循环，已排序的数组为 1、2、3、4、5，未排序的数组为 7、6，我们遍历未排序的数组，找到其中最小的元素 6，然后将其与未排序数组的第一个元素 7 交换位置，此时已排序的数组为 1、2、3、4、5、6，未排序的数组为 7。

7. 第七轮循环，已排序的数组为 1、2、3、4、5、6，未排序的数组为 7，我们遍历未排序的数组，找到其中最小的元素 7，然后将其与未排序数组的第一个元素 7 交换位置，此时已排序的数组为 1、2、3、4、5、6、7

下面是使用C++实现简单选择排序的示例代码：

void selectionSort(int 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]);
    }
}

在这段代码中，我们先遍历数组，依次以 arr[i] 作为起始元素，向后寻找最小的元素。通过内部循环的遍历，我们记录下最小元素的下标，然后将其与 arr[i] 进行交换，这样最小元素就被放到了正确的位置上。这个过程就像是不断从待排序的元素中选择最小的一个，放到已排序的元素的最后面，直到所有元素都排好序为止。

下面是使用上述函数对一个整型数组进行排序的示例：

int main() {
    int arr[] = { 64, 25, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

该程序的输出结果为：

Sorted array: 11 12 22 25 64

在这里，我们首先定义了一个包含 5 个整型元素的数组 arr，然后使用 selectionSort 函数对该数组进行排序，并输出排序后的结果。