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排序的优化见下篇文章