选择排序(Selection Sort)是一种基于比较的排序算法。其基本思想是每次从未排序部分中选出最小(或最大)的元素,将其放在已排序部分的末尾。重复这一过程,直到所有元素都排序完成。
以下是选择排序的基本实现代码:
#include <stdio.h>
// 交换两个元素的值
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 选择排序函数
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
// 找到未排序部分的最小元素
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
// 交换最小元素和未排序部分的第一个元素
swap(&arr[min_idx], &arr[i]);
}
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// 主函数
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
printf("未排序的数组: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("排序后的数组: \n");
printArray(arr, n);
return 0;
}
swap
:
selectionSort
:
for
循环遍历数组,每次选出未排序部分的最小元素,并将其与未排序部分的第一个元素交换。min_idx
。printArray
:
main
:
selectionSort
函数对数组进行排序。选择排序的基本实现已经非常简单直接,但仍有一些优化方法可以稍微提升其性能:
减少交换操作:
优化代码示例:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
// 仅在需要时才进行交换
if (min_idx != i)
swap(&arr[min_idx], &arr[i]);
}
}
双向选择排序:
优化代码示例:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n/2; i++) {
int min_idx = i;
int max_idx = i;
for (int j = i+1; j < n-i; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
if (arr[j] > arr[max_idx])
max_idx = j;
}
// 交换最小值到未排序部分的起始位置
if (min_idx != i)
swap(&arr[min_idx], &arr[i]);
// 如果最大值是起始位置的元素,需要更新max_idx
if (max_idx == i)
max_idx = min_idx;
// 交换最大值到未排序部分的末尾位置
if (max_idx != n-i-1)
swap(&arr[max_idx], &arr[n-i-1]);
}
}
选择排序的时间复杂度为
,这是因为每次选出最小(或最大)元素都需要遍历未排序部分。无论最坏、最好还是平均情况,选择排序的时间复杂度都是
。虽然选择排序的时间复杂度较高,但由于其简单性,在处理小型数据集时仍有一定的应用价值。
选择排序的空间复杂度为
,因为它只需要常数级别的额外空间来存储临时变量。选择排序是一个不稳定的排序算法,因为相同元素的相对位置可能会改变。
选择排序由于其简单性和易实现性,在以下几种情况下非常有用:
选择排序是C语言中一种简单且直观的排序算法,其实现简单且易于理解。尽管选择排序的效率较低,但通过减少不必要的交换操作和双向选择排序等方法,可以在一定程度上提升其性能。在学习和使用选择排序时,了解其优缺点以及适用场景,能够帮助我们更好地选择和使用排序算法。希望本文能帮助读者深入理解选择排序,并在实际编程中灵活应用。