原理:
- 选序列的第一个数为基数
- 从后向前找一个比基数小的数,从前向后找一个比基数大的数,swap
- 依次迭代,得到基数的正确位置
- 基数前后的两个序列递归进行上述过程
图解:
low与high相遇时为基数正确位置
图解来自https://blog.csdn.net/nrsc272420199/article/details/82587933
代码:
#include <iostream>
#include <algorithm>
using namespace std;
int Partion(int* a, int left, int right) //划分过程
{
int cardinal = a[left];
int i = left, j = right;
while (i < j)
{
while (i<j&&a[j]>cardinal)
--j;
if (i < j)
std::swap(a[i++], a[j]);
while (i < j&&a[i] < cardinal)
++i;
if (i < j)
std::swap(a[j--], a[i]);
}
a[i] = cardinal;
return i;
}
void Quick_sort(int* a, int left, int right)
{
if (right > left)
{
int pos = Partion(a, left, right);
Quick_sort(a, left, pos - 1);
Quick_sort(a, pos + 1, right);
}
}
int main(int argc, char** argv)
{
int a[5] = { 2,4,1,3,5 };
Quick_sort(a, 0, 4);
for (int i = 0; i <= 4; i++)
cout << a[i] << " ";
return 0;
}
结果:1 2 3 4 5