排序方法——《选择排序》

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。
  

                                           博主主页：Yan. yan.
                                              C语言专栏
                                            数据结构专栏
                                         力扣牛客经典题目专栏

1、选择排序的基本思想

  选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2、选择排序的原理

  选择排序的基本原理如下：

• 将数组中arr[0] ~ arr[n-1]的元素中找出最大或最小的数
• 将找的的数放到数组的第一个位置或最后一个位置上
• 剩余的元素重复上述步骤，直到数组元素完全有序

  像图中所示，一直重复循环，直到数组有序

3、选择排序的实现

  选择排序的实现有两种：

• 只找大，或只找小

void Swap(int* a, int* b)
{int ret = *a;*a = *b;*b = ret;
}void SelectSort(int* arr, int n)
{for (int j = 0; j < n; j++){int begin = 0;for (int i = 1; i < n; i++){int min = begin;while (arr[i] < arr[min]){min = i;}Swap(&arr[begin], &arr[min]);begin++;}}
}

• 一起找大和小，定义begin和end，最小的和begin交换，最大的和end交换

void Swap(int* a, int* b)
{int ret = *a;*a = *b;*b = ret;
}
void SelectSort(int* arr, 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++){while (arr[i] < arr[min]){min = i;}while (arr[i] > arr[max]){max = i;}}Swap(&arr[begin], &arr[min]);if (begin == max){max = min;}Swap(&arr[end], &arr[max]);begin++;end--;}
}

时间复杂度：O(N^2)
空间复杂度：O(1)
不稳定