目录
前言
单躺排序逻辑的实现
前言
在上一章学习了 hoaer 版本的快速算法>排序算法的实现
数据结构 ——— 快速算法>排序算法的实现(hoare版本)-CSDN博客
可是 hoaer 版本的快速算法>排序算法存在缺陷
比如说:如果把最左边的值当作 key 的话,那么就必须让右边先走,也就是要让右边先找到比 key 小的值,否则的话最后排出来的就是乱序
因为 left 是找比 key 大的值,right 是找比 key 小的值,只有让 right 先走,才能保证当他们快要相遇时,相遇的值比 key 小,否则让 left 先走的话,最后相遇的位置就不一定是比 key 小的值
所以基于上述原因,对 hoare 版本的快速算法>排序算法进行了改进,避免了这些缺陷
快速算法>排序算法(挖坑版本)的思想
同样是 left 往右边走,找比 key 小的值; right 往左边走,找比 key 大的值;且 key 是最左边的值
不同之处在于是把 key 的值先保存下来,那么就可以形象的理解为 key 的位置被挖了一个坑
然后 right 找到比 key 小的值时,就把小的值放在 key 的位置,也就是放在坑的位置
那么 right 这个位置就形成了新的坑,然后 left 再找,当 left 找到比 key 大的值时,就放到 right 这个坑的位置,最后 left 和 right 相遇的位置也肯定是一个坑,再把保存的 key 放入坑中
这时的数组同样能保证 key 左边的值比 key 小,key 右边的值比 key 大,且就算 left 先走也同样可以完成
以上就是挖坑法单躺排序的思想
单躺排序逻辑的实现
int PartSort_DigPit(int* a, int left, int right)
{// 保存 key 的值int key = a[left];// 坑的下标int hole = left;while (left < right){// 先找右边比 key 小的元素的下标while (left < right && a[right] >= key)right--;// 填坑a[hole] = a[right];// 赋值新坑的下标hole = right;// 再找左边比 key 大的元素的下标while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;}// 把 key 放在最终位置a[hole] = key;return hole;
}
快速算法>排序算法的实现(挖坑法)
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int key = PartSort_DigPit(a, begin, end);// [begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
除了挖坑法单躺的思想和 hoare 版本单躺的思想有差异,其他的思路都是一样的
这里就不过多赘述,直接看结论
代码验证: