120.【C语言】数据结构之快速排序(详解Hoare排序算法)
目录
1.Hoare单趟排序思想
2.单趟排序代码
初次写的代码
运行结果
查找问题原因
尝试解决问题
初次修正后代码
运行结果
正确的单趟排序代码
3.将单趟排序嵌入
如何递归?
递归结束的条件
1.较容易分析的结束条件:left==right
2.以{2,1}为例分析另一个结束条件
完整代码
运行结果
1.Hoare单趟排序思想
例如对于无序数组arr={6,1,2,7,9,3,4,5,10,8},排升序
① 选一个基准值(又叫关键值)key,一般来说key选arr[0](其实key也可以取其他值,下篇会详细介绍)
② 如果数组一共n个数,两个指针left和right分别从数组的左侧arr[0]和右侧arr[n-1]出发,其中right先走
③ left找到arr[left]比key小的就停止right需要找到arr[right]比key大的,之后arr[left]和arr[right]交换,left和right继续寻找,直到left>right或left==right退出
④ 最后将arr[key_i]和arr[left]交换,完成一次单趟排序
{6,1,2,7,9,3,4,5,10,8} --> {3,1,2,5,4,6,9,7,10,8}(比6小的都在6的左边.比6大的都在6的右边)
2.单趟排序代码
初次写的代码
//单趟快速排序
int key_i = left;
while (left < right)
{
//由于key_i==left,因此right指针先走
//右边找小
while (arr[right] > arr[key_i])
{
right--;
}
//左边找大
while (arr[left] < arr[key_i])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key_i], &arr[left]);运行结果
实际上运行结果不正确,6左侧有9,9比6大
查找问题原因
可以在while (arr[right] > arr[key_i])处下断点调试
发现问题:left==0不符合要求
尝试解决问题
可在循环前让left==1跳过arr[0]
int key_i = left;
left++;
while (left < right)
{
//......
}执行结果:实际上运行结果不正确,6左侧有9,9比6大
尝试寻找原因
下断点调试,
上图说明:到目前为止都没有什么问题
执行到下图时,问题出现:left>right还没有退出!
因此要在两个内循环中都加入条件: left<right,确保不越界!
初次修正后代码
//单趟快速排序
int key_i = left;
left++;
while (left < right)
{
//由于key_i==left,因此right指针先走
//右边找小
while (left < right && arr[right] > arr[key_i])
{
right--;
}
//左边找大
while (left < right && arr[left] < arr[key_i])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key_i], &arr[left]);运行结果
没有问题了,与设想的结果相同
其实修正后的代码还有巨大的问题!!
对{1,2,3,4,5}排序,执行结果反而将升序数组的顺序打乱了,问题在哪里?
执行到Swap(&arr[key_i], &arr[left]);时,key_i==0,left==1,导致错误互换,应该将left++删除
执行结果:没有问题了,与设想的结果相同
其实修正后的代码还有巨大的问题!!
对这个数组排序{6,1,2,7,9,3,4,5,10,6}会死循环
arr[right] == arr[key_i] 和 arr[left] == arr[key_i]时right没有变化,导致一直在while (left<right)里执行无法退出
改成while (left < right && arr[right] >= arr[key_i])和while (left < right && arr[left] <= arr[key_i])即可让left和right指针继续查找,而且避免了在while (left<right)执行前让left++的情况
正确的单趟排序代码
//单趟快速排序
int key_i = left;
while (left < right)
{
//由于key_i==left,因此right指针先走
//右边找小
while (left < right && arr[right] >= arr[key_i])
{
right--;
}
//左边找大
while (left < right && arr[left] <= arr[key_i])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key_i], &arr[left]);3.将单趟排序嵌入
如何递归?
第一次单趟排序后的数组{3,1,2,5,4,6,9,7,10,8},接下来分别对6的左侧数据和右侧数据排序
左侧数据表示的区间为[begin,key_i-1] ,右侧数据表示的区间为[key_i+1,end],直接递归调用即可
int begin = left;
int end = right;
//循环省略
QuickSort(arr, begin, key_i - 1);
QuickSort(arr, key_i + 1,end);考虑到循环执行时,left和right的值会改变,因此需要先保存left和right的值至begin和end中
画图为(极像二叉树的递归)
递归结束的条件
何时从递推到回归?(注意返回的条件写在QuickSort函数的最前面)
1.较容易分析的结束条件:left==right
2.以{2,1}为例分析另一个结束条件
则另一个结束条件为left>right
综上:递推结束的条件为left>=right
(其实从区间也能看出递推结束的条件:左区间 [begin,key_i-1]推出当begin<key_i-1时区间成立,begin对应形参left,key_i-1对应形参right,因此left<right;右区间 [key_i+1,end]推出当key_i+1<end时区间成立,key_i+1对应形参left,end对应形参right,因此left<right)
**注意:递归函数先写递归的结束条件再写递推的具体内容**
完整代码
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
//单趟快速排序
int begin = left;
int end = right;
int key_i = left;
while (left < right)
{
//由于key_i==left,因此right指针先走
//右边找小
while (left < right && arr[right] >= arr[key_i])
{
right--;
}
//左边找大
while (left < right && arr[left] <= arr[key_i])
{
left++;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[key_i], &arr[left]);
key_i = left;//arr[key_i]和arr[left]交换后下标要改变,否则会对下次递归产生不利结果
QuickSort(arr, begin, key_i - 1);
QuickSort(arr, key_i + 1,end);
}运行结果
注:有关Hoare排序为什么key_i==left要让right先走的原因和Hoare排序的优化见下篇文章