代码实现参见github/algorithm中各个类别下wz包中的代码。
2.算法中常犯错误
2.1 插入排序——稳定排序
- 39）少了对数据索引范围的检查
- 40）同堆中siftUp siftDown一样，循环外的赋值出错了
while (j >= 0 && e < array[j]) {
array[j + 1] = array[j];
j--;
}
// 这里之前赋值错写成了array[j] = e
array[j + 1] = e;
2.2 希尔排序
- 41）while循环常犯的错误，三要素中忘了更新推进循环的变量
while (j >= 0 && e < array[j]) {
array[j + increment] = array[j];
// 忘了更新j
j -= increment;
}
2.3 冒泡排序——稳定排序
2.4 选择排序
2.5 归并排序——稳定排序
2.6 快速排序
- 42）递归算法，缺少终止条件
private void sortCore(int left, int right) {
// 注意，递归解法都有终止条件，千万不要缺少！
if (right - left <= 0) {
return;
}
- 43）for循环中i变量的初始状态不要想当然写成i = 0
private int partition(int left, int right) {
int mid = array[right];
// less指向左边小于mid子数组最后索引的下一个
// 这里注意less起始地址是left不是0
int less = left;
for (int i = left; i <= right - 1; i++) {
// 算法导论的版本是<=，将小于等于的都放在左边
if (array[i] <= mid) {
swap(less++, i);
}
}
2.7 三向快速排序+三向字符串快速排序
- 44）长度、索引检测
// 这里犯了严重错误，只有长度允许，才继续
if (v.length() > d + 1) {
sort2(low, high, d + 1);
}
- 45）>=与>的区别
private boolean less(String a, String b, int d) {
for (int i = d; i < Math.min(a.length(), b.length()); i++) {
// 犯了小错误，这里应该是charAt(i)而不是charAt(d)
if (a.charAt(i) < b.charAt(i)) {
return true;
} else if (a.charAt(i) > b.charAt(i)) {
// 这个地方刚开始写错了，写成了>=，应该是>，等于则必须向后
return false;
}
}
- 总结：对于while循环，核心就是循环不变量，清晰定义循环不变量中各个变量表示的含义，以及循环不变量的状态是什么
2.8 堆排序
2.9 计数排序
2.10 字符串的低位优先排序
2.11 高位优先排序
- 46）索引检查
// 少了索引检测
checkValid(low, high);
if (high - low + 1 <= MIN_LENGTH) {
insertionSort(low, high, d);
// 少了return
return;
}
