6-1 判断顺序表的值是否有序(C) 分数 10

在C语言中，判断顺序表（数组或者链表）的值是否有序通常有几种常见方法：

1. **线性遍历**：从头到尾逐个比较相邻元素，如果发现任意两个连续的元素不符合递增或递减的顺序，则认为列表无序。这种方法适用于已知的升序或降序排列。

int is_sorted(int arr[], int n, bool ascending) {
    for (int i = 0; i < n - 1; i++) {
        if ((ascending && arr[i] > arr[i + 1]) || (!ascending && arr[i] < arr[i + 1])) {
            return 0;
        }
    }
    return 1;
}

这里的`ascending`参数用于指示排序方向，true表示升序，false表示降序。

2. **分治法**：可以采用二分查找的思想，对于有序序列，查找过程中若找到元素不在预期位置，即说明序列未按照单调顺序排列。

3. **堆排序辅助检查**：如果列表已经是部分有序（例如前半部分是有序的），可以先构建最大堆或最小堆，再依次将堆顶元素与最后一个元素交换并调整堆结构。如果最终堆为空或者只有一个元素，那么原序列就是有序的。

相关问题

pta6-1判断顺序表是否有序（Java语言描述

在Java中，判断一个顺序表（数组）是否有序，通常是指判断数组是否按照某种顺序（升序或降序）排列。我们可以遍历数组，比较相邻元素的大小来判断整个数组是否有序。以下是一个Java函数示例，用于判断数组是否为升序排列：

public class OrderCheck {
    // 判断数组是否为升序排列
    public static boolean isSorted(int[] arr) {
        if (arr == null || arr.length == 0) {
            // 空数组或null视为有序
            return true;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            // 比较相邻元素，如果后面的元素小于前面的元素，则不是升序
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        System.out.println("数组是否为升序排列: " + isSorted(array));
    }
}

这段代码定义了一个`isSorted`方法，它接受一个整型数组`arr`作为参数，并返回一个布尔值，表示该数组是否为升序排列。在`main`方法中，我们创建了一个测试数组，并调用`isSorted`方法来检查它是否有序。

6-1 基于顺序表的直接选择排序【有题解视频，可本地编译器调试】 分数 10

基于顺序表的直接选择排序是一种简单的排序算法，它的工作原理类似于找最小元素的过程。以下是基本步骤：

1. **遍历数组**: 从第一个元素开始，将其视为当前未排序部分中的最小元素。
2. **比较并交换**: 遍历剩余未排序部分，如果找到比当前最小元素小的元素，则交换它们的位置。
3. **移动边界**: 找到最小元素后，将其放到已排序部分的末尾。然后将未排序部分的指针向后移一位，继续寻找下一个最小元素。
4. **重复过程**: 继续上述步骤，直到整个数组都被排序。

**举例**：
假设有一个包含5个数字的顺序表：[8, 3, 1, 9, 4]，第一次遍历时，我们会找到最小的3，并将其与第一位交换，得到[3, 8, 1, 9, 4]。接着第二次遍历找到1，与第二位交换，得到[3, 1, 8, 9, 4]，以此类推，直到数组完全有序。

**代码示例**（Python伪代码）：

def selection_sort(lst):
    for i in range(len(lst)):
        min_index = i
        for j in range(i+1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j
        lst[i], lst[min_index] = lst[min_index], lst[i]
    return lst

# 测试排序
lst = [8, 3, 1, 9, 4]
sorted_lst = selection_sort(lst)