聊城网站建设找谁,网贷网站建设,一些大型网站的服务器需要租用多大的带宽,网站优化推广排名#x1f525;个人主页#xff1a; Quitecoder
#x1f525;专栏#xff1a;数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序#xff0c;本篇我们来探究非递归实现快速排序和归并排序 目录 1.非递归实现快速排序1.1 提取单趟排序1.2 用栈实现的具体思路1.3 代码…
个人主页 Quitecoder
专栏数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序本篇我们来探究非递归实现快速排序和归并排序 目录 1.非递归实现快速排序1.1 提取单趟排序1.2 用栈实现的具体思路1.3 代码实现 2.归并排序 1.非递归实现快速排序 快速排序的非递归实现主要依赖于栈stack来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子数组而非递归版本则通过手动管理一个栈来跟踪接下来需要排序的子数组的边界 那么怎样通过栈来实现排序的过程呢
思路如下
使用栈实现快速排序是对递归版本的模拟。在递归的快速排序中函数调用栈隐式地保存了每次递归调用的状态。但是在非递归的实现中你需要显式地使用一个辅助栈来保存子数组的边界
以下是具体步骤和栈的操作过程 初始化辅助栈 创建一个空栈。栈用于保存每个待排序子数组的起始索引(begin)和结束索引(end)。 开始排序 将整个数组的起始和结束索引作为一对入栈。这对应于最初的排序问题。 迭代处理 在栈非空时重复下面的步骤 弹出一对索引即栈顶元素来指定当前要处理的子数组。选择子数组的一个元素作为枢轴pivot进行分区可以是第一个元素也可以通过其他方法选择下面我们还是用三数取中。进行分区操作这会将子数组划分为比枢轴小的左侧部分和比枢轴大的右侧部分同时确定枢轴元素的最终位置。 处理子数组 分区操作完成后如果枢轴元素左侧的子数组如果存在有超过一个元素则将其起始和结束索引作为一对入栈。同样如果右侧的子数组如果存在也有超过一个元素也将其索引入栈 循环 继续迭代该过程直到栈为空此时所有的子数组都已经被正确排序。
所以主要思路就两个
分区单趟排序
1.1 提取单趟排序
我们上篇文章讲到递归排序的多种方法这里我们可以取其中的一种提取出单趟排序
int Getmidi(int* a, int begin, int end)
{int midi (begin end) / 2;if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else{if (a[midi] a[end])return midi;else if (a[end] a[begin])return end;elsereturn begin;}
}
void QuickSortHole(int* arr, int begin, int end) {if (begin end) {return;}int midi Getmidi(arr, begin, end);Swap(arr[midi], arr[begin]);int key arr[begin]; int left begin;int right end;while (left right) {while (left right arr[right] key) {right--;}arr[left] arr[right];while (left right arr[left] key) {left;}arr[right] arr[left];}arr[left] key; QuickSortHole(arr, begin, left - 1);QuickSortHole(arr, left 1, end);
}接下来完成单趟排序函数
int singlePassQuickSort(int* arr, int begin, int end)
{if (begin end) {return;}// 选择枢轴元素int midi Getmidi(arr, begin, end);Swap(arr[midi], arr[begin]);int key arr[begin]; // 挖第一个坑int left begin; // 初始化左指针int right end; // 初始化右指针// 进行分区操作while (left right) {// 从右向左找小于key的元素放到左边的坑中while (left right arr[right] key) {right--;}arr[left] arr[right];// 从左向右找大于key的元素放到右边的坑中while (left right arr[left] key) {left;}arr[right] arr[left];}// 将枢轴元素放入最后的坑中arr[left] key;// 函数可以返回枢轴元素的位置若需要进一步的迭代过程return left;
}1.2 用栈实现的具体思路
以下面这串数组为例
首先建立一个栈将整个数组的起始和结束索引作为一对入栈
弹出一对索引即栈顶元素来指定当前要处理的子数组这里即弹出0 9索引 找到枢轴6进行一次单趟排序
针对这个数组
6 3 4 9 5 8 7 2 1 10我们使用“三数取中”法选择枢轴。起始位置的元素为6结束位置的元素为10中间位置的元素为5。在这三个元素中6为中间大小的值因此选择6作为枢轴。因为枢轴已经在第一个位置我们可以直接开始单趟排序。
现在开始单趟排序
枢轴值为6。从右向左扫描找到第一个小于6的数1。从左向右扫描找到第一个大于6的数9。交换这两个元素。继续进行上述步骤直到左右指针相遇。
经过单趟排序后
6 3 4 1 5 2 7 8 9 10接下来需要将枢轴6放置到合适的位置。我们知道最终左指针和右指针会停在第一个大于或等于枢轴值6的位置。在这个例子中左右指针会停在7上。现在我们将6与左指针指向的位置的数交换
5 3 4 1 2 6 7 8 9 10现在枢轴值6处于正确的位置其左侧所有的元素都小于或等于6右侧所有的元素都大于或等于6。
分区操作完成后如果枢轴元素左侧的子数组如果存在有超过一个元素则将其起始和结束索引作为一对入栈。同样如果右侧的子数组如果存在也有超过一个元素也将其索引入栈
我们接下来完成这个入栈过程让两个子数组的索引入栈
接着取0 4索引进行单趟排序并不断分区分割的索引继续压栈继续迭代该过程直到栈为空此时所有的子数组都已经被正确排序
1.3 代码实现
这里我们调用之前的栈的代码基本声明如下
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST; void StackInit(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
// 获取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);我们接下来完成排序代码首先建栈初始化并完成第一个压栈过程
ST s;
StackInit(s);
StackPush(s, end);
StackPush(s, begin);实现一次单趟排序
int left StackTop(s);
StackPop(s);int right StackTop(s);
StackPop(s);int keyi singlePassQuickSort(a, left, right);注意这里我们先压入end那么我们先出的就是begin用left首先获取begin再pop掉获取end 接着判断keyi左右是否还有子数组
if (left keyi - 1)
{StackPush(s, keyi - 1);StackPush(s, left);
}
if (keyi 1right)
{StackPush(s, right);StackPush(s, keyi1);
}将此过程不断循环即为整个过程总代码如下
void Quicksortst(int* a, int begin, int end)
{ST s;StackInit(s);StackPush(s, end);StackPush(s, begin);while (!StackEmpty(s)){int left StackTop(s);StackPop(s);int right StackTop(s);StackPop(s);int keyi singlePassQuickSort(a, left, right);if (left keyi - 1){StackPush(s, keyi - 1);StackPush(s, left);}if (keyi 1right){StackPush(s, right);StackPush(s, keyi1);}}StackDestroy(s);
}这里思想跟递归其实是差不多的也是一次取一组进行排序递归寻找每个区间 2.归并排序
假如我们已经有了两个已经排序好的数组我们如何让他们并为一个有序的数组呢 我们的做法就是用两个索引进行比较然后插入一个新的数组完成排序这就是归并排序的基础思路
那如果左右不是两个排序好的数组呢
下面是归并排序的算法步骤 递归分解数组如果数组的长度大于1首先将数组分解成两个部分。通常这是通过将数组从中间切分为大致相等的两个子数组 递归排序子数组递归地对这两个子数组进行归并排序直到每个子数组只包含一个元素或为空这意味着它自然已经排序好 合并排序好的子数组将两个排序好的子数组合并成一个排序好的数组。这通常通过设置两个指针分别指向两个子数组的开始比较它们指向的元素并将较小的元素放入一个新的数组中然后移动指针。重复此过程直到所有元素都被合并进新数组 所以我们得需要递归来实现这一过程首先声明函数并建造新的数组
void MergeSort(int* a, int n)
{int* tmp (int *) malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}free(tmp);
}由于我们不能每次开辟一遍数组我们这里就需要一个子函数来完成递归过程
void _MergrSort(int* a, int begin, int end, int* tmp)首先不断递归将数组分解
int mid (begin end) / 2;if (begin end)
{return;
}
_MergrSort(a, begin, mid, tmp);
_MergrSort(a, mid1, end, tmp);接着获取分解的两个数组的各自的首端到尾端的索引
int begin1 begin, end1 mid;
int begin2 mid 1, end2 end;令要插入到数组tmp的起点为begin处
int begin1 begin, end1 mid;
int begin2 mid 1, end2 end;
int i begin;接下来遍历两个数组无论谁先走完都跳出循环
while (begin1 end1 begin2 end2)
{if (a[begin1] a[begin2]){tmp[i] a[begin1];i;begin1;}else{tmp[i] a[begin2];i;begin2;}
}这时会有一方没有遍历完按照顺序插入到新数组中即可
while (begin1 end1)
{tmp[i] a[begin1];begin1;i;
}
while (begin2 end2)
{tmp[i] a[begin2];begin2;i;
}插入到新数组后我们拷贝到原数组中即完成了一次排序 memcpy(abegin,tmpbegin,sizeof(int )*(end-begin1));
完整代码如下
void _MergrSort(int* a, int begin, int end, int* tmp)
{int mid (begin end) / 2;if (begin end){return;}_MergrSort(a, begin, mid, tmp);_MergrSort(a, mid1, end, tmp);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];i;begin1;}else{tmp[i] a[begin2];i;begin2;}}while (begin1 end1){tmp[i] a[begin1];begin1;i;}while (begin2 end2){tmp[i] a[begin2];begin2;i;}memcpy(abegin,tmpbegin,sizeof(int )*(end-begin1));
}
void MergeSort(int* a, int n)
{int* tmp (int *) malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergrSort(a, 0, n - 1, tmp);free(tmp);
}排序好的左半部分和右半部分接着被合并。为此使用了两个游标begin1和begin2它们分别指向两个子数组的起始位置然后比较两个子数组当前元素将较小的元素拷贝到tmp数组中。这个过程继续直到两个子数组都被完全合并在所有元素都被合并到tmp数组之后使用memcpy将排序好的部分拷贝回原数组a。这个地方注意memcpy的第三个参数它是sizeof(int)*(end - begin 1)表示拷贝的总大小单位是字节begin和end变量在这里表示待排序和合并的数组部分的起止索引
本节内容到此结束感谢大家阅读
