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

news/2024/5/19 0:05:24

int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (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;：返回基准值的最终位置，用于后续递归调用。