【选择排序】之C++实现

描述

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是：每一轮从待排序的数据中选择最小（或最大）的一个元素，然后与待排序数据的第一个元素交换位置。对剩余未排序的数据重复这个过程，直到所有数据排序完成。

实现思路

1. 遍历数组，找到最小元素的下标。
2. 将最小元素与当前遍历位置的元素交换位置。

图解

时间复杂度

选择排序的时间复杂度为O(n^2)，其中n为待排序的数组长度。

空间复杂度

选择排序的空间复杂度为O(1)，只需要常数级别的辅助空间。

示例代码

#include <iostream>

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;
            }
        }

        // 最小元素与当前元素交换
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        std::cout << "sort : " << i+1 << "  :";
        for(int k = 0; k < n-1; ++k)
        {
            std::cout << arr[k] << "\t";
        }
        std::cout << std::endl;
    }
}

int main() {
    int arr[] = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "sort Before:" << std::endl;
    selectionSort(arr, n);

    std::cout << "sort End: \n";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

结果：

注意事项

• 选择排序是一种不稳定的排序算法，即相同元素的相对顺序可能会改变。
• 选择排序的性能较差，不适用于大规模数据的排序。
• 在实际应用中，可以通过优化算法来提高选择排序的性能，比如记录最小元素的位置，然后直接交换。
• 需要进行多次交换操作，相比其他排序算法，选择排序的交换次数较多。

结论

不管脚步有多慢都不要紧，只要你在走，总会看到进步。