int GetMidi(int* a, int left, int right)
{
int mid = (left + right) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
-
三数取中
-
int GetMidi(int* a, int left, int right)：这是一个名为GetMidi的函数，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。 -
int mid = (left + right) / 2;：计算左右边界索引的中间索引mid，用于表示三个元素中间位置的索引。 -
if (a[left] < a[mid])：如果左边界元素小于中间元素。a.
if (a[mid] < a[right])：且中间元素小于右边界元素，则中间元素为中间值，返回中间索引mid。b.
else if (a[left] > a[right])：否则，如果左边界元素大于右边界元素，说明中间元素为最大值，返回左边界索引left。c.
else：否则，右边界元素为最大值，返回右边界索引right。 -
else：如果左边界元素大于中间元素。a.
if (a[mid] > a[right])：且中间元素大于右边界元素，则中间元素为中间值，返回中间索引mid。b.
else if (a[left] < a[right])：否则，如果左边界元素小于右边界元素，说明中间元素为最小值，返回左边界索引left。c.
else：否则，右边界元素为最小值，返回右边界索引right。
// Hoare
int PartSort1(int* a, int left, int right)
{
//int midi = GetMidi(a, left, right);
//Swap(&a[left], &a[midi]);
int keyi = left;
while (left < right)
{
// 找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
// 找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
};-
快速排序（一）
-
int PartSort1(int* a, int left, int right)：这是一个名为PartSort1的函数，用于对数组进行划分操作，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。 -
int keyi = left;：初始化关键元素索引keyi为左边界索引left，作为划分的基准元素索引。 -
while (left < right)：进入一个while循环，循环条件是左边界索引小于右边界索引，表示还有未比较的元素。 -
while (left < right && a[right] >= a[keyi])：从右边开始找到第一个小于基准元素的元素位置。 -
while (left < right && a[left] <= a[keyi])：从左边开始找到第一个大于基准元素的元素位置。 -
Swap(&a[left], &a[right]);：交换左右两侧找到的不符合条件的元素，使得左侧元素小于基准元素，右侧元素大于基准元素。 -
继续循环，直到左右指针相遇。
-
Swap(&a[keyi], &a[left]);：交换基准元素和左指针所指的元素，将基准元素放置到正确的位置。 -
return left;：返回基准元素的最终位置，用于后续递归调用。
int PartSort2(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int key = a[left];
// 保存key值以后，左边形成第一个坑
int hole = left;
while (left < right)
{
// 右边先走，找小，填到左边的坑，右边形成新的坑位
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
// 左边再走，找大，填到右边的坑，左边形成新的坑位
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}-
快速排序（二）
-
int PartSort2(int* a, int left, int right)：这是一个名为PartSort2的函数，用于对数组进行划分操作，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。 -
int midi = GetMidi(a, left, right);：调用GetMidi函数找到左、中、右三个元素中的中间值索引midi，并将中间值元素与左边界元素交换位置。 -
int key = a[left];：将左边界元素作为基准值key。 -
int hole = left;：初始化一个坑位hole，用于保存基准值的位置。 -
while (left < right)：进入一个while循环，循环条件是左边界索引小于右边界索引，表示还有未比较的元素。 -
while (left < right && a[right] >= key)：从右边开始找到第一个小于基准值的元素位置。a.
a[hole] = a[right];：将找到的小于基准值的元素填充到左边的坑位，并更新坑位hole为右边界索引right。 -
while (left < right && a[left] <= key)：从左边开始找到第一个大于基准值的元素位置。a.
a[hole] = a[left];：将找到的大于基准值的元素填充到右边的坑位，并更新坑位hole为左边界索引left。 -
继续循环，直到左右指针相遇。
-
a[hole] = key;：将基准值填充到最后的坑位，完成一次划分操作。 -
return hole;：返回基准值的最终位置，用于后续递归调用。
int PartSort3(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
return prev;
}-
快速排序（三）
-
int PartSort3(int* a, int left, int right)：这是一个名为PartSort3的函数，用于对数组进行划分操作，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。 -
int midi = GetMidi(a, left, right);：调用GetMidi函数找到左、中、右三个元素中的中间值索引midi，并将中间值元素与左边界元素交换位置。 -
int prev = left;：初始化prev为左边界索引left，用于记录小于基准值的元素的位置。 -
int cur = prev + 1;：初始化cur为prev的下一个位置，用于遍历数组。 -
int keyi = left;：初始化keyi为左边界索引left，作为划分的基准元素索引。 -
while (cur <= right)：进入一个while循环，循环条件是当前位置小于等于右边界索引，表示还有未比较的元素。 -
if (a[cur] < a[keyi] && ++prev != cur)：如果当前元素小于基准值且prev不等于cur，则交换prev和cur位置的元素，将小于基准值的元素放到prev的下一个位置。 -
++cur;：移动cur指针到下一个位置。 -
继续循环直到遍历完整个数组。
-
Swap(&a[prev], &a[keyi]);：将基准值放置到prev位置，完成一次划分操作。 -
return prev;：返回基准值的最终位置，用于后续递归调用。
