【2】选择排序算法

选择排序是一种简单的排序算法，其核心思想是每一次从待排序的元素中选择最小的元素，将其放在已排序的序列末尾，直到全部元素排序完成。

具体实现方法如下：

1. 遍历数组，将当前位置设为最小值索引minIndex。

2. 从当前位置后的元素中，寻找最小的元素，并记录其索引minIndex。

3. 若当前位置不是最小值，则将最小值与当前位置交换。

4. 重复1~3步，直到数组排序完成。

下面是使用C++实现选择排序的代码，同时包括动态演示过程：

#include <iostream>
using namespace std;

void selectionSort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
        cout << "Pass " << i+1 << ": ";
        for (int k = 0; k < n; k++) {
            cout << a[k] << " ";
        }
        cout << endl;
    }
}

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

输出结果如下：

Original array: 64 25 12 22 11 
Pass 1: 11 25 12 22 64 
Pass 2: 11 12 25 22 64 
Pass 3: 11 12 22 25 64 
Pass 4: 11 12 22 25 64 
Sorted array: 11 12 22 25 64

可以看到，每一轮排序后，都输出了当前数组的状态。