.png)
手机版
网站首页
全国服务热线：400-6263-721全国服务热线：400-6263-721位置：郑州童程童美少儿编程培训机构 > 学校动态 > CSP-S 初赛 排序算法
CSP-S 初赛问题求解与选择题
时间复杂度计算
排序算法详解
基础知识【背诵】
算法 较大时间复杂度 平均时间复杂度 稳定性 分类
直接插入排序 O ( n 2 ) O(n^2) O(n
2
) O ( n 2 ) O(n^2) O(n
2
) 稳定 插入排序
希尔排序 O ( n 3 2 ) O(\dfrac{n^3}{2}) O(
2
n
3
) O ( n 3 2 ) O(\dfrac{n^3}{2}) O(
2
n
3
) 不稳定 插入排序
冒泡排序 O ( n 2 ) O(n^2) O(n
2
) O ( n 2 ) O(n^2) O(n
2
) 稳定 交换排序
排序 O ( n 2 ) O(n^2) O(n
2
) O ( n log n ) O(n \log n) O(nlogn) 不稳定 交换排序
直接选择排序 O ( n 2 ) O(n^2) O(n
2
) O ( n 2 ) O(n^2) O(n
2
) 不稳定 选择排序
堆排序 O ( n log n ) O(n \log n) O(nlogn) O ( n log n ) O(n \log n) O(nlogn) 不稳定 选择排序
归并排序 O ( n log n ) O(n \log n) O(nlogn) O ( n log n ) O(n \log n) O(nlogn) 稳定 选择排序
基数排序 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) 稳定 选择排序
各种排序算法
直接插入排序
定义：将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。
希尔排序
定义：
Shell排序有效地利用了直接插入排序的两个性质： 在较好情况(序列本身已是有序的)下时间代价为Θ(n) ;对于短序列，直接插入排序比较有效：
先将序列转化为若干小序列，在这些小序列内进行插入排序。
逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态。
较后对整个序列进行扫尾直接插入排序，从而完成排序。
冒泡排序
定义：不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。
注意：避免不必要的比较。检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束。
排序
定义：
选择轴值(pivot)。
将序列划分为两个子序列L和R，使得L中所有记录都小于或等于轴值，R中记录都大于轴值。
对子序列L和R递归进行排序。
直接选择排序
选出剩下的未排序记录中的较小记录，然后直接与数组中第i个记录交换
堆排序
基于较大值堆来实现
归并排序
简单地将原始序列划分为两个子序列，并分别对每个子序列递归排序;
较后将排好序的子序列合并为一个有序序列，即归并过程。
归并排序可以求逆序对
基数排序
假设长度为 n n n 的序列 R = { r 0 ， r 1 ， … ， r n − 1 } R=\{ r_0，r_1，…，r_n-1 \} R={r
0
，r
1
，…，r
n
−1}
记录的排序码 K K K 包含 d d d 个子排序码 K = ( k d − 1 ， k d − 2 ， … ， k 1 ， k 0 ) K=(k_d-1，k_d-2，…，k_1，k_0 ) K=(k
d
−1，k
d
−2，…，k
1
，k
0
)
R R R 对排序码 ( k d − 1 ， k d − 2 ， … ， k 1 ， k 0 ) (k_d-1，k_d-2，…，k_1，k_0 ) (k
d
−1，k
d
−2，…，k
1
，k
0
) 有序
对于任意两个记录 R i ， R j ( 0 ≤ i < j ≤ n − 1 ) R i，R j (0 ≤ i< j ≤ n-1)
Ri，Rj(0≤i
基数排序分为两类：高位法 M S D MSD MSD，低位法 L S D LSD LSD
尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2474/news/611266/违者必究！ 以上就是郑州童程童美少儿编程培训机构 小编为您整理 CSP-S 初赛 排序算法的全部内容。
