目录
前言
建议：1.学习算法最重要的是理解算法的每一步，而不是记住算法。
2.建议读者学习算法的时候，自己手动一步一步地运行算法。
tips:希尔排序算法就是通过该算法衍生出来的，通过理解本算法可以为理解希尔排序打下基础。同时，本算法的逻辑简单。
直接排序算法，也称为选择排序（Selection Sort），是一种简单直观的排序算法。其基本思想是每一趟从待排序的数据元素中选择最小（或最大）的一个元素，将它与序列的第一个元素进行交换，然后再从剩余的元素中选择最小（或最大）的元素，与序列的第二个元素进行交换，如此循环，直到整个序列有序。总结就是，将无序元素与其前面的元素比较大小，以此来确定其位置，从而将其加入前面的有序的部分。
一、代码实现
#include <stdio.h>
// 交换数组中两个元素的值
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// 直接排序函数
void selectionSort(int arr[], int n) {
int i, j, min_idx;
// 选择排序的主循环
for (i = 0; i < n-1; i++) {
// 寻找在未排序部分中的最小元素的索引
min_idx = i;
for (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排序后的数组: \n");
printArray(arr, n);
return 0;
}在这段代码中，swap 函数用于交换数组中两个元素的值，而 selectionSort 函数实现了直接排序算法。主要的思路是在未排序的部分中找到最小元素的索引，然后与当前位置的元素进行交换，通过不断进行这样的操作，实现整个数组的排序。
二、时空复杂度
时间复杂度：
直接排序算法的时间复杂度主要由两层循环决定。
外层循环：外层循环的次数是 n-1，其中 n是数组的长度。这是因为在进行 n-1次选择后，剩下的最后一个元素已经有序了。
内层循环：内层循环用于在未排序的部分中寻找最小元素的索引。在最坏情况下，每次选择都需要遍历剩余未排序的元素。内层循环的次数是n,n-1,n-2,…,1。其平均时间复杂度为。
综合考虑外层和内层循环(只要考虑n的次数大的复杂度)，直接排序的时间复杂度为
其平均/最好/最差时间复杂度均为
空间复杂度：
直接排序是一种原地排序算法，它只需要常数级别的额外空间来存储少量的辅助变量，如循环中的索引和临时变量。因此，直接排序的空间复杂度为 O(1)，即常数级别的额外空间。
