结果如下:
第五次
0 1 2 3 4 5 6
3 4 5 9 2 1 7继续使用 pivot = 5 与 a[high] 进行对比
同样进行交换,结果如下:
第六次
0 1 2 3 4 5 6
3 4 1 9 2 5 7继续使用 pivot = 5 与 a[low] 进行对比
结果如下:(low++)
第七次
0 1 2 3 4 5 6
3 4 1 9 2 5 7继续使用 pivot = 5 与 a[low] 进行对比
结果如下:
第八次
0 1 2 3 4 5 6
3 4 1 5 2 9 7继续使用 pivot = 5 与 a[high] 进行对比
结果如下:(high--)
第九次
0 1 2 3 4 5 6
3 4 1 5 2 9 7继续使用 pivot = 5 与 a[high] 进行对比
结果如下:(最终结果low == high,橙色表示)
第九次
0 1 2 3 4 5 6
3 4 1 2 5 9 7最后由于 low++ 所以 low == high
到这里,已经利用 基准数pivot = 5 把这个数列分为了两部分(5 的左边都是小于它的,右边都是大于它的)
然后递归。用同样的方法,对分割出来的两部分用"基准数"继续进行分割
快排函数代码:
[cpp]
//快排函数
void sort(int *s, int low, int high)
{
int pivot;
//if语句的判断是结束递归的简单情景,不能缺
if (low < high)
{
// partition 函数就是利用基准数进行分割的功能函数,这个函数是重点
pivot = partition(s, low, high);
sort(s, pivot + 1, high);
sort(s, low, pivot - 1);
}
}
什么是递归的简单情景?可以看看这里
partition 函数代码:
[cpp]
//这个函数就是上面演示的代码实现
int partition(int *s, int low, int high)
{
int pivot;
pivot = s[low];
while (low < high)
{
while (low < high && pivot <= s[high])
{
high--;
}
swap(&s[low], &s[high]);
while (low < high && pivot >= s[low])
{
low++;
}
swap(&s[high], &s[low]);
}
return low;
}