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;
:返回基准值的最终位置,用于后续递归调用。