【数据结构】快速排序

5.1 hoare版本(左右指针法)
思路：

1. 选择一个基准值（key），通常是最左边或最右边的元素。
2. 定义两个指针：begin 和 end。begin 从左向右移动，end 从右向左移动。（注意：若选择最左边的元素作为 key，则应先移动 end；若选择最右边的元素作为 key，则应先移动 begin。）
3. 在移动过程中：
   • 若 end 遇到小于 key 的数，则停止。
   • begin 开始移动，直到遇到大于 key 的数。
   • 交换 begin 和 end 指向的元素。
   • 重复上述步骤，直到 begin 和 end 相遇。
   • 最后，将相遇点的元素与 key 交换。（假设选取最左边的值作为 key）
4. 此时，key 左侧的元素都小于 key，右侧的元素都大于 key。
5. 对 key 的左序列和右序列递归执行上述排序过程。持续这一操作，直到左右序列只剩一个元素或不存在。此时，该部分序列已排序完成。

快排动图解析

//快速排序   hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end
//只有一个数或区间不存在
if (begin >= end)
return;
int left = begin;
int right = end;
//选左边为key
int keyi = begin;
while (begin < end)
{
//右边选小   等号防止和key值相等    防止顺序begin和end越界
while (arr[end] >= arr[keyi] && begin < end)
{
--end;
}
//左边选大  
while (arr[begin] <= arr[keyi] && begin < end)
{
++begin;
}
//小的换到右边，大的换到左边
swap(&arr[begin], &arr[end]);
}
swap(&arr[keyi], &arr[end]);
keyi = end;
//[left,keyi-1]    keyi[keyi+1,right]
QuickSort(arr, left, keyi - 1);
QuickSort(arr,keyi + 1,right);
}

5.2

挖坑法：

动图显示

挖坑法思路：

挖坑法的本质其实是空间挪移，跟七巧板的原理差不多，将无序排成有序，需要有一个空间暂时进行回避，让其他元素进行流通

步骤

挖坑法步骤：

1. 创建左右指针。
2. 从右向左找出比基准小的数据：
   • 找到后立即放入左边"坑"中。
   • 当前位置变为新的"坑"。
3. 从左向右找出比基准大的数据：
   • 找到后立即放入右边"坑"中。
   • 当前位置再次变为新的"坑"。
4. 重复步骤2和3，直到左右指针相遇。
5. 结束循环后，将最初存储的分界值放入当前的"坑"中。
6. 返回当前"坑"下标（即分界值下标）。

代码实现：

void QuickSort1(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left < right && arr[right] >= key)
{
right--;
}
arr[hole] = arr[right];
hole=right;
while(left<right&&arr[left]<=key)
{
left++;
}
arr[hole] = arr[left];
hole = left;

}
arr[hole] = key;

}

lomuto前后指针法
方法简介：
建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边

代码：

void _QuickSort(int* arr, int left, int right)//lomuto指针法
{
int prev = left,cur = left + 1;
int key = left;
while (cur <= right)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[key]);
}

非递归版本：

递归的思想是不断的二分

非递归版本要借用栈的思想实现二分

栈：后进先出，栈顶进数据，也出数据，栈底不能

right先入栈，left在入栈，再出栈，left和right就是区间，找基准值，分区间

右区间入栈，基准值为keyi。

左区间[left,keyi-1]

右区间[keyi+1,right]

右区间入栈，right入栈，keyi+1入栈

左区间入栈，keyi-1入栈，left入栈

在此出栈，

栈不为空，栈出栈两次。left=0，right=2

在实际数组中，找基准值，keyi=0；（此数组）

左区间【0，-1】（非有效区间不入栈）

右区间【1，2】入栈

栈不为空，出栈两次

left=1，right2

找keyi，keyi=1

左区间【1，0】（非有效区间不入栈）

右区间【2，2】（只有一个数据也不入栈）

以上左区间全部找完

接下来找右区间

出栈两次

left=4，right=5；

找keyi，keyi=4；

左区间【4，3】【非有效区间不如栈】

右区间【5，5】【只有一个数据不入栈】

void  QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素
int begin = StackTop(&st);
stackpop(&st);
int end = StackTop(&st);
stackpop(&st);
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] <= arr[keyi]&&++prev!=cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}

Swap(&arr[keyi], &arr[prev]);
keyi = prev;

找基准值；
//左区间【begin,keyi-1】
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 < begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);

} 

}

STDestroy(&st);
}

原文地址：https://blog.csdn.net/wheeldown/article/details/143509959

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！