目录
- 一、计数排序
1.问题分析并选择合适的数据结构
2.算法正确性的证明
3.算法的分析 - 二、基数排序
1.问题分析并选择合适的数据结构
2.算法正确性的证明
3.算法的分析 - 三、桶排序
1.问题分析并选择合适的数据结构
2.算法正确性的证明
3.算法的分析
问题定义
一、计数排序
1.问题分析并选择合适的数据结构
计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)，排序时间为线性时间。
计数排序的基本思想：对每一个元素x，确定小于x的元素个数。
在计数排序算法代码中，假设输入是一个数组A[1..n]，A.length=n。我们还需要两个数组：B[1..n]存放排序的输出，C[0..k]提供临时存储空间。
2.算法正确性的证明
3.算法的分析
当k=O(n)，排序时间为线性时间。
二、基数排序
1.问题分析并选择合适的数据结构
与人们的直观感受相悖，基数排序是先按最低有效位进行排序来解决卡片排序问题的。从低位到高位进行。
因此，为了确保基数排序的正确性，一位数排序算法必须是稳定的。
基数排序的代码是非常直观的。假设n个d位元素存放在数组A中，其中第1位是最低位，第d位是最高位。
2.算法正确性的证明
3.算法的分析
三、桶排序
1.问题分析并选择合适的数据结构
桶排序假设输入数据服从均匀分布，平均情况下它的时间代价为O(n)。
计数排序假设输入属于一个小区间内的整数，而桶排序假设输入是由一个随机过程产生的，该过程将元素均匀、独立地分布在[0, 1]区间上。
在桶排序代码中，假设输入是一个包含n个元素的数组A，且每个元素0 <= A[i] < 1。此外，算法还需要一个临时数组B[0..n-1]来存放链表（即桶）。
2.算法正确性的证明
3.算法的分析
平均情况下它的时间代价为O(n)
