辽源网站建设设计,网站开发需要哪些职位,十大热门网页游戏排行,无锡做网站费用文章目录 冒泡排序(交换排序#xff09;基本思想特性总结代码实现 直接选择排序基本思想特性总结代码实现#xff08;优化#xff0c;每次循环同时选择最小和最大的数#xff09; 冒泡排序(交换排序#xff09;
基本思想
基本思想#xff1a;所谓交换#xff0c;就是根… 文章目录 冒泡排序(交换排序基本思想特性总结代码实现 直接选择排序基本思想特性总结代码实现优化每次循环同时选择最小和最大的数 冒泡排序(交换排序
基本思想
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定
代码实现
void bubbleSort(int* a, int n)//冒泡排序(时间复杂度为O(N^2),空间复杂度为O(1))
{for (int i 0; i n; i){bool exchange false;for (int j 1; j n - i; j){if (a[j - 1] a[j]){int tmp a[j];a[j] a[j - 1];a[j - 1] tmp;exchange true;}}if (exchange false)break;}
}直接选择排序
基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素 特性总结
直接选择排序思想非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
代码实现优化每次循环同时选择最小和最大的数
void Swap(int a, int b)
{int tmp a;a b;b tmp;
}void printArr(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void selectSort(int* a, int n)//选择排序时间复杂度为O(N^2),空间复杂度为O(1)
{int begin 0, end n - 1;while (begin end){int maxi begin, mini begin;for (int i begin; i end; i){if (a[i] a[maxi])maxi i;if (a[i] a[mini])mini i;}Swap(a[begin], a[mini]);if (maxi begin)//如果maxi和begin重叠修正一下即可{maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
}
