首页C语言选择排序举例与分析

C语言选择排序举例与分析

时间: 2024-11-18 21:16:45 浏览: 82

在C语言中，选择排序是一种简单直观的排序算法，它的工作原理是每次从未排序的部分中找到最小（或最大）的元素，然后将其放到已排序部分的末尾。以下是选择排序的一个基本示例： ```c #include <stdio.h> void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // 找到剩余未排序部分中的最小值索引 int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 将找到的最小值与当前未排序部分的第一个位置交换 int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } int main() { int numbers[] = {5, 2, 8, 3, 9}; int length = sizeof(numbers) / sizeof(numbers[0]); printf("Original array: "); for (int i = 0; i < length; i++) { printf("%d ", numbers[i]); } selectionSort(numbers, length); printf("\nSorted array: "); for (int i = 0; i < length; i++) { printf("%d ", numbers[i]); } return 0; } ``` 在这个例子中，`selectionSort`函数接收一个整数数组和它的长度。内部循环遍历数组，每次都找到剩余部分中的最小元素，然后将其放置在当前未排序部分的起始位置。整个过程重复，直到数组完全排序。 **分析：** 1. 时间复杂度：选择排序的时间复杂度为O(n^2)，其中n是数组的长度。因为它包含两个嵌套循环，每个循环都需要遍历整个剩余部分。 2. 空间复杂度：由于选择排序是原地排序，不需要额外存储空间，所以空间复杂度为O(1)。 3. 适用场景：对于小规模数据或者需要稳定性的排序（即相等元素保持原始顺序），选择排序是一个简单的选项；但对于大规模数据或性能要求较高的应用，则不太理想。

阅读全文