使用插入排序的算法进行排序

Question

(插入排序）:编写程序，在主函数中用随机函数产生20个[0~100)之间的整数，存放于一个一维数组中，先输出排序前的数据，再使用插入排序的算法进行排序，最后输出排好序的数据。(提示：注意“观察哨方法”的使用；)

Answer 1

引自免费微信小程序：皆我百晓生

在C语言中，实现插入排序的基本步骤包括以下几个部分：

1. 定义一个int类型指针arr[]用于存储待排序数组。
2. 首先，生成随机数组arr，大小为20个0到100之间（含0和100）的整数，元素存储在arr数组中，并设置初始值arr[0] = 0。
3. 初始化一个空的辅助数组sorted_arr，用于存放排序后的数组，其初始值为NULL。
4. 使用一个循环遍历从0到19（因为C语言是升序排列）的每个元素arr[i]，并按照下面的顺序执行操作：
   • 计算当前元素arr[i]与sorted_arr[0]之间的差值diff = arr[i] - sorted_arr[0]。
   • 如果diff不大于0，则将arr[i]添加到sorted_arr的相应位置，使其移动到下一个位置，同时更新当前索引i为新的相邻位置索引。
   • 否则，返回0，表示当前元素已经正确地插入到排序序列中。
5. 当循环结束后，sorted_arr包含了已排序的数组，我们将其输出。
6. 函数返回一个新声明的指针sorted_arr，它指向原始数组arr的所有元素，但已按降序排列。

以下是完整的插入排序算法代码示例：

#include <stdio.h>

// Function to generate a random integer between 0 and 100 (inclusive)
int* generateRandomNumber(int min, int max) {
    return &((rand()) % ((max - min + 1)) * (min - max));
}

void insertionSort(int* arr, int n) {
    int i;
    for (i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // While the previous element is smaller than or equal to the current element,
        while (j >= 0 && arr[j] <= key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

void printArray(int* arr, int size) {
    int temp;
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    srand(time(NULL));  // Set seed for random number generation

    int arr[20];  // Initialize the array with random numbers
    int n = sizeof(arr) / sizeof(arr[0]);

    // Generate random numbers and populate the array
    for (int i = 0; i < 20; i++)
        arr[i] = generateRandomNumber(0, 100);

    printf("Original array:\n");
    printArray(arr, n);

    // Sort the array using Insertion Sort
    insertionSort(arr, n);

    printf("Sorted array in descending order:\n");
    printArray(arr, n);

    return 0;
}

这段代码首先定义了一个生成随机整数的函数generateRandomNumber，然后在insertionSort函数中实现了插入排序算法。这个函数遍历整个数组，对每个元素都比较它与之前找到的最小元素，并根据这个比较结果向后移动相应的元素，直到找到合适的位置放置新元素。最后，printArray函数用于输出排序后的数组。

在main函数中，我们首先初始化一个随机数组arr，然后调用insertionSort函数对其进行排序，接着输出排序前、排序后的数组。最后，我们在控制台打印出所有元素。通过这段代码，我们可以在C语言中实现插入排序算法，并按降序排列一个指定长度的随机整数数组。