C语言实现排序之选择排序算法

1.代码

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// 函数声明
int* create_and_generate_random_array(int size);
void print_array(int *array, int size);
void selection_sort(int *array, int size);
int generate_random_size();

int main() {
    int size = generate_random_size(); // 随机生成数组大小

    int *array = create_and_generate_random_array(size);

    if (array == NULL) {
        // 如果内存分配失败
        printf("Memory allocation failed\n");
        return 1;
    }

    // 打印原始数组（如果需要，可以取消注释）
    // printf("Original array:\n");
    // print_array(array, size);

    // 获取开始时间
    clock_t start_time = clock();

    // 对数组进行选择排序
    selection_sort(array, size);

    // 获取结束时间
    clock_t end_time = clock();

    // 计算时间差并转换为毫秒
    double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;

    // 打印排序后的数组（如果需要，可以取消注释）
    // printf("Sorted array:\n");
    // print_array(array, size);

    printf("array_size = %d\n", size);

    // 打印执行时间
    printf("Execution time: %.2f ms\n", execution_time);

    // 释放分配的内存
    free(array);

    return 0;
}

// 生成随机数组大小
int generate_random_size() {
    srand(time(NULL));
    return rand() % 9000 + 1000; // 生成1000到9999之间的随机数
}

// 创建并生成随机数组
int* create_and_generate_random_array(int size) {
    int *array = (int *)malloc(sizeof(int) * size);
    if (array == NULL) {
        // 如果内存分配失败
        return NULL;
    }

    // 使用当前时间作为随机数种子
    srand(time(NULL));
    for (int i = 0; i < size; i++) {
        array[i] = rand() % 1000; // 生成0到999之间的随机数
    }

    return array;
}

// 打印数组
void print_array(int *array, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// 选择排序
void selection_sort(int *array, int size) {
    for (int i = 0; i < size - 1; i++) {
        // 找到最小元素的索引
        int min_index = i;
        for (int j = i + 1; j < size; j++) {
            if (array[j] < array[min_index]) {
                min_index = j;
            }
        }
        // 交换最小元素和当前元素
        int temp = array[min_index];
        array[min_index] = array[i];
        array[i] = temp;
    }
}

2.分析

/*
 * 选择排序（Selection Sort）的时间复杂度和稳定性如下：

### 时间复杂度

选择排序的时间复杂度可以分为以下几种情况：

1. **最佳情况（Best Case）**：
   - 无论数组是否有序，选择排序都需要进行 n-1 次比较，时间复杂度为 O(n^2)。

2. **最坏情况（Worst Case）**：
   - 同样，无论数组是否有序，选择排序都需要进行 n-1 次比较，时间复杂度为 O(n^2)。

3. **平均情况（Average Case）**：
   - 在所有可能的排列情况下，选择排序的时间复杂度也是 O(n^2)。

### 空间复杂度

选择排序的空间复杂度为 O(1)，因为它是原地排序算法，不需要额外的存储空间。

### 稳定性

选择排序是不稳定的排序算法。稳定性指的是在排序过程中，两个相等的元素的相对顺序是否会改变。在选择排序中，交换元素时可能会改变相等元素的相对顺序。

### 总结

- **时间复杂度**:
  - 最佳情况: O(n^2)
  - 最坏情况: O(n^2)
  - 平均情况: O(n^2)
- **空间复杂度**: O(1)
- **稳定性**: 不稳定

选择排序虽然简单易懂，但由于其最坏、平均和最佳情况下的时间复杂度均为 O(n^2)，在处理大规模数据时性能较差，因此在实际应用中较少使用，
 更多是用于教学和理解排序算法的基础概念。
 */

/*
 * `return rand() % 9000 + 1000;` 用于生成一个介于 1000 到 9999 之间的随机整数。它的原理可以通过以下步骤来理解：

1. **rand() 函数**：
   - `rand()` 是一个标准的 C 库函数，用于生成一个介于 0 和 RAND_MAX 之间的伪随机整数。`RAND_MAX` 是一个常数，通常是 32767（取决于实现）。

2. **取模运算**：
   - `rand() % 9000` 通过取模运算将 `rand()` 的结果限制在 0 到 8999 之间。取模运算 `%` 返回除法的余数，所以任何数 `rand()` 生成的数对 9000 取模，其结果都会在 0 到 8999 之间。

3. **调整范围**：
   - `rand() % 9000 + 1000` 将取模运算的结果加上 1000，从而将数值范围调整到 1000 到 9999 之间。具体来说：
     - 最小值：当 `rand() % 9000` 为 0 时，结果是 `0 + 1000 = 1000`。
     - 最大值：当 `rand() % 9000` 为 8999 时，结果是 `8999 + 1000 = 9999`。

总结来说，这段代码通过取模和加法操作，将 `rand()` 生成的 0 到 RAND_MAX 之间的伪随机数转换为 1000 到 9999 之间的伪随机数。

### 详细步骤

1. **生成随机数**：
   - `rand()` 生成一个伪随机数，例如假设生成的数为 `X`。

2. **限制范围**：
   - 计算 `X % 9000`，将 `X` 限制在 0 到 8999 之间。

3. **平移范围**：
   - 将结果加上 1000，把范围从 0 到 8999 平移到 1000 到 9999。

### 举例

假设 `rand()` 生成的伪随机数是 12345，那么：

1. `12345 % 9000` 计算结果为 345。
2. `345 + 1000` 计算结果为 1345。

所以，生成的随机数是 1345，确实在 1000 到 9999 之间。

### 使用 srand(time(NULL))

为了确保每次运行程序时 `rand()` 生成不同的随机数，通常使用 `srand(time(NULL))` 来设置随机数种子。`time(NULL)` 返回当前时间，
 以此作为种子值，使 `rand()` 生成的数列每次都不同。
 */