C++快速排序
void Partition(vector
<int> &data
, int left
, int right
)
{
if (right
<= left
)
return;
int target
= data
[left
];
int start
= left
;
int end
= right
;
while (end
> start
)
{
while (end
> start
&& data
[end
] >= target
)
--end
;
while (end
> start
&& data
[start
] <= target
)
++start
;
if (end
> start
)
swap(data
[start
], data
[end
]);
}
swap(data
[left
], data
[end
]);
int mid
= end
;
Partition(data
, left
, mid
);
Partition(data
, mid
+ 1, right
);
}
至于为什么从右端先开始：在while结束时，会让target和左右指针相遇的数进行交换，因为从右向左遍历时，会在第一个小于target的数停下来，此时保证交换后的两数为升序。
