数据结构 十大排序超硬核八万字详解【附动图演示、算法复杂度性能分析】

int right = end;
int keyi = begin;		//以最左边作为对照值记录，右边先走
while (left < right)
{
	//右边找比keyi所在位置小的值，若是 >= 则忽略（加上=防止死循环）
	while (left < right && a[right] >= a[keyi])
	{		//left < right —— 防止特殊情况越界
		right--;
	}

	//左边找比keyi所在位置大的值，若是 <= 则忽略
	while (left < right && a[left] <= a[keyi])
	{
		left++;
	}

	//都找到了，则交换
	swap(&a[left], &a[right]);
}
//最后当left和right相遇的时候将相遇位置的值与keyi位置的值交换
swap(&a[left], &a[keyi]);

keyi = left;		//因keyi位置的值被交换到相遇点，因此更新准备分化递归

return keyi;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

}

1
2

void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return; //最后递归下去区间不存在了，进行递归回调

int key = PartSort1(a, begin, end);		//单趟排序获取key值

//左右区间分化递归
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
1
2
3
4
5

}

---


* 其他的都不会有很大问题，我们主要来讲讲内部的循环逻辑
* 看到内部的这两段循环就是来控制L与R进行寻找走动的代码，也是快速排序的核心❤️所在



1
2
3
4
5
6
7
8
9
10
11

//右边找比keyi所在位置小的值，若是 >= 则忽略（加上=防止死循环）
while (left < right && a[right] >= a[keyi])
{ //left < right —— 防止特殊情况越界
right–;
}

//左边找比keyi所在位置大的值，若是 <= 则忽略
while (left < right && a[left] <= a[keyi])
{
left++;
}

* 但是有的同学在一上来可能就会写成这样，也是很多同学的通病（没有考虑到特殊情况）



1
2
3
4
5

//右边找比keyi所在位置小的值，若是 >= 则忽略（加上=防止死循环）
while (a[right] > a[keyi])
{ //left < right —— 防止特殊情况越界
right–;
}

//左边找比keyi所在位置大的值，若是 <= 则忽略
while (a[left] < a[keyi])
{
left++;
}

* 原因就是以下两点


⚠**没控制端点导致越界风险**  
 ⚠**没考虑相等情况导致死循环**


![在这里插入图片描述](https://img-blog.csdnimg.cn/252842aa937943719ccd3a1b831b0019.jpeg#pic_center)


* 接下去要说的就是第一次交换结束后的分化递归
* 我要特别强调的就是这一句，也就是**重置这个keyi，然后将其返回**，这个keyi不是新的keyi值，而是因为keyi被交换到了left所在位置，因此我们要做个标记方面后面的递归可以进行左右划分，当然你直接使用left或者right也是可以的，就是不要使用keyi就行了，否则这个区间就会异常
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/922089