1.冒泡排序
基本思想:两数比较大小,较大数后移,较小数前移
平均时间复杂度:o(n2)
代码实现:
void bubblesort(int arr[],int len) { int temp, i, j; for (i = 0; i < len - 1; i++) { for (j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
针对问题:顺序排好后,冒泡排序可能会继续下一轮循环,直到满足退出条件
优化方案:若本轮没有发生两数交换,则退出循环
void bubblesort(int arr[],int len) { int temp, i, j,flag; for (i = 0; i < len - 1; i++) { flag = 0 for (j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { flag = 1;/*发生两数交换,flag 置为 1*/ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (flag == 0) { break; } } }
2.选择排序
基本思想:第 i 次遍历数组,找出最小的数值与第 i 个元素交换
平均时间复杂度:o(n2)
代码实现:
void sort(int a[],int n){ int i,j,min,t; for(i=0;i<n-1;i++){ min=i; for(j=i+1;j<n;j++){ if(a[j]<a[min]){ min=j; } } if(min!=i){ t=a[i]; a[i]=a[min]; a[min]=t; } } }
参考资料:
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600307.html