快速排序
int Qsortkey1(int a[], int left, int right)
{
//挖坑法
int begin = left, end = right;
//三数取中
int tmp = san(a, left, right);
Swap(&a[tmp], &a[begin]);int key = a[begin];
int keyi = begin;
int pivot = begin;while (begin < end)
{//向左找小while (begin < end && a[end] >= key)end--;a[pivot] = a[end];pivot = end;//向右找大while (begin < end && a[begin] <= key)begin++;a[pivot] = a[begin];pivot = begin;
}
a[begin] = key;
pivot = begin;
keyi = pivot;return keyi;
}
//快排1
void Qsort1(int a[], int left, int right)
{
if (left >= right)
return;
int keyi = Qsortkey1(a, left, right);//递归
Qsort1(a, left, keyi - 1);
Qsort1(a, keyi + 1, right);
}
int Qsortkey2(int a[], int left, int right)
{
int begin = left, end = right;
//三数取中
int tmp = san(a, left, right);
Swap(&a[tmp], &a[begin]);int keyi = begin;while (begin < end)
{//end向左边找小,找到就停while (begin < end && a[end] >= a[keyi])end--;while (begin < end && a[begin] <= a[keyi])begin++;Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;return begin;
}