c语言排序算法课后习题

Question

对a数组a[0]~a[n-1] 中存储的n个整数从小到大排序。排序算法是：第一趟通过比较将n个整数中的最小值放在a[0]中，最大值放在a[n-1] 中；第二趟通过比较将n个整数中的次小值放在a[1]中，次大值放在a[n-2] 中；……，以此类推，直到待排序序列为递增序列。
c语言

Answer 1

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

为了实现这个排序算法，我们可以使用一个简单的选择排序方法。以下是详细的步骤和对应的C语言代码：

1. 首先定义一个函数select_sort，它接受一个整型数组arr和它的长度n作为参数。
2. 在主循环中，我们从第一个元素开始遍历，对于每个位置i，我们需要找到剩余未排序部分中的最小值（如果i为奇数）或最大值（如果i为偶数），然后与当前位置交换。
3. 为了找到最小值或最大值，我们可以在剩下的元素中进行一次遍历，并记住当前找到的最小值或最大值及其索引。
4. 完成一轮遍历后，数组的第一个到第i个元素就按照要求排好序了。

下面是完整的C语言代码实现：

#include <stdio.h>

// Function to perform the selection sort
void select_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Determine if i is odd or even and find the corresponding extreme value
        int min_or_max = (i % 2 == 0) ? MIN : MAX;
        int min_or_max_val = arr[i];
        int min_or_max_index = i;

        // Find the minimum or maximum value in the unsorted part of the array
        for (int j = i + 1; j < n; j++) {
            if ((min_or_max == MIN && arr[j] < min_or_max_val) ||
                (min_or_max == MAX && arr[j] > min_or_max_val)) {
                min_or_max_val = arr[j];
                min_or_max_index = j;
            }
        }

        // Swap the found extreme value with the current position i
        int temp = arr[min_or_max_index];
        arr[min_or_max_index] = arr[i];
        arr[i] = temp;
    }
}

// Define MIN and MAX constants
#define MIN 0
#define MAX 1

int main() {
    int arr[] = {9, 5, 1, 6, 3, 7, 8, 2, 4}; // Example input array
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    select_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

这段代码首先打印出原始数组，然后调用select_sort函数对其进行排序，最后打印出排序后的数组。注意，这里使用了宏定义MIN和MAX来表示要查找的是最小值还是最大值，这样可以使代码更简洁易读。运行此程序，你会看到输入数组按题目要求进行了排序。