选择排序(selectionSort)

本文主要是介绍选择排序(selectionSort)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选择排序是一种简单直观的排序算法，其基本思想是：每次从未排序的元素中选取最小（或最大）的元素，放到已排序序列的末尾。下面是选择排序的详细解释及示例代码：

基本思想

1. 首先，从未排序的序列中找到最小（或最大）的元素，将其放到序列的起始位置。
2. 然后，从剩余未排序的元素中继续寻找最小（或最大）的元素，放到已排序序列的末尾。
3. 重复上述过程，直到所有元素都排好序。
4. 时间复杂度：O(n^2)。
5. 稳定性：不稳定。 

选择排序的特点

1. 相对简单：选择排序是一种比较简单的排序算法，易于理解和实现。
2. 不稳定：在排序过程中，相同大小的元素可能会交换位置，导致相同元素的相对位置发生变化，因此选择排序是一种不稳定的排序算法。
3. 原地排序：选择排序是一种原地排序算法，它不需要额外的辅助空间。
4. 时间复杂度：选择排序的时间复杂度为O(n^2)，其中n是待排序元素的数量。

选择排序的步骤如下：

1. 初始状态：将整个序列分为已排序部分和未排序部分，初始时已排序部分为空。
2. 选择最小元素：从未排序部分选择最小（或最大）的元素，并记录其位置。
3. 将最小元素交换到已排序部分的末尾。
4. 重复步骤2和步骤3，直到所有元素都排序完成。

#include<stdio.h>// 交换函数，用于交换数组中两个元素的值
void swap(int* x, int* y) {int temp = *x;*x = *y;*y = temp;
}// 选择排序函数
void selectionSort(int arr[], int n) {int i, j, minIndex;// 外层循环控制轮数，共需要 n-1 轮for (i = 0; i < n - 1; i++) {minIndex = i; // 假设当前轮次的第一个元素为最小值的索引// 内层循环在未排序的元素中找到最小值的索引for (j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 更新最小值的索引}}// 将当前轮次找到的最小值与当前轮次的第一个元素交换位置swap(&arr[i], &arr[minIndex]);    }
}int main() {int arr[] = { 5, 3, 8, 4, 2 };int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");selectionSort(arr, n);printf("排序后数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

这篇关于选择排序(selectionSort)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---