数据结构与算法：选择排序

介绍

选择排序是一种简单直观的排序算法，其基本思想是：从待排序的数据元素中，每次选择最小（或最大）的元素，将其与序列的起始位置交换，然后继续对剩余的元素进行排序，知道整个序列排序完成。

算法步骤

1、从待排序的序列中选择一个最小的元素，将其与序列第一个位置交换。

2、在剩余未排序的元素中继续选择最小的元素，放到已排序序列的末尾。

3、重复上述步骤，知道所有元素排序完成

优缺点

优点：

简单易懂：选择排序算法简单直观，易于实现和理解适用于小规模数据集：在小规模数据集上表现良好部分有序数据集优化：在部分有序的数据集上可以进行优化内存要求低：适用于对内存要求严格的场景不敏感的数据集顺序：适用于对数据集的顺序不敏感的情况

缺点：

效率低：时间复杂度为,不适合大规模数据集多次交换：需要进行多次交换操作不稳定性：选择排序是不稳定的排序方法。相同的元素在排序后的相对位置可能会改

代码 #include <stdio.h> void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void Print(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void SelectSort(int* a, int n) { int begin = 0; while (begin < n - 1) { int min = begin; for (int i = begin + 1; i < n; i++) { if (a[i] < a[min]) { min = i; } } Swap(&a[begin], &a[min]); begin++; } } int main() { int a[] = { 9,1,2,5,7,4,6,3 }; int sz = sizeof(a) / sizeof(int); SelectSort(a, sz); Print(a, sz); return 0; } 优化

每次循环只取一个最小值效率太慢，可以同时去最小值和最大值。

void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int min = begin; int max = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] < a[min]) { min = i; } if (a[i] > a[max]) { max = i; } } Swap(&a[begin], &a[min]); if (begin == max) max = min; Swap(&a[end], &a[max]); begin++; end--; } }