点击即玩的小游戏网站,百度的总部在哪里,潮州市工程建设网站,玄武区网站建设目录
前言
一、代码实现
二、时空复杂度
时间复杂度#xff1a;
空间复杂度#xff1a; 前言
建议#xff1a;1.学习算法最重要的是理解算法的每一步#xff0c;而不是记住算法。 2.建议读者学习算法的时候#xff0c;自己手动一步一步地运行算法。
tips:希尔排序算…目录
前言
一、代码实现
二、时空复杂度
时间复杂度
空间复杂度 前言
建议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 i1; 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)即常数级别的额外空间。
