重庆网站制作哪家好,删除wordpress标志,天津百度爱采购,免费注册126邮箱冒泡排序
利用每趟都确定出一个最大值或者最小值
如果需要排一个从小到大的数组#xff0c;那么我们每一趟都要确定一个最大值放在最后#xff0c;一共有n个数#xff0c;我们最多需要排列n-1趟就可以了#xff0c;我们可以改进自己的代码#xff0c;利用一个flag标记那么我们每一趟都要确定一个最大值放在最后一共有n个数我们最多需要排列n-1趟就可以了我们可以改进自己的代码利用一个flag标记最初flag为0,当需要发生交换的时候flag修改成1,。
冒泡的时间复杂度最优的时候为On,最差的时候为O(n^2).
稳定性稳定
接下来我们写一下代码
void bubblesort(int*nums,int n){for(int i1;in-1;i){int flag0;for(int j0;jn-1-i;j){if(nums[j]nums[j1]){swap(nums[j],nums[j1]);flag1;}}if(flag0){return ;}}
}
排序算法都不需要返回值的。
选择排序
根据排序的名字我们就可以了解到这个排序和选择有关当然我们需要选择一个最大的或者最小的与待排序数组最后一个发生交换。
每次都要查找最后出待排序数组最大的一个元素我们采用遍历的形式最好用index标记最大值的数组下标。
void seletsort(int*nums,int n){for(int i1;in-1;i){int maxindex0;for(int j1;jn-i;j){if(nums[maxindex]nums[j]){maxindexj;}}if(maxindex!n-i){swap(nums[maxindex],nums[n-i]);}}
}时间复杂度O(n^2),在性能上优于冒泡稳定性不稳定
因为当几个相同的元素在筛选的时候会优先选择前边的先排列会造成元素之间位置交换所以选择排序在稳定性上并不稳定。
插入排序
将数组分为有序区和无序区在未排序的时候数组有序区元素个数为1个nums[0],遍历无序区
将无序区第一个元素与有序区的元素依次比较如果无序区元素大于有序区元素那么不用发生位置变化如果小于有序区元素有序区元素就要依次向后移动一位。
代码如下
void insertsort(int*nums,int n){for(int i1;in-1;i){int ji-1;int tempnums[i];for(;j0;j--){if(nums[j]temp){nums[j1]nums[j];}else{break;}}nums[j1]temp;}
}
时间复杂度当最好的情况数组本身就是有序的O(n), 最糟糕的情况O(n^2); 直接插入排序比冒泡选择的性能好一些。
稳定性分析稳定的
计数排序桶排序
望文生义桶排序就像一个大桶一样把数据都存储进去我们把数组比喻成了桶遍历一遍我们的待排序数组把数组中成功出现的元素记录在新数组中
这个新数组我们需要利用calloc申请空间因为calloc申请的数组默认初始化为0,最后记得要释放内存。
一个数可能在待排序数组中出现好多次我们需要解决好这个问题不能遗漏元素。
桶排序不是元素比较而是利用下标来确定元素的正确位置。
代码如下
首先需要一个函数确定待排序数组中最大的元素是几由此来确定桶的下标范围
int maxVal(int* nums, int n) {int max nums[0];for (int i 1; i n; i) {if (nums[i] max) {max nums[i];}}return max;
}void bucketsort(int* nums, int n) {int max maxVal(nums, n);//原数组最大值int* bucket (int*)calloc((max 1), sizeof(int));//用桶计数记录元素出现的次数for (int i 0; i n; i) {bucket[nums[i]];}int index 0;for (int i 0; i max ; i) {while (bucket[i]--) {//计数归零的时候停止nums[index] i;}}}时间复杂度On; 空间复杂度On; 稳定排序
