排序算法整理C++(初赛)
2022/9/5 1:26:10
本文主要是介绍排序算法整理C++(初赛),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
排序算法整理
常见考点
- 将一个乱掉的字符串排回有序(以交换为基本操作)的最少操作,就是冒泡排序。
- 排序算法的稳定性
- 排序算法的时间复杂度
排序算法的稳定性
稳定性是指排序前两个元素a1 = a2,a1在前。排序过后,倘若a1始终在前,则算法是稳定的,否则是不稳定的。
稳定的
冒泡排序、插入排序、归并排序、基数排序
不稳定的
堆排序、快速排序、希尔排序、选择排序
各个算法细锁
冒泡排序
基本思路:双重循环遍历数组,交换两个相邻的逆序的数字。时间复杂度一般 - \(O(n^2)\),最坏 - \(O(n^2)\),最好\(O(n)\)。
代码
for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n - i; j ++) { if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); } }
都说最优复杂度是O(N),但显然这个程序怎么看都是\(O(n^2)\),实际上\(O(n)\)是优化过的。考试的时候记住就行。
选择排序
基本思路:遍历一遍数组 i in (1, n + 1),从 i 数开始遍历到后面,寻找最小的比它小的数,与它交换。
无论如何都是\(O(n^2)\)。
代码
for(int i = 1; i < n; i ++) { int min = i; for(j = i + 1; j <= n; j ++) { if(a[min] > a[j]) min = j; swap(a[i], a[min]); } }
归并排序
分治思想,将数组中所有的数递归分为两个一组
网上讲的挺好的归并排序MergeSort(通俗易懂_kevinmeanscool的博客-CSDN
这个算法还能用来求逆序对,所以在复赛中也挺重要 虽然现在一般复赛不会考,只要在else后面(代码)加一句ans += mid - i +1
,但我不知道原理。
代码
void merge_sort(int a[], int l, int r){ if(l >= r) return; int mid = l + r >> 1; merge_sort(a, l, mid); merge_sort(a, mid + 1, r); int k = 0; int i = l; int j = mid + 1; while(i <= mid && j <= r){ if(a[i] <= a[j]) f[k ++] = a[i ++]; else f[k ++] = a[j ++]; } while(i <= mid) f[k ++] = a[i ++]; while(j <= r) f[k ++] = a[j ++]; for(i = l, j = 0; i <= r; i ++, j ++){ a[i] = f[j]; } }
快速排序
基本思路:找一个基准数,先由i从左边出发,找到一个小于,j再从右边出发,找一个小于基准数的数。分开区间,重复此操作。时间复杂度平均\(O(nlon_n)\),最优也是\(O(nlon_n)\),最差\(O(n^2)\)。
代码
void qsort(int l, int r) { int mid = a[l + r >> 1]; int i = l, j = r; do{ while(a[i] < mid) i ++; while(a[j] > mid) j --; if(i <= j) { swap(a[i], a[j]); i ++; j --; } }while(i <= j); if(l < j) qsort(l, j); if(i < r) qsort(i, r); } int main() { qsort(1, n); }
根据代码图解
(如果加载不出来请刷新,因为图放在Github):
数组:[3, 2, 9, 5, 1, 8, 2]
找到了
交换,注意i ++, j -- 不然会死循环
i 不再动了,因为a[i] = mid
这里没写 i ++, j --
这篇关于排序算法整理C++(初赛)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享