数据结构入门——排序（代码实现）（下）

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;
		}
	}
}

1. 三数取中

2. int GetMidi(int* a, int left, int right)：这是一个名为GetMidi的函数，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。

3. int mid = (left + right) / 2;：计算左右边界索引的中间索引mid，用于表示三个元素中间位置的索引。

4. if (a[left] < a[mid])：如果左边界元素小于中间元素。

   a. if (a[mid] < a[right])：且中间元素小于右边界元素，则中间元素为中间值，返回中间索引mid。

   b. else if (a[left] > a[right])：否则，如果左边界元素大于右边界元素，说明中间元素为最大值，返回左边界索引left。

   c. else：否则，右边界元素为最大值，返回右边界索引right。

5. 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;
};

1. 快速排序（一）

2. int PartSort1(int* a, int left, int right)：这是一个名为PartSort1的函数，用于对数组进行划分操作，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。

3. int keyi = left;：初始化关键元素索引keyi为左边界索引left，作为划分的基准元素索引。

4. while (left < right)：进入一个while循环，循环条件是左边界索引小于右边界索引，表示还有未比较的元素。

5. while (left < right && a[right] >= a[keyi])：从右边开始找到第一个小于基准元素的元素位置。

6. while (left < right && a[left] <= a[keyi])：从左边开始找到第一个大于基准元素的元素位置。

7. Swap(&a[left], &a[right]);：交换左右两侧找到的不符合条件的元素，使得左侧元素小于基准元素，右侧元素大于基准元素。

8. 继续循环，直到左右指针相遇。

9. Swap(&a[keyi], &a[left]);：交换基准元素和左指针所指的元素，将基准元素放置到正确的位置。

10. 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;
}

1. 快速排序（二）

2. int PartSort2(int* a, int left, int right)：这是一个名为PartSort2的函数，用于对数组进行划分操作，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。

3. int midi = GetMidi(a, left, right);：调用GetMidi函数找到左、中、右三个元素中的中间值索引midi，并将中间值元素与左边界元素交换位置。

4. int key = a[left];：将左边界元素作为基准值key。

5. int hole = left;：初始化一个坑位hole，用于保存基准值的位置。

6. while (left < right)：进入一个while循环，循环条件是左边界索引小于右边界索引，表示还有未比较的元素。

7. while (left < right && a[right] >= key)：从右边开始找到第一个小于基准值的元素位置。

   a. a[hole] = a[right];：将找到的小于基准值的元素填充到左边的坑位，并更新坑位hole为右边界索引right。

8. while (left < right && a[left] <= key)：从左边开始找到第一个大于基准值的元素位置。

   a. a[hole] = a[left];：将找到的大于基准值的元素填充到右边的坑位，并更新坑位hole为左边界索引left。

9. 继续循环，直到左右指针相遇。

10. a[hole] = key;：将基准值填充到最后的坑位，完成一次划分操作。

11. 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;
}

1. 快速排序（三）

2. int PartSort3(int* a, int left, int right)：这是一个名为PartSort3的函数，用于对数组进行划分操作，接受一个整型数组指针a，左边界索引left和右边界索引right作为参数。

3. int midi = GetMidi(a, left, right);：调用GetMidi函数找到左、中、右三个元素中的中间值索引midi，并将中间值元素与左边界元素交换位置。

4. int prev = left;：初始化prev为左边界索引left，用于记录小于基准值的元素的位置。

5. int cur = prev + 1;：初始化cur为prev的下一个位置，用于遍历数组。

6. int keyi = left;：初始化keyi为左边界索引left，作为划分的基准元素索引。

7. while (cur <= right)：进入一个while循环，循环条件是当前位置小于等于右边界索引，表示还有未比较的元素。

8. if (a[cur] < a[keyi] && ++prev != cur)：如果当前元素小于基准值且prev不等于cur，则交换prev和cur位置的元素，将小于基准值的元素放到prev的下一个位置。

9. ++cur;：移动cur指针到下一个位置。

10. 继续循环直到遍历完整个数组。

11. Swap(&a[prev], &a[keyi]);：将基准值放置到prev位置，完成一次划分操作。

12. return prev;：返回基准值的最终位置，用于后续递归调用。