数据结构--经典排序之选择排序（超详细！！）

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是，首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点是与数据规模较小，其在待排序的数据规模较小时，效率较高，且实现简单。但是其缺点是不论数据量大小，都需要进行n*(n-1)/2次比较，时间复杂度为O(n^2)，所以不适合数据规模大的情况。

代码实现

方法一：一次排一个
过程说明：
1.初始化外层循环变量i为0，表示当前要排序的元素索引。
2.对于数组中的每个元素（由i指示），执行以下步骤：
2.1.初始化内层循环变量j为i+1，表示从当前元素的下一个元素开始比较。
2.2 遍历剩余的元素（由j指示），找到最小的元素并记录其索引min。
2.3 使用Swap函数交换当前元素（索引为i）和找到的最小元素（索引为min）的位置。
3.外层循环继续，直到所有元素都排好序。

// 选择排序函数，对数组a中的n个元素进行排序  
void Swap(int* a, int* b) {//用于交换两个整数的值  int tmp = *a;*a = *b;*b = tmp;
}
void SelectSort(int* a, int n) {  int i, j, min; // 声明循环变量i, j和最小元素索引min  // 外层循环，遍历数组的每一个元素  for (i = 0; i < n; i++) {  // 初始化最小元素的索引为当前索引i  min = i;  // 内层循环，从当前元素的下一个元素开始，遍历剩余的元素  for (j = i + 1; j < n; j++) { // 注意，这里从i+1开始，因为前面的元素已经排好序了  // 如果找到一个更小的元素，则更新最小元素的索引  if (a[j] < a[min]) {  min = j;  }  }  // 交换当前元素和找到的最小元素的位置  Swap(&a[i], &a[min]);  }  
}  

方法二：一次排两个
过程说明：
1.Swap 函数是一个简单的值交换函数，它接受两个整数的指针，并交换它们所指向的值。
2.SelectSort 函数是一个选择排序的变种。在传统的选择排序中，我们通常只找剩余部分的最小值（或最大值）并与首元素交换。但在这里，我们同时找最大值和最小值，并将它们分别与排序区间的两端进行交换。这样做的好处是可以加速排序过程，尤其是在数据部分有序或完全有序的情况下。
3.在每次循环中，我们首先初始化max和min为区间的起始位置begin。然后，我们遍历begin到end之间的所有元素，找到这个区间内的最大值和最小值的位置。
4.接着，我们使用Swap函数将begin位置的值与最小值进行交换，这样确保了begin位置始终是已排序的最小值。
5.如果在交换之前，max恰好是begin，那么由于begin位置的值已经被交换出去，我们需要更新max为min的位置。
6.然后，我们使用Swap函数将end位置的值与最大值进行交换，这样确保了end位置始终是已排序的最大值。
7.最后，我们缩小排序区间（begin++和end–）

// 函数Swap用于交换两个整数的值  
void Swap(int* a, int* b) {  // 创建一个临时变量tmp，用于存储a指向的值  int tmp = *a;  // 将b指向的值赋给a指向的变量  *a = *b;  // 将临时变量tmp的值（即原来a的值）赋给b指向的变量  *b = tmp;  
}  // 函数SelectSort实现了选择排序算法，但有所变化，它同时考虑了最大值和最小值  
void SelectSort(int* a, int n) {  // begin表示排序区间的起始位置，end表示排序区间的结束位置  int begin = 0, end = n - 1;  // 当begin小于end时，继续进行排序  while (begin < end) {  // 初始化max和min为begin，它们分别用于记录当前排序区间内的最大值和最小值的位置  int max = begin, min = begin;  // 遍历begin到end之间的所有元素  for (int i = begin+1; i <= end; i++) {  // 如果找到比当前最大值还大的元素，更新max  if (a[i] > a[max]) {  max = i;  }  // 如果找到比当前最小值还小的元素，更新min  if (a[i] < a[min]) {  min = i;  }  }  // 将begin位置的值与最小值进行交换  Swap(&a[begin], &a[min]);  // 如果最大值的位置恰好是原来的begin位置（现在已经与最小值交换了），则更新max为min的位置  if (max == begin) {  max = min;  }  // 将end位置的值与最大值进行交换  Swap(&a[end], &a[max]);  // 缩小排序区间，继续下一轮排序  begin++;  end--;  }  
}

使用示例

#include<stdio.h>void PrintArray(int* a, int n)//打印
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void Swap(int* a, int* b) {int tmp = *a;*a = *b;*b = tmp;
}void SelectSort1(int* a, int n) {int begin = 0, end = n - 1;while (begin < end) {int max = begin, min = begin;for (int i = begin+1; i <= end; i++) {if (a[i] > a[max]) {max = i;}if (a[i] < a[min]) {min = i;}}Swap(&a[begin], &a[min]);if (max == begin) {max = min;}Swap(&a[end], &a[max]);begin++;end--;}
}void SelectSort2(int* a, int n) {for (int i = 0; i < n; i++) {int min = i;for (int j = i + 1; j < n ; j++) {if (a[j] < a[min]) {min = j;}}Swap(&a[min], &a[i]);}
}void TestSort()
{int a[] = { 6, 3, 9, 1, 5, 8, 2, 4, 7};PrintArray(a, sizeof(a) / sizeof(int));//计算数组元素个数并打印SelectSort1(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main() {TestSort();return 0;
}