数据结构学习笔记-简单选择排序

zeta186012 / 2024-06-05 / 原文

简单选择排序的算法设计与分析

问题描述：设计并分析简单选择排序

【算法设计思想】

迭代选择: 算法通过循环遍历数组，进行 size 次迭代。

最小值选择: 在每次迭代 (i) 中，算法致力于找到未排序子数组 (arr[i] 到 arr[size-1]) 内最小元素的索引。这个最小元素将被选出来进行交换。

交换: 一旦最小元素的索引 (minIndex) 被确定，它就会与当前索引 (i) 处的元素进行交换。这实际上将最小元素放置在未排序子数组开头的正确排序位置。

渐进排序: 每次迭代，排序子数组都会增长一个元素，最终导致整个数组在循环结束时按升序排序。

【算法描述】

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

【完整的测试程序】

#include <iostream>
using namespace std;

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void selectionSort(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

int main(int argc, char const *argv[]) {
    int arr[6] = {1, 2, 3, 5, 3, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, size);
    printArray(arr, size);
    return 0;
}